Testing thresholds for high-dimensional sparse random geometric graphs. (English) Zbl 07774369
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 672-677 (2022).
MSC:
| 68Qxx | Theory of computing |
Keywords:
belief propagation; cavity method; optimal transport; random geometric graphs; random graphsReferences:
| [1] | Noga Alon and Joel H Spencer. 2004. The probabilistic method. John Wiley & Sons. https://doi.org/10.1002/0471722154 10.1002/0471722154 · Zbl 1333.05001 |
| [2] | Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. 2010. Detecting high log-densities: an O(n^1/4) approximation for densest k-subgraph. In Proceedings of the forty-second ACM symposium on Theory of computing. 201-210. https://doi.org/10.1145/1806689.1806719 10.1145/1806689.1806719 · Zbl 1293.05200 |
| [3] | Matthew Brennan, Guy Bresler, and Brice Huang. 2021. De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions. arXiv preprint arXiv:2103.14011. |
| [4] | Matthew Brennan, Guy Bresler, and Dheeraj Nagaraj. 2020. Phase transitions for detecting latent geometry in random graphs. Probability Theory and Related Fields, 178, 3 (2020), 1215-1289. https://doi.org/10.1007/s00440-020-00998-3 10.1007/s00440-020-00998-3 · Zbl 1468.60011 |
| [5] | Sébastien Bubeck, Jian Ding, Ronen Eldan, and Miklós Z Rácz. 2016. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms, 49, 3 (2016), 503-532. https://doi.org/10.1002/rsa.20633 10.1002/rsa.20633 · Zbl 1349.05315 |
| [6] | Sébastien Bubeck and Shirshendu Ganguly. 2018. Entropic CLT and phase transition in high-dimensional Wishart matrices. International Mathematics Research Notices, 2018, 2 (2018), 588-606. https://doi.org/10.1093/imrn/rnw243 10.1093/imrn/rnw243 · Zbl 1407.82024 |
| [7] | Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová. 2018. Information-theoretic thresholds from the cavity method. Advances in Mathematics, 333 (2018), 694-795. https://doi.org/10.1016/j.aim.2018.05.029 10.1016/j.aim.2018.05.029 · Zbl 1397.82013 |
| [8] | Daniel Cullina and Negar Kiyavash. 2016. Improved achievability and converse bounds for erdos-rényi graph matching. ACM SIGMETRICS Performance Evaluation Review, 44, 1 (2016), 63-72. https://doi.org/10.1145/2896377.2901460 10.1145/2896377.2901460 · Zbl 1359.94245 |
| [9] | Amir Dembo, Andrea Montanari, Allan Sly, and Nike Sun. 2014. The replica symmetric solution for Potts models on d-regular graphs. Communications in Mathematical Physics, 327, 2 (2014), 551-575. https://doi.org/10.1007/s00220-014-1956-6 10.1007/s00220-014-1956-6 · Zbl 1288.82009 |
| [10] | Luc Devroye, András György, Gábor Lugosi, and Frederic Udina. 2011. High-dimensional random geometric graphs and their clique number. Electronic Journal of Probability, 16 (2011), 2481-2508. https://doi.org/10.1214/EJP.v16-967 10.1214/EJP.v16-967 · Zbl 1244.05200 |
| [11] | Martin Dyer, Alistair Sinclair, Eric Vigoda, and Dror Weitz. 2004. Mixing in time and space for lattice spin systems: A combinatorial view. Random Structures & Algorithms, 24, 4 (2004), 461-479. https://doi.org/10.1002/rsa.20004 10.1002/rsa.20004 · Zbl 1126.82021 |
| [12] | Ronen Eldan and Dan Mikulincer. 2020. Information and dimensionality of anisotropic random geometric graphs. In Geometric Aspects of Functional Analysis. Springer, 273-324. https://doi.org/10.1007/978-3-030-36020-7_13 10.1007/978-3-030-36020-7_13 · Zbl 1453.05118 |
| [13] | Paul Erdős and Alfréd Rényi. 1959. On random graphs. I. Publicationes Mathematicae. · Zbl 0092.15705 |
| [14] | Uriel Feige. 2002. Relations between average case complexity and approximation complexity. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. 534-543. https://doi.org/10.1145/509907.509985 10.1145/509907.509985 · Zbl 1192.68358 |
| [15] | Uriel Feige and Joe Kilian. 2001. Heuristics for semirandom graph problems. J. Comput. System Sci., 63, 4 (2001), 639-671. https://doi.org/10.1006/jcss.2001.1773 10.1006/jcss.2001.1773 · Zbl 1006.68103 |
| [16] | Uriel Feige, Michael Langberg, and Gideon Schechtman. 2004. Graphs with tiny vector chromatic numbers and huge chromatic numbers. SIAM J. Comput., 33, 6 (2004), 1338-1368. https://doi.org/10.1109/SFCS.2002.1181951 10.1109/SFCS.2002.1181951 · Zbl 1105.68088 |
| [17] | Uriel Feige and Gideon Schechtman. 2002. On the optimality of the random hyperplane rounding technique for MAX CUT. Random Structures & Algorithms, 20, 3 (2002), 403-440. https://doi.org/10.1002/rsa.10036 10.1002/rsa.10036 · Zbl 1005.90052 |
| [18] | David Gamarnik, Dmitriy Katz, and Sidhant Misra. 2015. Strong spatial mixing of list coloring of graphs. Random Structures & Algorithms, 46, 4 (2015), 599-613. https://doi.org/10.1002/rsa.20518 10.1002/rsa.20518 · Zbl 1317.05054 |
| [19] | Dima Grigoriev. 2001. Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259, 1-2 (2001), 613-622. https://doi.org/10.1016/S0304-3975(00)00157-2 10.1016/S0304-3975(00)00157-2 · Zbl 0974.68192 |
| [20] | Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. 1983. Stochastic blockmodels: First steps. Social networks, 5, 2 (1983), 109-137. https://doi.org/10.1016/0378-8733(83)90021-7 10.1016/0378-8733(83)90021-7 |
| [21] | Mark Jerrum. 1992. Large cliques elude the Metropolis process. Random Structures & Algorithms, 3, 4 (1992), 347-359. https://doi.org/10.1002/rsa.3240030402 10.1002/rsa.3240030402 · Zbl 0754.60018 |
| [22] | Tiefeng Jiang and Danning Li. 2015. Approximation of rectangular beta-Laguerre ensembles and large deviations. Journal of Theoretical Probability, 28, 3 (2015), 804-847. https://doi.org/10.1007/S10959-013-0519-7 10.1007/S10959-013-0519-7 · Zbl 1333.15032 |
| [23] | Subhash Khot, Madhur Tulsiani, and Pratik Worah. 2014. A characterization of strong approximation resistance. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 634-643. https://doi.org/10.1145/2591796.2591817 10.1145/2591796.2591817 · Zbl 1315.68154 |
| [24] | Suqi Liu and Miklós Z Rácz. 2021. Phase transition in noisy high-dimensional random geometric graphs. arXiv preprint arXiv:2103.15249. · Zbl 1515.05160 |
| [25] | Marc Mézard and Giorgio Parisi. 2003. The cavity method at zero temperature. Journal of Statistical Physics, 111, 1 (2003), 1-34. https://doi.org/10.1023/A:1022221005097 10.1023/A:1022221005097 · Zbl 1014.82032 |
| [26] | Hidetoshi Nishimori. 1981. Internal energy, specific heat and correlation function of the bond-random Ising model. Progress of Theoretical Physics, 66, 4 (1981), 1169-1181. https://doi.org/10.1143/PTP.66.1169 10.1143/PTP.66.1169 |
| [27] | Dmitry Panchenko. 2009. Cavity method in the spherical SK model. In Annales de l’IHP Probabilités et statistiques. 45, 1020-1047. https://doi.org/10.1214/08-AIHP193 10.1214/08-AIHP193 · Zbl 1193.82021 |
| [28] | Dmitry Panchenko. 2013. The Sherrington-Kirkpatrick model. Springer Science & Business Media. https://doi.org/10.1007/978-1-4614-6289-7 10.1007/978-1-4614-6289-7 · Zbl 1266.82005 |
| [29] | Mathew Penrose. 2003. Random geometric graphs. 5, Oxford university press. https://doi.org/10.1093/acprof:oso/9780198506263.001.0001 10.1093/acprof:oso/9780198506263.001.0001 · Zbl 1029.60007 |
| [30] | Miklós Z Rácz and Jacob Richey. 2019. A smooth transition from Wishart to GOE. Journal of Theoretical Probability, 32, 2 (2019), 898-906. https://doi.org/10.1007/s10959-018-0808-2 10.1007/s10959-018-0808-2 · Zbl 1447.60027 |
| [31] | Benjamin Rossman. 2008. On the constant-depth complexity of k-clique. In Proceedings of the fortieth annual ACM symposium on Theory of computing. 721-730. https://doi.org/10.1145/1374376.1374480 10.1145/1374376.1374480 · Zbl 1231.68154 |
| [32] | Grant Schoenebeck. 2008. Linear level Lasserre lower bounds for certain k-CSPs. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 593-602. https://doi.org/10.1109/FOCS.2008.74 10.1109/FOCS.2008.74 |
| [33] | Michel Talagrand. 2003. Spin glasses: a challenge for mathematicians: cavity and mean field models. 46, Springer Science & Business Media. https://doi.org/10.1017/S096354830421656X 10.1017/S096354830421656X · Zbl 1033.82002 |
| [34] | Cédric Villani. 2008. Optimal transport: old and new. 338, Springer Science & Business Media. https://doi.org/10.1007/978-3-540-71050-9 10.1007/978-3-540-71050-9 · Zbl 1156.53003 |
| [35] | Mark Walters. 2011. Random geometric graphs. Surveys in combinatorics, 392 (2011), 365-402. https://doi.org/10.1017/CBO9781139004114.009 10.1017/CBO9781139004114.009 · Zbl 1244.05206 |
| [36] | Dror Weitz. 2006. Counting independent sets up to the tree threshold. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. 140-149. https://doi.org/10.1145/1132516.1132538 10.1145/1132516.1132538 · Zbl 1301.68276 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
