Algorithms & Randomness Center (ARC)
Elizabeth Yang (Berkeley)
January 23, 2023
Pettit Microelectronics Building 102 A&B - 3:30 pm
Title: Testing thresholds for high-dimensional random geometric graphs
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 each 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}. Furthermore, 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:
- Sharp estimates for the area of the intersection of a random sphere cap with an arbitrary subset of the sphere, which are obtained using optimal transport maps and entropy-transport inequalities on the unit sphere.
- Analyzing the Belief Propagation algorithm to characterize the distributions of (subsets of) the random vectors conditioned on producing a particular graph.
Based on joint work with Siqi Liu, Sidhanth Mohanty, and Tselil Schramm.
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
