Testing thresholds for high-dimensional sparse random geometric graphs

The random geometric graph model Geo d (n, p) is a distribution over graphs in which the edges capture a latent geometry. To sample G ∼ Geo d (n, p), we identify each of our n vertices with an independently and uniformly sampled vector from the d-dimensional unit sphere S d-1 , and we connect pairs of vertices whose vectors are "sufficiently close," such that the marginal probability of an edge is p. Because of the underlying geometry, this model is natural for applications in data science and beyond. We investigate the problem of testing for this latent geometry, or in other words, distinguishing an Erdős-Rényi graph G(n, p) from a random geometric graph Geo d (n, p). It is not too difficult to * UC Berkeley.