Events

Math and Data (MaD) Seminar: On The Fourier Coefficients of High-Dimensional Random Geometric Graphs

Speaker: Guy Bresler

Location: 60 Fifth Avenue, Room 7th floor open space, CDS

Date: Thursday, May 9, 2024

The random geometric graph RGG(n,d,p) on the d-dimensional sphere is formed by sampling n i.i.d. vectors uniformly and placing an edge between pairs of vertices i and j closer than some threshold chosen so that the marginal edge probability is p. We study the low-degree Fourier coefficients of this distribution and prove sharp bounds on them. Our main conceptual contribution is a novel probabilistic representation for the RGG: we prove that the dependence among edges can be localized to few fragile edges and then show how randomness in the remaining edges acts as a noise operator. The results have implications both for hypothesis testing and for computational-statistical gaps. Joint work with Kiril Bangachev. https://arxiv.org/abs/2402.12589