{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:41Z","timestamp":1750309121269,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:00:00Z","timestamp":1740096000000},"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":["Commun. ACM"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:p>\n            Despite being a quintessential example of a hard problem, the quest for finding fast algorithms for deciding satisfiability of propositional formulas has occupied computer scientists both in theory and in practice. In this article, we survey recent progress on designing algorithms with strong refutation guarantees for\n            <jats:italic>smoothed<\/jats:italic>\n            instances of the\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>k<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            -SAT problem. Smoothed instances are formed by slight random perturbations of arbitrary instances, and their study is a way to bridge the gap between worst-case and average-case models of problem instances. Our methods yield new algorithms for smoothed\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>k<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            -SAT instances with guarantees that match those for the significantly simpler and well-studied model of\n            <jats:italic>random<\/jats:italic>\n            formulas. Additionally, they have led to a novel and unexpected line of attack on some longstanding extremal combinatorial problems in graph theory and coding theory. As an example, we will discuss the resolution of a 2008 conjecture of Feige on the existence of short cycles in hypergraphs.\n          <\/jats:p>","DOI":"10.1145\/3635117","type":"journal-article","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T21:19:36Z","timestamp":1740086376000},"page":"83-91","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["New Spectral Algorithms for Refuting Smoothed k-SAT"],"prefix":"10.1145","volume":"68","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Peter","family":"Manohar","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,2,21]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.28"},{"key":"e_1_3_1_3_2","unstructured":"Allen S.R. O\u2019Donnell R. and Witmer D. How to refute a random CSP. Corr Abs\/1505.04383 2015."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585143"},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s B. Extremal graph theory. Academic Press 1978.","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-51074-9_4"},{"key":"e_1_3_1_8_2","doi-asserted-by":"crossref","unstructured":"Bri\u00ebt J. and Castro-Silva D. On the threshold for Szemer\u00e9di\u2019s theorem with random differences 2023.","DOI":"10.5817\/CZ.MUNI.EUROCOMB23-032"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_28"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.16"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85221-6_9"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435.013"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.78"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3560469"},{"key":"e_1_3_1_15_2","first-page":"37:1","volume-title":"33rd Symp. on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orl\u00e9ans, France, volume 47 of LIPIcs","author":"Fotakis D.","year":"2016","unstructured":"Fotakis, D., Lampis, M., and Paschos, V.T. Sub-exponential approximation schemes for csps: From dense to almost sparse. In 33rd Symp. on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orl\u00e9ans, France, volume 47 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2016, 37:1\u201337:14."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44693-1_26"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519955"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch89"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_1_20_2","doi-asserted-by":"crossref","unstructured":"Kothari P.K. and Manohar P. An exponential lower bound for linear 3-query locally correctable codes. Corr Abs\/2311.00558 2023.","DOI":"10.1145\/3618260.3649640"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2195-2"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Raghavendra P. Rao S. and Schramm T. Strongly refuting random csps below the spectral threshold. Proceedings of the 49th Annual ACM SIGACT Symp. on Theory of Computing STOC 2017 Montreal QC Canada June 19-23 2017 2017 121\u2013131.","DOI":"10.1145\/3055399.3055417"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380813"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.000-2"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3635117","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3635117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:06Z","timestamp":1750286946000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3635117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,21]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10.1145\/3635117"],"URL":"https:\/\/doi.org\/10.1145\/3635117","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2025,2,21]]},"assertion":[{"value":"2025-02-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}