Sasha Golovnev: Polynomial formulations as a barrier for reduction-based hardness proofs
This event is free and open to the publicAdd to Google Calendar
In this paper, 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).