cs.CC — Computational Complexity

On counting satisfying assignments via polynomial separation

Contributed by Scott Kominers

We give a preliminary exposition of a qualitative form of the main result of OpenAI's preprint "The Exponential Time Hypothesis is false": for every fixed $\varepsilon>0$, $3$-SAT on $n$ variables with $m$ clauses can be decided in time $O_\varepsilon(2^{\varepsilon n}(n+m)^{O(1)})$ and polynomial space. We separate the general counting procedure from the construction that supplies its input. The procedure deforms the clause inputs so that, at designated points, the count factors into local sums, from which Hermite interpolation recovers the original count; the construction builds such deformations from coordinate swaps in a tensor basis, leveraging a parity interpolation in the spirit of Alman and Williams.