Fall 2020

Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs

Thursday, Jan. 13, 2022 9:00 am9:50 am PST

Add to Calendar


Sidhanth Mohanty (UC Berkeley)


Calvin Lab Auditorium

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, & 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 Siqi Liu, Tselil Schramm, and Elizabeth Yang (