{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T12:49:47Z","timestamp":1777898987007,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"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 1715187, CCF 1565264, CNS 1618026, CAREER Award 2047933"],"award-info":[{"award-number":["CCF 1715187, CCF 1565264, CNS 1618026, CAREER Award 2047933"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451099","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1629-1642","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Playing unique games on certified small-set expanders"],"prefix":"10.1145","author":[{"given":"Mitali","family":"Bafna","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boaz","family":"Barak","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tselil","family":"Schramm","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"2015","article-title":"Unique Games on the Hypercube","volume":"2015","author":"Agarwal Naman","year":"2015","unstructured":"Naman Agarwal, Guy Kindler, Alexandra Kolla, and Luca Trevisan. 2015. Unique Games on the Hypercube. Chicago J. Theor. Comput. Sci., 2015, 2015. http:\/\/cjtcs.cs.uchicago.edu\/articles\/2015\/1\/contents.html","journal-title":"Chicago J. Theor. Comput. Sci."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2856030"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_3_2_1_4_1","first-page":"2010","article-title":"Improved Algorithms for Unique Games via Divide and Conquer","volume":"17","author":"Arora Sanjeev","year":"2010","unstructured":"Sanjeev Arora, Russell Impagliazzo, William Matthews, and David Steurer. 2010. Improved Algorithms for Unique Games via Divide and Conquer. Electron. Colloquium Comput. Complex., 17, 2010. Pages 41. http:\/\/eccc.hpi-web.de\/report\/2010\/041","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374380"},{"key":"e_1_3_2_1_6_1","volume-title":"Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR, abs\/2005.02970","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR, abs\/2005.02970, 2020. arxiv:2005.02970"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929394"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591886"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055488"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.9"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_13_1","volume-title":"Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236","author":"Barak Boaz","year":"2014","unstructured":"Boaz Barak and David Steurer. 2014. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236, 2014."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.3"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384329"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783030"},{"key":"e_1_3_2_1_18_1","volume-title":"Robustly Learning any Clusterable Mixture of Gaussians. CoRR, abs\/2005.06417","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, and Sushrut Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. CoRR, abs\/2005.06417, 2020. arxiv:2005.06417"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188804"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000086"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.85"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316299"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_2_1_28_1","first-page":"2018","article-title":"Small Set Expansion in The Johnson Graph","volume":"25","author":"Khot Subhash","year":"2018","unstructured":"Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra. 2018. Small Set Expansion in The Johnson Graph. Electronic Colloquium on Computational Complexity (ECCC), 25, 2018. Pages 78. https:\/\/eccc.weizmann.ac.il\/report\/2018\/078","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055432"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00062"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629614"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.20"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.78"},{"key":"e_1_3_2_1_35_1","volume-title":"Kothari and Jacob Steinhardt","author":"Pravesh","year":"2017","unstructured":"Pravesh K. Kothari and Jacob Steinhardt. 2017. Better Agnostic Clustering Via Relaxed Tensor Norms. CoRR, abs\/1711.07465, 2017. arxiv:1711.07465"},{"key":"e_1_3_2_1_36_1","volume-title":"Kothari and David Steurer","author":"Pravesh","year":"2017","unstructured":"Pravesh K. Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. CoRR, abs\/1711.11581, 2017. arxiv:1711.11581"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488611"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2665063"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214079"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.54"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18318-8_17"},{"key":"e_1_3_2_1_43_1","volume-title":"Analysis of boolean functions","author":"O'Donnell Ryan","unstructured":"Ryan O'Donnell. 2014. Analysis of boolean functions. Cambridge University Press."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.111"},{"key":"e_1_3_2_1_45_1","unstructured":"Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra Tselil Schramm and David Steurer. 2018. High-dimensional estimation via sum-of-squares proofs. World Scientific. Pages 3389\u20133423.","DOI":"10.1142\/9789813272880_0186"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.73"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.33"},{"key":"e_1_3_2_1_52_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Raghavendra Prasad","year":"2017","unstructured":"Prasad Raghavendra and Benjamin Weitz. 2017. On the Bit Complexity of Sum-of-Squares Proofs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)."},{"key":"e_1_3_2_1_53_1","unstructured":"David Steurer. 2011. On the complexity of Unique Games and graph expansion."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Salil P. Vadhan. 2012. Pseudorandomness. Now Publishers Inc.. isbn:1601985940","DOI":"10.1561\/9781601985958"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451099","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451099","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":54,"alternative-id":["10.1145\/3406325.3451099","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451099","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}