The Exponential Time Hypothesis is False

We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary $k$-CNF formula. For every fixed $k\ge2$, on a formula with $n$ variables and $m$ clauses, our algorithm uses space polynomial in $n$ and $m$ and runs in time $(n+m)^{O_k(1)}2^{n/(\log n)^{1/2+o(1)}}$. Our algorithm refutes the Exponential Time Hypothesis (ETH), which postulates that deciding 3-SAT on $n$ variables requires $2^{\Omega(n)}$ time in the worst case.