Testing Thresholds for High-dimensional Sparse Random Geometric Graphs

on YouTube ↗56m

" summary

Main result: when p = c/n the random geometric graph Geo_d(n,p) becomes statistically indistinguishable from G(n,p) once d ≥ poly(log n), with total variation distance tending to 0, closing the gap from prior requirements of d ≫ n^{3/2} and resolving a conjecture up to logs; methods combine centered triangle counting lower bounds with a high‑precision analysis of neighborhood distributions via Belief Propagation and sharp sphere‑cap intersection estimates using optimal transport and entropy‑transport inequalities.

AI-written summary · about

" chapters (8)

1. 0:00Testing thresholds in RGG
2. 3:21Motivation for studying random geometric graphs
3. 7:15RGG vs Erdős–Rényi
4. 13:54Known distinguishability results
5. 20:39Proof strategy for indistinguishability
6. 33:22Neighborhood areas on sphere
7. 41:02Conditioning on graph structure
8. 54:36Results and open questions

" related talks

• 24mRobust Parameter Estimation For Random GraphsJayadev Acharya · Rigorous Evidence for Information-Computation Trade-offs
• 40mTesting Correlation of Unlabeled Random GraphsJiaming Xu · Computational Phase Transitions (Simons Institute, 2020)
• 49mRecent Advances in Counting Sparse GraphsSourav Chatterjee · Random Instances and Phase Transitions (Simons Institute, 2016)
• 42mBootstrap Percolation on Random GraphsMihyun Kang · Random Instances and Phase Transitions (Simons Institute, 2016)
• 45mThe lower tail: Poisson approximation revisitedLutz Warnke · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 34mAlgorithmic High-Dimensional Geometry IAlex Andoni · Big Data Boot Camp 2013
• 01h 03mHigh Dimensional Geometry and Concentration IISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 34mInformation/Computation Gaps in Heavy-Tailed StatisticsSam Hopkins · Computational Phase Transitions (Simons Institute, 2020)