On the Fourier Coefficients of High-Dimensional Random Geometric Graphs
April 19,
-
Speaker(s):Guy Bresler (MIT, EECS)
Lunch
Pizza will be served at 11:50 AM.
Abstract
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. Our main conceptual contribution is a novel strategy for bounding Fourier coefficients which we believe is more widely applicable to studying latent space distributions: 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. We apply the resulting bounds to: 1) Settle the low-degree polynomial complexity of distinguishing spherical and Gaussian random geometric graphs from Erdos-Renyi both in the case of observing a complete set of edges and in the non-adaptively chosen mask 2) Exhibit a statistical-computational gap for distinguishing 𝖱𝖦𝖦 and the planted coloring model [KVWX23] in a regime when 𝖱𝖦𝖦 is distinguishable from Erdos-Renyi. Joint work with Kiril Bangachev. https://arxiv.org/abs/2402.12589
