{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T17:15:29Z","timestamp":1772730929441,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["DMS-2053333, DMS-2210734, CCF-1900507, CCF- 1651588, CCF-1856424, CCF-2144593"],"award-info":[{"award-number":["DMS-2053333, DMS-2210734, CCF-1900507, CCF- 1651588, CCF-1856424, CCF-2144593"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","award":["Sloan Research Fellowship"],"award-info":[{"award-number":["Sloan Research Fellowship"]}],"id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585156","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1345-1356","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Random Graph Matching at Otter\u2019s Threshold via Counting Chandeliers"],"prefix":"10.1145","author":[{"given":"Cheng","family":"Mao","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, USA"}]},{"given":"Yihong","family":"Wu","sequence":"additional","affiliation":[{"name":"Yale University, USA"}]},{"given":"Jiaming","family":"Xu","sequence":"additional","affiliation":[{"name":"Duke University, USA"}]},{"given":"Sophie H.","family":"Yu","sequence":"additional","affiliation":[{"name":"Duke University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1401651112"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36136-7_40"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"#cr-split#-e_1_3_2_1_6_1.1","unstructured":"Boaz Barak Chi-Ning Chou Zhixian Lei Tselil Schramm and Yueqi Sheng. 2019. (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs. In Advances in Neural Information Processing Systems. 9186-9194. https:\/\/doi.org\/10.48550\/arXiv.1805.02349 10.48550\/arXiv.1805.02349"},{"key":"#cr-split#-e_1_3_2_1_6_1.2","unstructured":"Boaz Barak Chi-Ning Chou Zhixian Lei Tselil Schramm and Yueqi Sheng. 2019. (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs. In Advances in Neural Information Processing Systems. 9186-9194. https:\/\/doi.org\/10.48550\/arXiv.1805.02349"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209055"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73545-X"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20633"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0303-9_27"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210015"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2964791.2901460"},{"key":"#cr-split#-e_1_3_2_1_13_1.1","unstructured":"Daniel Cullina and Negar Kiyavash. 2017. Exact alignment recovery for correlated Erd\u0151s-R\u00e9nyi graphs. arXiv 1711.06783 https:\/\/doi.org\/10.48550\/arXiv.1711.06783 10.48550\/arXiv.1711.06783"},{"key":"#cr-split#-e_1_3_2_1_13_1.2","unstructured":"Daniel Cullina and Negar Kiyavash. 2017. Exact alignment recovery for correlated Erd\u0151s-R\u00e9nyi graphs. arXiv 1711.06783 https:\/\/doi.org\/10.48550\/arXiv.1711.06783"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366702"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.01.002"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341617.3326151"},{"key":"#cr-split#-e_1_3_2_1_17_1.1","unstructured":"Jian Ding and Hang Du. 2022. Matching recovery threshold for correlated random graphs. arXiv preprint arXiv:2205.14650 https:\/\/doi.org\/10.48550\/arXiv.2205.14650 10.48550\/arXiv.2205.14650"},{"key":"#cr-split#-e_1_3_2_1_17_1.2","unstructured":"Jian Ding and Hang Du. 2022. Matching recovery threshold for correlated random graphs. arXiv preprint arXiv:2205.14650 https:\/\/doi.org\/10.48550\/arXiv.2205.14650"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-020-00997-4"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-022-09570-y"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-022-09575-7"},{"key":"e_1_3_2_1_21_1","volume-title":"Conference on Learning Theory. 1633\u20131665","author":"Ganassali Luca","year":"2020","unstructured":"Luca Ganassali and Laurent Massouli\u00e9 . 2020 . From tree matching to sparse graph alignment . In Conference on Learning Theory. 1633\u20131665 . https:\/\/doi.org\/10.48550\/arXiv.2002.01258 10.48550\/arXiv.2002.01258 Luca Ganassali and Laurent Massouli\u00e9. 2020. From tree matching to sparse graph alignment. In Conference on Learning Theory. 1633\u20131665. https:\/\/doi.org\/10.48550\/arXiv.2002.01258"},{"key":"e_1_3_2_1_22_1","volume-title":"Conference on Learning Theory. 2080\u20132102","author":"Ganassali Luca","year":"2021","unstructured":"Luca Ganassali , Laurent Massouli\u00e9 , and Marc Lelarge . 2021 . Impossibility of partial recovery in the graph alignment problem . In Conference on Learning Theory. 2080\u20132102 . https:\/\/doi.org\/10.48550\/arXiv.2102.02685 10.48550\/arXiv.2102.02685 Luca Ganassali, Laurent Massouli\u00e9, and Marc Lelarge. 2021. Impossibility of partial recovery in the graph alignment problem. In Conference on Learning Theory. 2080\u20132102. https:\/\/doi.org\/10.48550\/arXiv.2102.02685"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.74"},{"key":"#cr-split#-e_1_3_2_1_24_1.1","unstructured":"Luca Ganassali Laurent Massouli\u00e9 and Guilhem Semerjian. 2022. Statistical limits of correlation detection in trees. arXiv preprint arXiv:2209.13723 https:\/\/doi.org\/10.48550\/arXiv.2209.13723 10.48550\/arXiv.2209.13723"},{"key":"#cr-split#-e_1_3_2_1_24_1.2","unstructured":"Luca Ganassali Laurent Massouli\u00e9 and Guilhem Semerjian. 2022. Statistical limits of correlation detection in trees. arXiv preprint arXiv:2209.13723 https:\/\/doi.org\/10.48550\/arXiv.2209.13723"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2355"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1869.70.185"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2424894"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_50"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of Thirty Fourth Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"3329","author":"Mao Cheng","year":"2021","unstructured":"Cheng Mao , Mark Rudelson , and Konstantin Tikhomirov . 2021 . Random Graph Matching with Improved Noise Robustness . In Proceedings of Thirty Fourth Conference on Learning Theory (Proceedings of Machine Learning Research , Vol. 134). 3296\u2013 3329 . https:\/\/doi.org\/10.48550\/arXiv.2101.11783 10.48550\/arXiv.2101.11783 Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. 2021. Random Graph Matching with Improved Noise Robustness. In Proceedings of Thirty Fourth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 134). 3296\u20133329. https:\/\/doi.org\/10.48550\/arXiv.2101.11783"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-022-01184-3"},{"key":"#cr-split#-e_1_3_2_1_32_1.1","unstructured":"Cheng Mao Yihong Wu Jiaming Xu and Sophie H Yu. 2021. Testing network correlation efficiently via counting trees. arXiv preprint arXiv:2110.11816 https:\/\/doi.org\/10.48550\/arXiv.2110.11816 10.48550\/arXiv.2110.11816"},{"key":"#cr-split#-e_1_3_2_1_32_1.2","unstructured":"Cheng Mao Yihong Wu Jiaming Xu and Sophie H Yu. 2021. Testing network correlation efficiently via counting trees. arXiv preprint arXiv:2110.11816 https:\/\/doi.org\/10.48550\/arXiv.2110.11816"},{"key":"#cr-split#-e_1_3_2_1_33_1.1","unstructured":"Cheng Mao Yihong Wu Jiaming Xu and Sophie H Yu. 2022. Random graph matching at Otter's threshold via counting chandeliers. arXiv preprint arXiv:2209.12313 https:\/\/doi.org\/10.48550\/arXiv.2209.12313 10.48550\/arXiv.2209.12313"},{"key":"#cr-split#-e_1_3_2_1_33_1.2","doi-asserted-by":"crossref","unstructured":"Cheng Mao Yihong Wu Jiaming Xu and Sophie H Yu. 2022. Random graph matching at Otter's threshold via counting chandeliers. arXiv preprint arXiv:2209.12313 https:\/\/doi.org\/10.48550\/arXiv.2209.12313","DOI":"10.1145\/3564246.3585156"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-014-0576-6"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.33"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.AofA.2022.16"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969046"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020596"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/ac70d2"},{"key":"e_1_3_2_1_41_1","volume-title":"Kombinatorische anzahlbestimmungen f\u00fcr gruppen, graphen und chemische verbindungen. Acta mathematica, 68","author":"P\u00f3lya George","year":"1937","unstructured":"George P\u00f3lya . 1937. Kombinatorische anzahlbestimmungen f\u00fcr gruppen, graphen und chemische verbindungen. Acta mathematica, 68 ( 1937 ), 145\u2013254. George P\u00f3lya. 1937. Kombinatorische anzahlbestimmungen f\u00fcr gruppen, graphen und chemische verbindungen. Acta mathematica, 68 (1937), 145\u2013254."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3433652"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.6778"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3169005"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512952"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.245"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585156","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585156","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":53,"alternative-id":["10.1145\/3564246.3585156","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585156","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}