Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
DNF Sparsification and a faster deterministic counting algorithm

Parikshit Gopalan, Raghu Meka, and Omer Reingold


Given a DNF formula f on n variables, the two natural size measures are the number of terms or size s(f), and the maximum width of a term w(f). It is folklore that short DNF formulas can be made narrow. We prove a converse, showing that narrow formulas can be sparsified. More precisely, any width w DNF irrespective of its size can be approximated by a width w DNF with at most (wlog(1/eps))O(w) terms.

We combine our sparsification result with the work of Luby and Velikovic to give a faster deterministic algorithm for approximately counting the number of satisfying solutions to a DNF. Given a formula on n variables with nO(1) terms, we give a deterministic nO(loglog(n)) time algorithm that computes an additive approximation to the fraction of satisfying assignments of f. This improves the previous best result due to Luby and Velickovic from nearly two decades ago.


Publication typeInproceedings
Published inCCC'11
> Publications > DNF Sparsification and a faster deterministic counting algorithm