Polynomial Formulations as a Barrier for Reduction-Based Hardness Proofs
Open Access
- 8 September 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (4) , 1-44
Abstract
The Strong Exponential Time Hypothesis (SETH) asserts that for every \(\varepsilon > 0\) there exists k such that k -SAT requires time \((2-\varepsilon)^{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- k -SAT, and Set Cover. In this article, we show that fine-grained reductions implying even \(\lambda^{n}\) -hardness of these problems from SETH for any \(\lambda > 1\) , 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). We also extend this barrier result to the class of parameterized problems. Namely, for every \(\lambda > 1\) we conditionally rule out fine-grained reductions implying SETH-based lower bounds of \(\lambda^{k}\) for a number of problems parameterized by the solution size k . 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).
Keywords
Funding Information
- Foundation for the Advancement of Theoretical Physics and Mathematics “BASIS” (075-15-2022-289)
- NSF CAREER Award (CCF2338730)
This publication has 41 references indexed in Scilit:
- A linear vertex kernel for maximum internal spanning treeJournal of Computer and System Sciences, 2013
- Contracting Graphs to Paths and TreesAlgorithmica, 2012
- A 2k kernel for the cluster editing problemJournal of Computer and System Sciences, 2012
- Exact Exponential Algorithms2010
- Finding paths of length k in timeInformation Processing Letters, 2009
- Dynamic Programming for Minimum Steiner TreesTheory of Computing Systems, 2007
- A new algorithm for optimal 2-constraint satisfaction and its implicationsTheoretical Computer Science, 2005
- Vertex Cover: Further Observations and Further ImprovementsJournal of Algorithms, 2001
- Explicit construction of exponential sized families of k-independent setsDiscrete Mathematics, 1986
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von InterpolationskoeffizientenNumerische Mathematik, 1973