{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005008,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":64,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF-1940205"],"award-info":[{"award-number":["CCF-1940205"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718125","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"310-321","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7131-956X","authenticated-orcid":false,"given":"Kiril","family":"Bangachev","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6716-8827","authenticated-orcid":false,"given":"Guy","family":"Bresler","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2490670"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.017"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1483"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"497","author":"Bangachev Kiril","year":"2024","unstructured":"Kiril Bangachev and Guy Bresler. 2024. Detection of L_\u221e Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, Edomnton, Canada. 427\u2013497. https:\/\/proceedings.mlr.press\/v247\/bangachev24a\/bangachev24a.pdf"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649676"},{"key":"e_1_3_2_1_7_1","unstructured":"Kiril Bangachev and Guy Bresler. 2024. Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds Robust Testing and Enumeration. arxiv:2408.00995. arxiv:2408.00995"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21276"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.79"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000575"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AIHP1033"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42254-020-00264-4"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02808010"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2014.500"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21178"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-020-00998-3"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20633"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v16-967"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649761"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Quentin Duchemin and Yohann de Castro. 2022. Random Geometric Graph: Some recent developments and perspectives. https:\/\/doi.org\/10.48550\/ARXIV.2203.15351 10.48550\/ARXIV.2203.15351","DOI":"10.48550\/ARXIV.2203.15351"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-021-01092-y"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36020-7_13"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physd.2015.10.021"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-96-03732-X"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0109045"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000575"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/10-AAP693"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1214\/009117906000000278"},{"volume-title":"The random-cluster model","year":"2006","key":"e_1_3_2_1_32_1","unstructured":"Geoffrey. Grimmett. 2006. The random-cluster model. Springer, Berlin. isbn:3540328904 lccn:2006925087"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-015-0659-z"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139043816.012"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1198\/016214502388618906"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_1_39_1","unstructured":"Shuangping Li and Tselil Schramm. 2023. Spectral clustering in the Gaussian mixture block model. arxiv:2305.00979."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519989"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585106"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.3150\/22-BEJ1547"},{"key":"e_1_3_2_1_43_1","volume-title":"Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research","volume":"2481","author":"Mao Cheng","year":"2023","unstructured":"Cheng Mao, Alexander S. Wein, and Shenduo Zhang. 2023. Detection-Recovery Gap for Planted Dense Cycles. In Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research, Vol. 195). PMLR, Bangalore, India. 2440\u20132481. https:\/\/proceedings.mlr.press\/v195\/mao23a.html"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2024.3521305"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton63246.2024.10735333"},{"key":"e_1_3_2_1_46_1","first-page":"101","article-title":"Probabilistic Characteristics of Graphs with Large Connectivity","volume":"10","author":"Margulis G. A.","year":"1974","unstructured":"G. A. Margulis. 1974. Probabilistic Characteristics of Graphs with Large Connectivity. Probl. Peredachi Inf., 10 (1974), 101\u2013108. https:\/\/www.mathnet.ru\/links\/9d11aa4e75d1cd5224a5fe7c59b0c119\/ppi1034.pdf","journal-title":"Probl. Peredachi Inf."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2011.10.005"},{"key":"e_1_3_2_1_48_1","volume-title":"Social distance as a metric: a systematic introduction to smallest space analysis. Bonds of pluralism: The form and substance of urban social networks, 6","author":"McFarland David D","year":"1973","unstructured":"David D McFarland and Daniel J Brown. 1973. Social distance as a metric: a systematic introduction to smallest space analysis. Bonds of pluralism: The form and substance of urban social networks, 6 (1973), 2."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649761"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897548"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746603"},{"volume-title":"Analysis of Boolean Functions (1 ed.)","author":"O\u2019Donnell Ryan","key":"e_1_3_2_1_53_1","unstructured":"Ryan O\u2019Donnell. 2014. Analysis of Boolean Functions (1 ed.). Cambridge University Press, West Nyack. isbn:9781107471542"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1090\/bull"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2009.5400615"},{"key":"e_1_3_2_1_57_1","volume-title":"Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research","volume":"3509","author":"Mirabel","unstructured":"Mirabel E. Reid and Santosh S. Vempala. 2023. The k-Cap Process on Geometric Random Graphs. In Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research, Vol. 195). PMLR, Bangalore, India. 3469\u20133509. https:\/\/proceedings.mlr.press\/v195\/reid23a.html"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535742"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00537230"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2021.107593"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.078701"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.2307\/1994937"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:39:28Z","timestamp":1750693168000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":64,"alternative-id":["10.1145\/3717823.3718125","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718125","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}