Given a DNF formula 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 $epsilon$-approximated by a width $w$ DNF with at most $(wlog(1/epsilon))^{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 poly(n) terms, we give a deterministic $n^{tilde{O}(log log(n))}$ 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 result due to Luby and Velickovic from nearly two decades ago had a run-time of $n^{exp(O(sqrt{log log n}))}$.
Download