High-dimensional random geometric graphs
I will talk about a random geometric graph model, 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. Upon observing a graph, we want to tell if it was
generated from this geometric model, or from the Erdos-Renyi model. We
show that there exists a computationally efficient procedure to do this
which is almost optimal (in an information-theoretic sense). The key
insight is based on a new statistic which we call "signed triangles".
To prove optimality we compute the total variation distance between
Wishart matrices and the Gaussian Orthogonal Ensemble. This is joint
work with Sebastien Bubeck, Jian Ding, Ronen Eldan, and Jacob Richey.