{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004100,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","funder":[{"name":"NSF","award":["2236669"],"award-info":[{"award-number":["2236669"]}]},{"name":"VILLUM Foundation Grant","award":["54451"],"award-info":[{"award-number":["54451"]}]},{"name":"Basic Algorithms Research Copenhagen (BARC)","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Independent Research Fund Denmark under the Sapere Aude research career programme","award":["1054-00032B"],"award-info":[{"award-number":["1054-00032B"]}]},{"name":"Swiss National Science Foundation","award":["200021-184656"],"award-info":[{"award-number":["200021-184656"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718181","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"1154-1165","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving the Correlation Cluster LP in Sublinear Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4961-763X","authenticated-orcid":false,"given":"Nairen","family":"Cao","sequence":"first","affiliation":[{"name":"New York University, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0779-8962","authenticated-orcid":false,"given":"Vincent","family":"Cohen-Addad","sequence":"additional","affiliation":[{"name":"Google Research, Grenoble, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1454-7587","authenticated-orcid":false,"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9140-9415","authenticated-orcid":false,"given":"Shi","family":"Li","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8835-0926","authenticated-orcid":false,"given":"David Rasmussen","family":"Lolck","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7353-7734","authenticated-orcid":false,"given":"Alantha","family":"Newman","sequence":"additional","affiliation":[{"name":"University Grenoble Alpes, Grenoble, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5237-1709","authenticated-orcid":false,"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8241-536X","authenticated-orcid":false,"given":"Lukas","family":"Vogl","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9439-8942","authenticated-orcid":false,"given":"Shuyi","family":"Yan","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3149-7799","authenticated-orcid":false,"given":"Hanwen","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498759.1498824"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.43"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 13th Conference on Innovations in Theoretical Computer Science (ITCS) (LIPIcs","volume":"20","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi and Chen Wang. 2022. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. In Proceedings of the 13th Conference on Innovations in Theoretical Computer Science (ITCS) (LIPIcs, Vol. 215). 10:1\u201310:20."},{"key":"e_1_3_2_1_6_1","volume-title":"Correlation clustering. Machine learning, 56, 1","author":"Bansal Nikhil","year":"2004","unstructured":"Nikhil Bansal, Avrim Blum, and Shuchi Chawla. 2004. Correlation clustering. Machine learning, 56, 1 (2004), 89\u2013113."},{"key":"e_1_3_2_1_7_1","unstructured":"Soheil Behnezhad Moses Charikar Vincent Cohen-Addad Alma Ghafari and Weiyun Ma. 2024. Fully Dynamic Correlation Clustering: Breaking 3-Approximation. arXiv preprint arXiv:2404.06797."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00074"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch33"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0522-9"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649749"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.143"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367549"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC). 219\u2013228","author":"Chawla Shuchi","year":"2015","unstructured":"Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. 2015. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC). 219\u2013228."},{"key":"e_1_3_2_1_16_1","unstructured":"Yudong Chen Sujay Sanghavi and Huan Xu. 2012. Clustering sparse graphs. In Advances in Neural Information Processing Systems (Neurips). 2204\u20132212."},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning (ICML). 2069\u20132078","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub Tarnawski. 2021. Correlation Clustering in Constant Many Parallel Rounds. In Proceedings of the 38th International Conference on Machine Learning (ICML). 2069\u20132078."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00065"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00068"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649712"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 41st International Conference on Machine Learning (ICML\u201924)","author":"Dalirrooyfard Mina","year":"2024","unstructured":"Mina Dalirrooyfard, Konstantin Makarychev, and Slobodan Mitrovi\u0107. 2024. Pruned Pivot: correlation clustering algorithm for dynamic, parallel, and local computation models. In Proceedings of the 41st International Conference on Machine Learning (ICML\u201924). JMLR.org, Article 394, 22 pages."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.78"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2303095"},{"key":"e_1_3_2_1_24_1","volume-title":"Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!. Advances in Neural Information Processing Systems (NeurIPS), 36","author":"Makarychev Konstantin","year":"2024","unstructured":"Konstantin Makarychev and Sayak Chakrabarty. 2024. Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!. Advances in Neural Information Processing Systems (NeurIPS), 36 (2024)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of 35th International Conference on Machine Learning (ICML). 5596\u20135605","author":"Yaroslavtsev Grigory","year":"2018","unstructured":"Grigory Yaroslavtsev and Adithya Vadapalli. 2018. Massively parallel algorithms and hardness for single-linkage clustering under \u2113 _p-distances. In Proceedings of 35th International Conference on Machine Learning (ICML). 5596\u20135605."}],"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.3718181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:42:20Z","timestamp":1750693340000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":26,"alternative-id":["10.1145\/3717823.3718181","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718181","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"}}]}}