Subexponential Weighted Counting and Exact Optimisation

The deterministic algorithm of \oai{} that counts the satisfying assignments of a $k$-CNF in time $2^{o(n)}$ is reproduced in full and extended from counting to sums of local weights with values in any commutative \Q-algebra. The extension gives deterministic $2^{o(n)}$ algorithms for exact Max-Cut and Max-$k$-SAT on sparse instances, for the independence polynomial, the maximum independent set and the knapsack problem with a conflict graph on every graph, for $0$-$1$ integer programs whose rows involve boundedly many variables, for Vertex Cover in time 2^{o(k)}+\poly(n), for the density of states of Ising and Potts models on bounded-degree graphs, for the Tutte polynomial on the hyperbolas $(x-1)(y-1)=q$, for the minimum distance and the maximum-likelihood decoding of codes with sparse parity checks, for Max-Cut and Max-$k$-SAT at every average degree $o(\sqrt{\log n/\log\log n})$, for Max-Cut on dense graphs close to blow-ups of graphs with $o(n/\log n)$ vertices, and for every problem in \SNP.