Counting good truth assignments of random k-SAT formulae

We present a deterministic approximation algorithm to compute logarithm of the number of ‘good’ truth assignments for a random k-satisfiability (k-SAT) formula in polynomial time (by ‘good’ we mean that violates a small fraction of clauses). The relative error is bounded above by an arbitrarily small constant ε with high probability¹ as long as the clause density (ratio of clauses to variables) α < αu(k) = 2k^-1logk(1 + o(1)). The algorithm is based on computation of marginal distribution via belief propagation and use of an interpolation procedure. This scheme substitutes the traditional one based on approximation of marginal probabilities via MCMC, in conjunction with self-reduction, which is not easy to extend to the present problem.

Our results are expected hold for a reasonable non-random setup with locally tree-like sparse k-SAT formulas. We derive 2k^-1 log k(1+o(1)) as threshold for uniqueness of the Gibbs distribution on satisfying assignment of random infinite tree k-SAT formulae to establish our results, which is of interest in its own right.