Probability Seminar: Miklos Racz

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.