DNF Sparsification and a faster deterministic counting algorithm

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 n^O(1) terms, we give a deterministic n^O(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.