{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:18Z","timestamp":1781031438377,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1955351"],"award-info":[{"award-number":["CCF-1955351"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["DMS-2235451"],"award-info":[{"award-number":["DMS-2235451"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["EECS-2216970"],"award-info":[{"award-number":["EECS-2216970"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["MPS-NITMB-00005320"],"award-info":[{"award-number":["MPS-NITMB-00005320"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800885","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1777-1788","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Phylogenetic Reconstruction from Sampled Quartets"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-9720-1023","authenticated-orcid":false,"given":"Dionysis","family":"Arvanitakis","sequence":"first","affiliation":[{"name":"Northwestern University, Computer Science, Evanston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4475-4504","authenticated-orcid":false,"given":"Vaggos","family":"Chatziafratis","sequence":"additional","affiliation":[{"name":"University of California at Santa Cruz, Santa Cruz, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6515-8771","authenticated-orcid":false,"given":"Yiyuan","family":"Luo","sequence":"additional","affiliation":[{"name":"University of California at Santa Cruz, Santa Cruz, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9587-3677","authenticated-orcid":false,"given":"Konstantin","family":"Makarychev","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210030"},{"key":"e_1_3_2_1_2_1","volume-title":"12th International Conference on Learning Representations.","author":"Alon Noga","year":"2024","unstructured":"Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, and Grigory Yaroslavtsev. 2024. Optimal sample complexity of contrastive learning. In 12th International Conference on Learning Representations."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.30"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1041754"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/130941043"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796352"},{"key":"e_1_3_2_1_7_1","volume-title":"Spectral methods for learning multivariate latent tree structure. Advances in Neural Information Processing Systems, 24","author":"Anandkumar Animashree","year":"2011","unstructured":"Animashree Anandkumar, Kamalika Chaudhuri, Daniel J Hsu, Sham M Kakade, Le Song, and Tong Zhang. 2011. Spectral methods for learning multivariate latent tree structure. Advances in Neural Information Processing Systems, 24 (2011)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022873112823"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100271"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225140"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i6.25822"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syu087"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(86)90038-2"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.130"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1133"},{"key":"e_1_3_2_1_16_1","volume-title":"SODA","author":"Bryant David","year":"2000","unstructured":"David Bryant, John Tsang, Paul E Kearney, and Ming Li. 2000. Computing the quartet distance between evolutionary trees. In SODA 2000. 9, 285\u2013286."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.03.004"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00024"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49477-4_3"},{"key":"e_1_3_2_1_20_1","volume-title":"Hierarchical structure and the prediction of missing links in networks. Nature, 453, 7191","author":"Clauset Aaron","year":"2008","unstructured":"Aaron Clauset, Cristopher Moore, and Mark EJ Newman. 2008. Hierarchical structure and the prediction of missing links in networks. Nature, 453, 7191 (2008), 98\u2013101."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3321386"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2044-8317.1981.tb00626.x"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798342496"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055459"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2912074"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132540"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-009-0246-2"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316390"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.28"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320212"},{"key":"e_1_3_2_1_31_1","volume-title":"Inferring phylogenies. 2","author":"Felsenstein Joseph","unstructured":"Joseph Felsenstein. 2004. Inferring phylogenies. 2, Sinauer Associates Sunderland, MA."},{"key":"e_1_3_2_1_32_1","volume-title":"Foundations of comparison-based hierarchical clustering. Advances in Neural Information Processing Systems, 32","author":"Ghoshdastidar Debarghya","year":"2019","unstructured":"Debarghya Ghoshdastidar, Micha\u00ebl Perrot, and Ulrike von Luxburg. 2019. Foundations of comparison-based hierarchical clustering. Advances in Neural Information Processing Systems, 32 (2019)."},{"key":"e_1_3_2_1_33_1","volume-title":"Language phylogenies reveal expansion pulses and pauses in Pacific settlement. Science, 323, 5913","author":"Gray Russell D","year":"2009","unstructured":"Russell D Gray, Alexei J Drummond, and Simon J Greenhill. 2009. Language phylogenies reveal expansion pulses and pauses in Pacific settlement. Science, 323, 5913 (2009), 479\u2013483."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mbs.2006.11.005"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-015-0659-z"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756144"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_12"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90001-2"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118737.3118847"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925985"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743492"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361683"},{"key":"e_1_3_2_1_44_1","volume-title":"The 36th Annual Conference on Learning Theory. 1666\u20131729","author":"Kandiros Vardis","year":"2023","unstructured":"Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, and Davin Choo. 2023. Learning and testing latent-tree Ising models efficiently. In The 36th Annual Conference on Learning Theory. 1666\u20131729."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.11646\/zootaxa.1668.1.4"},{"key":"e_1_3_2_1_47_1","volume-title":"COLT","author":"Makarychev Konstantin","year":"2016","unstructured":"Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. 2016. Learning communities in the presence of errors. In COLT 2016. 1258\u20131291."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-03-03382-8"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-968X.2005.00149.x"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022605311895"},{"key":"e_1_3_2_1_51_1","volume-title":"Learning with noisy labels. Advances in Neural Information Processing Systems, 26","author":"Natarajan Nagarajan","year":"2013","unstructured":"Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. 2013. Learning with noisy labels. Advances in Neural Information Processing Systems, 26 (2013)."},{"key":"e_1_3_2_1_52_1","volume-title":"Poincar\u00e9 embeddings for learning hierarchical representations. Advances in Neural Information Processing Systems, 30","author":"Nickel Maximillian","year":"2017","unstructured":"Maximillian Nickel and Douwe Kiela. 2017. Poincar\u00e9 embeddings for learning hierarchical representations. Advances in Neural Information Processing Systems, 30 (2017)."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.026112"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0104008"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Charles Semple and Mike Steel. 2003. Phylogenetics. 24 Oxford University Press on Demand.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/2621980"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ympev.2011.06.021"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/110820555"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/11086964X"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a025664"},{"key":"e_1_3_2_1_63_1","volume-title":"High-dimensional probability: an introduction with applications in data science. 47","author":"Vershynin Roman","unstructured":"Roman Vershynin. 2018. High-dimensional probability: an introduction with applications in data science. 47, Cambridge University Press."},{"key":"e_1_3_2_1_64_1","volume-title":"ICML 2016. 2081","author":"Vikram Sharad","year":"2016","unstructured":"Sharad Vikram and Sanjoy Dasgupta. 2016. Interactive Bayesian hierarchical clustering. In ICML 2016. 2081\u20132090."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0035025"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500845"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0226281-1"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-3-1"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/mst040"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194274133"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800885","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800885","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:01:10Z","timestamp":1781028070000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800885"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":70,"alternative-id":["10.1145\/3798129.3800885","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800885","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}