Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs

Explore the intricacies of distinguishing Erdős-Rényi graphs from random geometric graphs in this 56-minute lecture by Siqi Liu from UC Berkeley. Delve into structural results that improve upon previous bounds and nearly resolve a conjecture by Bubeck, Ding, Eldan, and Rácz. Examine key proof ideas, including the analysis of the Belief Propagation algorithm and sharp estimates for sphere cap intersections using optimal transport maps and entropy-transport inequalities. Gain insights into statistical indistinguishability thresholds for various probability ranges and understand the implications of this joint work with Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang on high-dimensional sparse random geometric graphs.

Testing Thresholds for High-dimensional Sparse Random Geometric Graphs