On the Fourier Coefficients of High-Dimensional Random Geometric Graphs
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155580 |
| _version_ | 1811093808510664704 |
|---|---|
| author | Bangachev, Kiril Bresler, Guy |
| author_facet | Bangachev, Kiril Bresler, Guy |
| author_sort | Bangachev, Kiril |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T15:51:01Z |
| format | Article |
| id | mit-1721.1/155580 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:51:01Z |
| publishDate | 2024 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1555802024-09-09T04:17:57Z On the Fourier Coefficients of High-Dimensional Random Geometric Graphs Bangachev, Kiril Bresler, Guy STOC ’24, June 24–28, 2024, Vancouver, BC, Canada The random geometric graph RGG(n,Sd−1,p) is formed by sampling n i.i.d. vectors {Vi}i = 1n uniformly on Sd−1 and placing an edge between pairs of vertices i and j for which ⟨ Vi,Vj⟩ ≥ τdp, where τdp is such that the expected density is p. We study the low-degree Fourier coefficients of the distribution RGG(n,Sd−1,p) and its Gaussian analogue. Our main conceptual contribution is a novel two-step strategy for bounding Fourier coefficients which we believe is more widely applicable to studying latent space distributions. First, we localize the dependence among edges to few fragile edges. Second, we partition the space of latent vector configurations (Sd−1)⊗ n based on the set of fragile edges and on each subset of configurations, we define a noise operator acting independently on edges not incident (in an appropriate sense) to fragile edges. 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 M model recently introduced by Mardia, Verchand, and Wein; 2) Exhibit a statistical-computational gap for distinguishing RGG and a planted coloring model in a regime when RGG is distinguishable from ; 3) Reprove known bounds on the second eigenvalue of r 2024-07-10T18:53:28Z 2024-07-10T18:53:28Z 2024-06-10 2024-07-01T07:49:16Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155580 Bangachev, Kiril and Bresler, Guy. 2024. "On the Fourier Coefficients of High-Dimensional Random Geometric Graphs." PUBLISHER_CC en 10.1145/3618260.3649676 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Bangachev, Kiril Bresler, Guy On the Fourier Coefficients of High-Dimensional Random Geometric Graphs |
| title | On the Fourier Coefficients of High-Dimensional Random Geometric Graphs |
| title_full | On the Fourier Coefficients of High-Dimensional Random Geometric Graphs |
| title_fullStr | On the Fourier Coefficients of High-Dimensional Random Geometric Graphs |
| title_full_unstemmed | On the Fourier Coefficients of High-Dimensional Random Geometric Graphs |
| title_short | On the Fourier Coefficients of High-Dimensional Random Geometric Graphs |
| title_sort | on the fourier coefficients of high dimensional random geometric graphs |
| url | https://hdl.handle.net/1721.1/155580 |
| work_keys_str_mv | AT bangachevkiril onthefouriercoefficientsofhighdimensionalrandomgeometricgraphs AT breslerguy onthefouriercoefficientsofhighdimensionalrandomgeometricgraphs |