Counting good truth assignments of random k-SAT formulae
Andrea Montanari, Devavrat Shah · arXiv (Cornell University) · 2006
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 violate a small fraction of clauses). The relative error is bounded above by an arbitrarily small constant epsilon with high probability as long as the clause density (ratio of clauses to variables) alpha