{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:16:57Z","timestamp":1755998217506,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,4,20]],"date-time":"2020-04-20T00:00:00Z","timestamp":1587340800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,4,20]]},"DOI":"10.1145\/3366423.3380045","type":"proceedings-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T08:11:44Z","timestamp":1588579904000},"page":"2831-2834","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Clustering with a faulty oracle"],"prefix":"10.1145","author":[{"given":"Kasper","family":"Green Larsen","sequence":"first","affiliation":[{"name":"Aarhus University"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[{"name":"Harvard University"}]},{"given":"Charalampos","family":"Tsourakakis","sequence":"additional","affiliation":[{"name":"Boston University"}]}],"member":"320","published-online":{"date-parts":[[2020,4,20]]},"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\/0095-8956(85)90092-9"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027\u20131035","author":"Arthur David","year":"2007","unstructured":"David Arthur and Sergei Vassilvitskii . 2007 . k-means++: The advantages of careful seeding . In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027\u20131035 . David Arthur and Sergei Vassilvitskii. 2007. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027\u20131035."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2180912.2180915"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_3_2_1_6_1","volume-title":"KDD.","author":"Bonchi Francesco","year":"1972","unstructured":"Francesco Bonchi , David Garcia-Soriano , and Edo Liberty . 2014. Correlation clustering: from theory to practice .. In KDD. 1972 . Francesco Bonchi, David Garcia-Soriano, and Edo Liberty. 2014. Correlation clustering: from theory to practice.. In KDD. 1972."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_52"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347112"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_3_2_1_10_1","unstructured":"Nicolo Cesa-Bianchi Claudio Gentile Fabio Vitale Giovanni Zappella 2012. A Correlation Clustering Approach to Link Classification in Signed Networks.. In COLT. 34\u20131.  Nicolo Cesa-Bianchi Claudio Gentile Fabio Vitale Giovanni Zappella 2012. A Correlation Clustering Approach to Link Classification in Signed Networks.. In COLT. 34\u20131."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1828"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21760"},{"key":"e_1_3_2_1_13_1","volume-title":"Clustering partially observed graphs via convex optimization.Journal of Machine Learning Research 15, 1","author":"Chen Yudong","year":"2014","unstructured":"Yudong Chen , Ali Jalali , Sujay Sanghavi , and Huan Xu. 2014. Clustering partially observed graphs via convex optimization.Journal of Machine Learning Research 15, 1 ( 2014 ), 2213\u20132238. Yudong Chen, Ali Jalali, Sujay Sanghavi, and Huan Xu. 2014. Clustering partially observed graphs via convex optimization.Journal of Machine Learning Research 15, 1 (2014), 2213\u20132238."},{"key":"e_1_3_2_1_14_1","unstructured":"Yudong Chen Sujay Sanghavi and Huan Xu. 2012. Clustering sparse graphs. In Advances in neural information processing systems. 2204\u20132212.  Yudong Chen Sujay Sanghavi and Huan Xu. 2012. Clustering sparse graphs. In Advances in neural information processing systems. 2204\u20132212."},{"key":"e_1_3_2_1_15_1","volume-title":"Prediction and clustering in signed networks: a local to global perspective.Journal of Machine Learning Research 15, 1","author":"Chiang Kai-Yang","year":"2014","unstructured":"Kai-Yang Chiang , Cho-Jui Hsieh , Nagarajan Natarajan , Inderjit\u00a0 S Dhillon , and Ambuj Tewari . 2014. Prediction and clustering in signed networks: a local to global perspective.Journal of Machine Learning Research 15, 1 ( 2014 ), 1177\u20131213. Kai-Yang Chiang, Cho-Jui Hsieh, Nagarajan Natarajan, Inderjit\u00a0S Dhillon, and Ambuj Tewari. 2014. Prediction and clustering in signed networks: a local to global perspective.Journal of Machine Learning Research 15, 1 (2014), 1177\u20131213."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Kasper Green\u00a0Larsen Michael Mitzenmacher and Charalampos\u00a0E Tsourakakis. 2019. Optimal Learning of Joint Alignments with a Faulty Oracle. arXiv preprint arXiv:1909.09912(2019).  Kasper Green\u00a0Larsen Michael Mitzenmacher and Charalampos\u00a0E Tsourakakis. 2019. Optimal Learning of Joint Alignments with a Faulty Oracle. arXiv preprint arXiv:1909.09912(2019).","DOI":"10.1109\/ITA50056.2020.9244966"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875569"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2546280"},{"key":"e_1_3_2_1_19_1","volume-title":"Data clustering: 50 years beyond K-means. Pattern recognition letters 31, 8","author":"Jain K","year":"2010","unstructured":"Anil\u00a0 K Jain . 2010. Data clustering: 50 years beyond K-means. Pattern recognition letters 31, 8 ( 2010 ), 651\u2013666. Anil\u00a0K Jain. 2010. Data clustering: 50 years beyond K-means. Pattern recognition letters 31, 8 (2010), 651\u2013666."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772756"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1753326.1753532"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the Conference on Learning Theory (COLT), Vol.\u00a06. 12","author":"Makarychev Konstantin","year":"2015","unstructured":"Konstantin Makarychev , Yury Makarychev , and Aravindan Vijayaraghavan . 2015 . Correlation clustering with noisy partial information . In Proceedings of the Conference on Learning Theory (COLT), Vol.\u00a06. 12 . Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. 2015. Correlation clustering with noisy partial information. In Proceedings of the Conference on Learning Theory (COLT), Vol.\u00a06. 12."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873659"},{"key":"e_1_3_2_1_24_1","unstructured":"Arya Mazumdar and Barna Saha. 2016. Clustering Via Crowdsourcing. arXiv preprint arXiv:1604.01839(2016).  Arya Mazumdar and Barna Saha. 2016. Clustering Via Crowdsourcing. arXiv preprint arXiv:1604.01839(2016)."},{"key":"e_1_3_2_1_25_1","unstructured":"Arya Mazumdar and Barna Saha. 2017. Clustering with noisy queries. In Advances in Neural Information Processing Systems. 5790\u20135801.  Arya Mazumdar and Barna Saha. 2017. Clustering with noisy queries. In Advances in Neural Information Processing Systems. 5790\u20135801."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471721182"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959929"},{"key":"e_1_3_2_1_28_1","unstructured":"Michael Mitzenmacher and Charalampos\u00a0E Tsourakakis. 2016. Predicting Signed Edges with O(n1 + o(1)) Queries. arXiv preprint arXiv:1609.00750(2016).  Michael Mitzenmacher and Charalampos\u00a0E Tsourakakis. 2016. Predicting Signed Edges with O(n1 + o(1)) Queries. arXiv preprint arXiv:1609.00750(2016)."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92871-5_5"},{"volume-title":"Probability and computing: Randomized algorithms and probabilistic analysis","author":"Mitzenmacher Michael","key":"e_1_3_2_1_30_1","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and computing: Randomized algorithms and probabilistic analysis . Cambridge university press . Michael Mitzenmacher and Eli Upfal. 2005. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge university press."},{"key":"e_1_3_2_1_31_1","unstructured":"Andrew\u00a0Y Ng Michael\u00a0I Jordan and Yair Weiss. 2002. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems. 849\u2013856.  Andrew\u00a0Y Ng Michael\u00a0I Jordan and Yair Weiss. 2002. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems. 849\u2013856."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1704842.1705056"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113286"},{"key":"e_1_3_2_1_34_1","unstructured":"Van Vu. 2014. A simple SVD algorithm for finding hidden partitions. arXiv preprint arXiv:1404.3918(2014).  Van Vu. 2014. A simple SVD algorithm for finding hidden partitions. arXiv preprint arXiv:1404.3918(2014)."}],"event":{"name":"WWW '20: The Web Conference 2020","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"],"location":"Taipei Taiwan","acronym":"WWW '20"},"container-title":["Proceedings of The Web Conference 2020"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366423.3380045","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3366423.3380045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:16Z","timestamp":1750199596000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366423.3380045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,20]]},"references-count":34,"alternative-id":["10.1145\/3366423.3380045","10.1145\/3366423"],"URL":"https:\/\/doi.org\/10.1145\/3366423.3380045","relation":{},"subject":[],"published":{"date-parts":[[2020,4,20]]},"assertion":[{"value":"2020-04-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}