{"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":1750695005587,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","funder":[{"name":"National Science Foundation","award":["2008305,2402284,2152413"],"award-info":[{"award-number":["2008305,2402284,2152413"]}]},{"name":"Natural Sciences and Engineering Research Council of Canada","award":["RGPIN-2024-04290"],"award-info":[{"award-number":["RGPIN-2024-04290"]}]},{"name":"Alfred P. Sloan Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"name":"University of Waterloo","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Simons Foundation","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718194","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"417-428","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8914-5995","authenticated-orcid":false,"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2601-1689","authenticated-orcid":false,"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9737-2406","authenticated-orcid":false,"given":"Aaron","family":"Putterman","sequence":"additional","affiliation":[{"name":"Harvard University, 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","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, Francis R. Bach and David M. Blei (Eds.) (JMLR Workshop and Conference Proceedings","volume":"2246","author":"Ahn Kook Jin","year":"2015","unstructured":"Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. 2015. Correlation Clustering in Data Streams. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, Francis R. Bach and David M. Blei (Eds.) (JMLR Workshop and Conference Proceedings, Vol. 37). JMLR.org, 2237\u20132246."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1137\/1.9781611973099.40"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1145\/2213556.2213560"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1145\/1411509.1411513"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1137\/1.9781611974331.ch93"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1137\/1.9781611977585.CH20"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.4230\/LIPICS.ITCS.2022.10"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.4230\/LIPICS.ICALP.2019.18"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/3125644"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1109\/FOCS54457.2022.00074"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1137\/1.9781611977554.ch33"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/3498334"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1145\/237814.237827"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.4230\/LIPICS.ITCS.2024.12"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1137\/1.9781611978322.97"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1145\/3406325.3451113"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1137\/1.9781611977912.101"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1145\/3618260.3649749"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.4230\/LIPICS.ITCS.2022.37"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1109\/SFCS.2003.1238225"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1145\/2746539.2746604"},{"key":"e_1_3_2_1_22_1","volume-title":"Communication-Optimal Distributed Clustering. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016","author":"Chen Jiecao","year":"2016","unstructured":"Jiecao Chen, He Sun, David P. Woodruff, and Qin Zhang. 2016. Communication-Optimal Distributed Clustering. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (Eds.). 3720\u20133728."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1109\/FOCS54457.2022.00052"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1145\/2623330.2623743"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021","volume":"2078","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 2021, 18-24 July 2021, Virtual Event, Marina Meila and Tong Zhang (Eds.) (Proceedings of Machine Learning Research, Vol. 139). PMLR, 2069\u20132078."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1109\/FOCS57990.2023.00065"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1109\/FOCS54457.2022.00068"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1145\/3618260.3649712"},{"key":"e_1_3_2_1_29_1","volume-title":"Forty-first International Conference on Machine Learning, ICML 2024","author":"Dalirrooyfard Mina","year":"2024","unstructured":"Mina Dalirrooyfard, Konstantin Makarychev, and Slobodan Mitrovic. 2024. Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1016\/J.TCS.2006.05.008"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1007\/978-3-642-97881-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1145\/2090236.2090266"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1109\/FOCS.2014.66"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1109\/FOCS.2014.66"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.5555\/313559.313605"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1137\/1.9781611973075.76"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1109\/FOCS61266.2024.00105"},{"key":"e_1_3_2_1_38_1","volume-title":"Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023","author":"Makarychev Konstantin","year":"2023","unstructured":"Konstantin Makarychev and Sayak Chakrabarty. 2023. Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (Eds.)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1007\/978-3-662-48054-0_39"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1145\/3232536"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1137\/080734029"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.1137\/08074489X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_43_1","DOI":"10.1214\/22-STS852"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1609\/aaai.v33i01.33015957"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '25","name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia"},"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.3718194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:06Z","timestamp":1750693386000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":44,"alternative-id":["10.1145\/3717823.3718194","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718194","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"}}]}}