Polynomial formulations as a barrier for reduction-based hardness proofs

The Strong Exponential Time Hypothesis (SETH) postulates that SAT cannot be solved in less than $2^n$ steps. In recent years, many SETH-based lower bounds have been proven: for example, $n^2$ for Edit Distance, $2^n$ for Hitting Set, $2^{\text{treewidth}}$ for Independent Set. One may speculate that SETH can explain many other current algorithmic barriers. In the talk, we'll show that, for many problems, an SETH lower bound would imply new circuit lower bounds.