Polynomial formulations as a barrier for reduction-based hardness proofs

Polynomial formulations as a barrier for reduction-based hardness proofs (via Zoom)

Abstract: The Strong Exponential Time Hypothesis (SETH) asserts that for every epsilon>0 there exists k such that k-SAT requires time (2-epsilon)^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 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).
Based on joint work with Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, and Denil Sharipov.

Bio:  Assistant Professor at Georgetown University. Research interests include Computational Complexity, Algorithms, Pseudorandomness, Learning Theory, and Cryptography.
Received PhD in 2017 from NYU where he was advised by Oded Regev and Yevgeniy Dodis. After that, he was a research scientist at Columbia University and Yahoo Research, and a Rabin postdoc at Harvard University.