{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:17:07Z","timestamp":1757621827127,"version":"3.44.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100012708","name":"Foundation for the Advancement of Theoretical Physics and Mathematics \u201cBASIS\u201d","doi-asserted-by":"crossref","award":["075-15-2022-289"],"award-info":[{"award-number":["075-15-2022-289"]}],"id":[{"id":"10.13039\/501100012708","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF CAREER award","award":["CCF2338730"],"award-info":[{"award-number":["CCF2338730"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>\n            The Strong Exponential Time Hypothesis (SETH) asserts that for every\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varepsilon &gt; 0\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            there exists\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            such that\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -SAT requires time\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((2-\\varepsilon)^{n}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . The field of fine-grained complexity has leveraged SETH to prove quite tight conditional lower bounds for dozens of problems in various domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. Yet, it has been repeatedly asked in the literature whether SETH-hardness results can be proven for other fundamental problems such as Hamiltonian Path, Independent Set, Chromatic Number, MAX-\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -SAT, and Set Cover.\n          <\/jats:p>\n          <jats:p>\n            In this article, we show that fine-grained reductions implying even\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\lambda^{n}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -hardness of these problems from SETH for\n            <jats:italic toggle=\"yes\">any<\/jats:italic>\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\lambda &gt; 1\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , would imply new circuit lower bounds: super-linear lower bounds for Boolean series-parallel circuits or polynomial lower bounds for arithmetic circuits (each of which is a four-decade open question).\n          <\/jats:p>\n          <jats:p>\n            We also extend this barrier result to the class of parameterized problems. Namely, for every\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\lambda &gt; 1\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            we conditionally rule out fine-grained reductions implying SETH-based lower bounds of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\lambda^{k}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for a number of problems parameterized by the solution size\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>Our main technical tool is a new concept called polynomial formulations. In particular, we show that many problems can be represented by relatively succinct low-degree polynomials, and that any problem with such a representation cannot be proven SETH-hard (without proving new circuit lower bounds).<\/jats:p>","DOI":"10.1145\/3721134","type":"journal-article","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T10:47:45Z","timestamp":1741085265000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial Formulations as a Barrier for Reduction-Based Hardness Proofs"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5605-5485","authenticated-orcid":false,"given":"Tatiana","family":"Belova","sequence":"first","affiliation":[{"name":"Steklov Institute of Mathematics, St. Petersburg, Russia and ITMO University, St. Petersburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7847-1027","authenticated-orcid":false,"given":"Alexander","family":"Golovnev","sequence":"additional","affiliation":[{"name":"Computer Science, Georgetown University, Washington, District of Columbia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5656-0336","authenticated-orcid":false,"given":"Alexander","family":"S. Kulikov","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington, District of Columbia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1019-5719","authenticated-orcid":false,"given":"Ivan","family":"Mihajlin","sequence":"additional","affiliation":[{"name":"JetBrains Research, Limassol, Cyprus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7411-1671","authenticated-orcid":false,"given":"Denil","family":"Sharipov","sequence":"additional","affiliation":[{"name":"St Petersburg State University, St. Petersburg, Russian Federation"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90161-5"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.24"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_3_3_14_2","first-page":"261","volume-title":"ITCS 2016","author":"Carmosino Marco L.","year":"2016","unstructured":"Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. 2016. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In ITCS 2016. ACM, 261\u2013270."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.04.001"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/11611257_21"},{"key":"e_1_3_3_20_2","first-page":"8","article-title":"Bounds for linear satisfiability problems","volume":"1999","author":"Erickson Jeff","year":"1999","unstructured":"Jeff Erickson. 1999. Bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science 1999 (1999), 8.","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"e_1_3_3_21_2","first-page":"240","volume-title":"FSTTCS 2000","author":"Fellows Michael R.","year":"2000","unstructured":"Michael R. Fellows, Catherine McCartin, Frances A. Rosamond, and Stege Ulrike. 2000. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In FSTTCS 2000. Springer, 240\u2013251."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.03.004"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715953"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1324-4"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3185378"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9670-2"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0110015"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_3_31_2","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft John E.","year":"1979","unstructured":"John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison-Wesley."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766282"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743516"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_61"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780595"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_26"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.4171\/jems\/861"},{"key":"e_1_3_3_38_2","first-page":"1180","volume-title":"STOC 2022","author":"Li Jiatu","year":"2022","unstructured":"Jiatu Li and Tianqi Yang. 2022. \\(3.1n-o(n)\\) circuit lower bounds for explicit functions. In STOC 2022. ACM, 1180\u20131193."},{"key":"e_1_3_3_39_2","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bulletin of EATCS 105 (2011), 41\u201372. Retrieved from http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/92","journal-title":"Bulletin of EATCS"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3170442"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_24"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492475"},{"key":"e_1_3_3_43_2","first-page":"1065","volume-title":"SODA 2010","author":"P\u01cetra\u015fcu Mihai","year":"2010","unstructured":"Mihai P\u01cetra\u015fcu and Ryan Williams. 2010. On the possibility of faster SAT algorithms. In SODA 2010. SIAM, 1065\u20131075."},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436566"},{"key":"e_1_3_3_47_2","first-page":"184","article-title":"Vermeidung von divisionen","volume":"264","author":"Strassen Volker","year":"1973","unstructured":"Volker Strassen. 1973. Vermeidung von divisionen. Journal f\u00fcr die reine und angewandte Mathematik 264 (1973), 184\u2013202.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"},{"key":"e_1_3_3_49_2","first-page":"17","volume-title":"IPEC 2015","author":"Williams Virginia Vassilevska","year":"2015","unstructured":"Virginia Vassilevska Williams. 2015. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In IPEC 2015. Schloss Dagstuhl, 17\u201329."},{"key":"e_1_3_3_50_2","volume-title":"ICM 2018","volume":"3447","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In ICM 2018, 3447--3487."},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_3_53_2","doi-asserted-by":"crossref","unstructured":"Ryan Williams. 2009. Finding paths of length k in \\(O^{*}(2^{k})\\) time. Information Processing Letters 109 6 (2009) 315\u2013318.","DOI":"10.1016\/j.ipl.2008.11.004"},{"key":"e_1_3_3_54_2","first-page":"2:1","volume-title":"CCC 2016","volume":"50","author":"Williams Ryan","year":"2016","unstructured":"Ryan Williams. 2016. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In CCC 2016, Vol. 50. Dagstuhl, 2:1\u20132:17."},{"key":"e_1_3_3_55_2","unstructured":"Or Zamir. 2021. Breaking the \\(2^{n}\\) barrier for 5-coloring and 6-coloring. In ICALP 2021. LIPIcs Vol. 198 113:1\u2013113:20."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3721134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T15:51:57Z","timestamp":1757346717000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3721134"],"URL":"https:\/\/doi.org\/10.1145\/3721134","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2023-07-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-19","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}