{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T23:12:23Z","timestamp":1771369943614,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519955","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"678-689","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random"],"prefix":"10.1145","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Peter","family":"Manohar","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Abascal Jackson","year":"2021","unstructured":"Jackson Abascal , Venkatesan Guruswami , and Pravesh K. Kothari . 2021. Strongly refuting all semi-random Boolean CSPs . In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13 , 2021 . SIAM, 454\u2013472. Jackson Abascal, Venkatesan Guruswami, and Pravesh K. Kothari. 2021. Strongly refuting all semi-random Boolean CSPs. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021. SIAM, 454\u2013472."},{"key":"e_1_3_2_1_2_1","volume-title":"APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference (LIPIcs","volume":"15","author":"Ahn Kwangjun","year":"2020","unstructured":"Kwangjun Ahn . 2020 . A Simpler Strong Refutation of Random k-XOR. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference (LIPIcs , Vol. 176). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2:1\u20132: 15 . Kwangjun Ahn. 2020. A Simpler Strong Refutation of Random k-XOR. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference (LIPIcs, Vol. 176). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2:1\u20132:15."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.48"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.39"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384234"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225140"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746625"},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 29th Annual Conference on Learning Theory. 417\u2013445","author":"Barak Boaz","year":"2016","unstructured":"Boaz Barak and Ankur Moitra . 2016 . Noisy Tensor Completion via the Sum-of-Squares Hierarchy . In Proceedings of the 29th Annual Conference on Learning Theory. 417\u2013445 . Boaz Barak and Ankur Moitra. 2016. Noisy Tensor Completion via the Sum-of-Squares Hierarchy. In Proceedings of the 29th Annual Conference on Learning Theory. 417\u2013445."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488665"},{"key":"e_1_3_2_1_11_1","volume-title":"Algorithms and Techniques (Lecture Notes in Computer Science","volume":"321","author":"Coja-Oghlan Amin","year":"2004","unstructured":"Amin Coja-Oghlan , Andreas Goerdt , and Andr\u00e9 Lanka . 2004 . Strong Refutation Heuristics for Random k-SAT. In Approximation, Randomization, and Combinatorial Optimization , Algorithms and Techniques (Lecture Notes in Computer Science , Vol. 3122). Springer, 310\u2013 321 . Amin Coja-Oghlan, Andreas Goerdt, and Andr\u00e9 Lanka. 2004. Strong Refutation Heuristics for Random k-SAT. In Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques (Lecture Notes in Computer Science, Vol. 3122). Springer, 310\u2013321."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.59"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85221-6_9"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.78"},{"key":"e_1_3_2_1_15_1","unstructured":"Uriel Feige and Tal Wagner. 2016. Generalized Girth Problems in Graphs and Hypergraphs.  Uriel Feige and Tal Wagner. 2016. Generalized Girth Problems in Graphs and Hypergraphs."},{"key":"e_1_3_2_1_16_1","volume-title":"33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016","volume":"14","author":"Fotakis Dimitris","year":"2016","unstructured":"Dimitris Fotakis , Michael Lampis , and Vangelis Th. Paschos . 2016 . Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse . In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 , February 17-20, 2016, Orl\u00e9ans, France (LIPIcs , Vol. 47). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 37:1\u201337: 14 . Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. 2016. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orl\u00e9ans, France (LIPIcs, Vol. 47). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 37:1\u201337:14."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000575"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070014"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Pravesh K. Kothari Ryuhei Mori Ryan O\u2019Donnell and David Witmer. 2017. Sum of squares lower bounds for refuting any CSP. In STOC. ACM 132\u2013145.  Pravesh K. Kothari Ryuhei Mori Ryan O\u2019Donnell and David Witmer. 2017. Sum of squares lower bounds for refuting any CSP. In STOC. ACM 132\u2013145.","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_3_2_1_22_1","first-page":"51","article-title":"Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators","volume":"24","author":"Margulis G. A.","year":"1988","unstructured":"G. A. Margulis . 1988 . Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators . Problemy Peredachi Informatsii , 24 , 1 (1988), 51 \u2013 60 . issn:0555-2923 G. A. Margulis. 1988. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24, 1 (1988), 51\u201360. issn:0555-2923","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754402"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2195-2"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra Satish Rao and Tselil Schramm. 2017. Strongly refuting random CSPs below the spectral threshold. In STOC. ACM 121\u2013131.  Prasad Raghavendra Satish Rao and Tselil Schramm. 2017. Strongly refuting random CSPs below the spectral threshold. In STOC. ACM 121\u2013131.","DOI":"10.1145\/3055399.3055417"},{"key":"e_1_3_2_1_26_1","volume-title":"Coding for Sunflowers. CoRR, abs\/1909.04774","author":"Rao Anup","year":"2019","unstructured":"Anup Rao . 2019. Coding for Sunflowers. CoRR, abs\/1909.04774 ( 2019 ), arXiv:1909.04774. arxiv:1909.04774 Anup Rao. 2019. Coding for Sunflowers. CoRR, abs\/1909.04774 (2019), arXiv:1909.04774. arxiv:1909.04774"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.37"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45078-8_23"},{"key":"e_1_3_2_1_29_1","volume-title":"The Kikuchi Hierarchy and Tensor PCA. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","author":"Wein Alexander S.","year":"2019","unstructured":"Alexander S. Wein , Ahmed El Alaoui , and Cristopher Moore . 2019 . The Kikuchi Hierarchy and Tensor PCA. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 , Baltimore, Maryland, USA , November 9-12, 2019. IEEE Computer Society, 1446\u20131468. Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. 2019. The Kikuchi Hierarchy and Tensor PCA. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019. IEEE Computer Society, 1446\u20131468."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519955","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519955","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:38Z","timestamp":1750268978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519955"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":29,"alternative-id":["10.1145\/3519935.3519955","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519955","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}