DNF Sparsification and a Faster Deterministic Counting Algorithm

摘要

We give a faster deterministic algorithm for approximately counting the number of satisfying solutions to a dnf or cnf. Given a dnf (or cnf) $f$ on $n$ variables and $poly(n)$ terms, we give a deterministic $n^{tilde{O}((log log n)^2)}$ time algorithm that computes an (additive) $epsilon$ approximation to the fraction of satisfying assignments of $f$ for $epsilon = 1/poly(log n)$. The previous best algorithm due to Luby and Velickovic from nearly two decades ago had a run-time of $n^{exp(O(sqrt{log log n}))}$. A crucial ingredient in our algorithm is a structural result which allows us to sparsify any small-width dnf formula. It says that any width $w$ dnf (irrespective of the number of terms) can be $epsilon$-approximated by a width $w$ dnf with at most $(wlog(1/epsilon))^{O(w)}$ terms. Further, our approximating dnf s have an additional ``sandwiching'' property which is crucial for applications to derandomization. We believe the sparsification result to be of independent interest and use it to show a weak derandomization of the switching lemma wherein the random restrictions need only have limited independence.