High-dimensional random geometric graphs
2nd November 2018, 4:30 pm – 5:30 pm
Main Maths Building, SM4
I will talk about two natural random geometric graph models, where connections between vertices depend on distances between latent d-dimensional labels. We are particularly interested in the high-dimensional case when d is large. We study a basic hypothesis testing problem: can we distinguish a random geometric graph from an Erdos-Renyi random graph (which has no geometry)? We show that there exists a computationally efficient procedure which is almost optimal (in an information-theoretic sense). The proofs will highlight new graph statistics as well as connections to random matrices. This is based on joint work with Sebastien Bubeck, Jian Ding, Ronen Eldan, and Jacob Richey.