{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T12:57:50Z","timestamp":1791637070413,"version":"4.3.4"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055491","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"47-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":108,"title":["Learning from untrusted data"],"prefix":"10.1145","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacob","family":"Steinhardt","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregory","family":"Valiant","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms. arXiv","author":"Abbe E.","year":"2015","unstructured":"E. Abbe and C. Sandon . Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms. arXiv , 2015 a. E. Abbe and C. Sandon. Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap. arXiv, 2015b. D. Achlioptas and F. McSherry. On spectral learning of mixtures of distributions. In COLT , 2005. E. Abbe and C. Sandon. Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms. arXiv, 2015a. E. Abbe and C. Sandon. Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap. arXiv, 2015b. D. Achlioptas and F. McSherry. On spectral learning of mixtures of distributions. In COLT, 2005."},{"key":"e_1_3_2_2_2_1","volume-title":"Multisection in the stochastic block model using semidefinite programming. arXiv","author":"Agarwal N.","year":"2015","unstructured":"N. Agarwal , A. S. Bandeira , K. Koiliaris , and A. Kolla . Multisection in the stochastic block model using semidefinite programming. arXiv , 2015 . N. Agarwal, A. S. Bandeira, K. Koiliaris, and A. Kolla. Multisection in the stochastic block model using semidefinite programming. arXiv, 2015."},{"key":"e_1_3_2_2_3_1","first-page":"49","volume-title":"Improved spectral-norm bounds for clustering. Approximation, Randomization, and Combinatorial Optimization","author":"Awasthi P.","year":"2012","unstructured":"P. Awasthi and O. Sheffet . Improved spectral-norm bounds for clustering. Approximation, Randomization, and Combinatorial Optimization , pages 37\u2013 49 , 2012 . P. Awasthi and O. Sheffet. Improved spectral-norm bounds for clustering. Approximation, Randomization, and Combinatorial Optimization, pages 37\u201349, 2012."},{"key":"e_1_3_2_2_4_1"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374474"},{"key":"e_1_3_2_2_6_1","first-page":"398","volume-title":"ALT","author":"Balcan M. F.","year":"2009","unstructured":"M. F. Balcan , H. R\u00f6glin , and S. Teng . Agnostic clustering . In ALT , pages 384\u2013 398 , 2009 . M. F. Balcan, H. R\u00f6glin, and S. Teng. Agnostic clustering. In ALT, pages 384\u2013398, 2009."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_3_2_2_8_1","first-page":"729","volume-title":"NIPS","author":"Bhatia K.","year":"2015","unstructured":"K. Bhatia , P. Jain , and P. Kar . Robust regression via hard thresholding . In NIPS , pages 721\u2013 729 , 2015 . K. Bhatia, P. Jain, and P. Kar. Robust regression via hard thresholding. In NIPS, pages 721\u2013729, 2015."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1034"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1290"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970395"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/090761793"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1841234"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670322"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.003"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.85"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1773"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2%3C195::AID-RSA5%3E3.0.CO;2-A"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/070684914"},{"key":"e_1_3_2_2_21_1","volume-title":"Community detection in sparse networks via Grothendieck\u2019s inequality. arXiv","author":"Gu\u00e9don O.","year":"2014","unstructured":"O. Gu\u00e9don and R. Vershynin . Community detection in sparse networks via Grothendieck\u2019s inequality. arXiv , 2014 . O. Gu\u00e9don and R. Vershynin. Community detection in sparse networks via Grothendieck\u2019s inequality. arXiv, 2014."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685798"},{"key":"e_1_3_2_2_23_1","volume-title":"Robust Statistics: The Approach Based on Influence Functions","author":"Hampel F. R.","year":"2011","unstructured":"F. R. Hampel , E. M. Ronchetti , P. J. Rousseeuw , and W. A. Stahel . Robust Statistics: The Approach Based on Influence Functions . Wiley , 2011 . F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust Statistics: The Approach Based on Influence Functions. Wiley, 2011."},{"key":"e_1_3_2_2_24_1","volume-title":"COLT","author":"Hardt M.","year":"2013","unstructured":"M. Hardt and A. Moitra . Algorithms and hardness for robust subspace recovery . In COLT , 2013 . M. Hardt and A. Moitra. Algorithms and hardness for robust subspace recovery. In COLT, 2013."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470434697"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222052"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1577069.1755877"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791122.2791126"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_3_2_2_30_1","first-page":"354","volume-title":"ALT","author":"Kushagra S.","year":"2016","unstructured":"S. Kushagra , S. Samadi , and S. Ben-David . Finding meaningful cluster structure amidst background noise . In ALT , pages 339\u2013 354 , 2016 . S. Kushagra, S. Samadi, and S. Ben-David. Finding meaningful cluster structure amidst background noise. In ALT, pages 339\u2013354, 2016."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_3_2_2_32_1","volume-title":"Concentration and regularization of random graphs. arXiv","author":"Le C. M.","year":"2015","unstructured":"C. M. Le , E. Levina , and R. Vershynin . Concentration and regularization of random graphs. arXiv , 2015 . C. M. Le, E. Levina, and R. Vershynin. Concentration and regularization of random graphs. arXiv, 2015."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214013"},{"key":"e_1_3_2_2_34_1","volume-title":"Learning communities in the presence of errors. arXiv","author":"Makarychev K.","year":"2015","unstructured":"K. Makarychev , Y. Makarychev , and A. Vijayaraghavan . Learning communities in the presence of errors. arXiv , 2015 . K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. Learning communities in the presence of errors. arXiv, 2015."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875554"},{"key":"e_1_3_2_2_36_1","volume-title":"How robust are reconstruction thresholds for community detection? arXiv","author":"Moitra A.","year":"2015","unstructured":"A. Moitra , W. Perry , and A. S. Wein . How robust are reconstruction thresholds for community detection? arXiv , 2015 . A. Moitra, W. Perry, and A. S. Wein. How robust are reconstruction thresholds for community detection? arXiv, 2015."},{"key":"e_1_3_2_2_37_1","volume-title":"Coverings of random ellipsoids, and invertibility of matrices with iid heavy-tailed entries. arXiv","author":"Rebrova E.","year":"2015","unstructured":"E. Rebrova and K. Tikhomirov . Coverings of random ellipsoids, and invertibility of matrices with iid heavy-tailed entries. arXiv , 2015 . E. Rebrova and K. Tikhomirov. Coverings of random ellipsoids, and invertibility of matrices with iid heavy-tailed entries. arXiv, 2015."},{"key":"e_1_3_2_2_38_1","volume-title":"Norms of random matrices: local and global problems. arXiv","author":"Rebrova E.","year":"2016","unstructured":"E. Rebrova and R. Vershynin . Norms of random matrices: local and global problems. arXiv , 2016 . E. Rebrova and R. Vershynin. Norms of random matrices: local and global problems. arXiv, 2016."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jfan.1998.3384"},{"key":"e_1_3_2_2_40_1","volume-title":"NIPS","author":"Steinhardt J.","year":"2016","unstructured":"J. Steinhardt , G. Valiant , and M. Charikar . Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction . In NIPS , 2016 . J. Steinhardt, G. Valiant, and M. Charikar. Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction. In NIPS, 2016."},{"key":"e_1_3_2_2_41_1","volume-title":"Contributions to probability and statistics, 2:448\u2013485","author":"Tukey J. W.","year":"1960","unstructured":"J. W. Tukey . A survey of sampling from contaminated distributions. Contributions to probability and statistics, 2:448\u2013485 , 1960 . J. W. Tukey. A survey of sampling from contaminated distributions. Contributions to probability and statistics, 2:448\u2013485, 1960."},{"key":"e_1_3_2_2_42_1","volume-title":"Principal component analysis with contaminated data: The high dimensional case. arXiv","author":"Xu H.","year":"2010","unstructured":"H. Xu , C. Caramanis , and S. Mannor . Principal component analysis with contaminated data: The high dimensional case. arXiv , 2010 . H. Xu, C. Caramanis, and S. Mannor. Principal component analysis with contaminated data: The high dimensional case. arXiv, 2010."},{"key":"e_1_3_2_2_43_1","first-page":"1064","volume-title":"NIPS","author":"Zha H.","year":"2001","unstructured":"H. Zha , X. He , C. Ding , H. Simon , and M. Gu . Spectral relaxation for k-means clustering . In NIPS , pages 1057\u2013 1064 , 2001 . H. Zha, X. He, C. Ding, H. Simon, and M. Gu. Spectral relaxation for k-means clustering. In NIPS, pages 1057\u20131064, 2001."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055491","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":43,"alternative-id":["10.1145\/3055399.3055491","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055491","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}