{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:20:07Z","timestamp":1790814007082,"version":"4.1.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T00:00:00Z","timestamp":1550707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1524062"],"award-info":[{"award-number":["CCF-1524062"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Faculty Research Award"],"award-info":[{"award-number":["Faculty Research Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005851","name":"John Simon Guggenheim Memorial Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005851","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2019,2,21]]},"abstract":"<jats:p>The need for deeply understanding when algorithms work (or not) has never been greater.<\/jats:p>","DOI":"10.1145\/3232535","type":"journal-article","created":{"date-parts":[[2019,2,22]],"date-time":"2019-02-22T17:01:44Z","timestamp":1550854904000},"page":"88-96","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Beyond worst-case analysis"],"prefix":"10.1145","volume":"62","author":[{"given":"Tim","family":"Roughgarden","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,2,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 12<sup>th<\/sup> International Conference on Artificial Intelligence and Statistics","author":"Ackerman M.","year":"2009","unstructured":"Ackerman , M. and Ben-David , S . Clusterability: A theoretical study . In Proceedings of the 12<sup>th<\/sup> International Conference on Artificial Intelligence and Statistics , 2009 , 1--8. Ackerman, M. and Ben-David, S. Clusterability: A theoretical study. In Proceedings of the 12<sup>th<\/sup> International Conference on Artificial Intelligence and Statistics, 2009, 1--8."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.08.002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/302908.303020"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055402"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055487"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 30<sup>th<\/sup> International Conference on Machine Learning","author":"Arora S.","year":"2013","unstructured":"Arora , S. , Ge , R. , Halpern , Y. Mimno , D.M. , Moitra , A. , Sontag , D. , Wu , Y. and Zhu , M . A practical algorithm for topic modeling with provable guarantees . In Proceedings of the 30<sup>th<\/sup> International Conference on Machine Learning , 2013 , 280--288. Arora, S., Ge, R., Halpern, Y. Mimno, D.M., Moitra, A., Sontag, D., Wu, Y. and Zhu, M. A practical algorithm for topic modeling with provable guarantees. In Proceedings of the 30<sup>th<\/sup> International Conference on Machine Learning, 2013, 280--288."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027217"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450144"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 43<sup>rd<\/sup> Annual International Colloquium on Automata, Languages, and Programming","author":"Balcan M.-F.","year":"2016","unstructured":"Balcan , M.-F. , Haghtalab , N. and White , C . k-center clustering under perturbation resilience . In Proceedings of the 43<sup>rd<\/sup> Annual International Colloquium on Automata, Languages, and Programming , 2016 , Article No. 68. Balcan, M.-F., Haghtalab, N. and White, C. k-center clustering under perturbation resilience. In Proceedings of the 43<sup>rd<\/sup> Annual International Colloquium on Automata, Languages, and Programming, 2016, Article No. 68."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.53"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000193"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1034"},{"key":"e_1_2_1_14_1","volume-title":"The Simplex Method: A probabilistic analysis","author":"Borgwardt K.H.","year":"1980","unstructured":"Borgwardt , K.H. The Simplex Method: A probabilistic analysis . Springer-Verlag , 1980 . Borgwardt, K.H. The Simplex Method: A probabilistic analysis. Springer-Verlag, 1980."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188826"},{"key":"e_1_2_1_18_1","volume-title":"Clustering is difficult only when it does not matter. arXiv:1205.4891","author":"Daniely A.","year":"2012","unstructured":"Daniely , A. , Linial , N. and M. Saks . Clustering is difficult only when it does not matter. arXiv:1205.4891 , 2012 . Daniely, A., Linial, N. and M. Saks. Clustering is difficult only when it does not matter. arXiv:1205.4891, 2012."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305485"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027127.2027146"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3011870"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1773"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3086952"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050276"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305559"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634141"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897573"},{"key":"e_1_2_1_32_1","first-page":"1","article-title":"The computer science and physics of community detection: Landscapes, phase transitions, and hardness","volume":"121","author":"Moore C","year":"2017","unstructured":"Moore , C . The computer science and physics of community detection: Landscapes, phase transitions, and hardness . Bulletin of EATCS 121 ( 2017 ), 1 -- 37 . Moore, C. The computer science and physics of community detection: Landscapes, phase transitions, and hardness. Bulletin of EATCS 121 (2017), 1--37.","journal-title":"Bulletin of EATCS"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395117"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1711"},{"key":"e_1_2_1_36_1","volume-title":"CS264 lecture notes on beyond worst-case analysis","author":"Roughgarden T.","year":"2009","unstructured":"Roughgarden , T. CS264 lecture notes on beyond worst-case analysis . Stanford University , 2009 --2017. Available at http:\/\/www.timroughgarden.org\/notes.html. Roughgarden, T. CS264 lecture notes on beyond worst-case analysis. Stanford University, 2009--2017. Available at http:\/\/www.timroughgarden.org\/notes.html."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_39_1","volume-title":"Wiley","author":"Trevisan L.","year":"2014","unstructured":"Trevisan , L. Inapproximability of combinatorial optimization problems. Paradigms of Combinatorial Optimization: Problems and New Approaches. V.T. Paschos, ed . Wiley , 2014 . Trevisan, L. Inapproximability of combinatorial optimization problems. Paradigms of Combinatorial Optimization: Problems and New Approaches. V.T. Paschos, ed. Wiley, 2014."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 5<sup>th<\/sup> International Conference on Learning Representations","author":"Zhang C.","year":"2017","unstructured":"Zhang , C. , Bengio , S. , Hardt , M. , Recht , B. and Vinyals , O . Understanding deep learning requires rethinking generalization . In Proceedings of the 5<sup>th<\/sup> International Conference on Learning Representations , 2017 . Zhang, C., Bengio, S., Hardt, M., Recht, B. and Vinyals, O. Understanding deep learning requires rethinking generalization. In Proceedings of the 5<sup>th<\/sup> International Conference on Learning Representations, 2017."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232535","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3232535","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3232535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:42Z","timestamp":1750210782000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,21]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,2,21]]}},"alternative-id":["10.1145\/3232535"],"URL":"https:\/\/doi.org\/10.1145\/3232535","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,21]]},"assertion":[{"value":"2019-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}