Abstract
In the random geometric graph model, we identify each of our n vertices with an independently
and uniformly sampled vector from the d-dimensional unit sphere, and we connect pairs of
vertices whose vectors are "sufficiently close", such that the marginal probability of an edge is p.
We investigate the problem of distinguishing an Erdős-Rényi graph from a random geometric
graph. When p = c / n for constant c, we prove that if d ≥ poly log n, the total variation distance
between the two distributions is close to 0; this improves upon the best previous bound of
Brennan, Bresler, and Nagaraj (2020), which required d >> n^{3/2}, and further our result is
nearly tight, resolving a conjecture of Bubeck, Ding, Eldan, and Rácz (2016) up to logarithmic
factors. We also obtain improved upper bounds on the statistical indistinguishability thresholds
in d for the full range of p satisfying 1/n ≤ p ≤ 1/2, improving upon the previous bounds by
polynomial factors.
In this talk, we will discuss the key ideas in our proof, which include:
- Analyzing the Belief Propagation algorithm to characterize the distributions of (subsets of) the
random vectors conditioned on producing a particular graph.
- Sharp estimates for the area of the intersection of a random sphere cap with an arbitrary
subset of the sphere, which are proved using optimal transport maps and entropy-transport
inequalities on the unit sphere.
Based on joint work with Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang.