DNF Sparsification and a Faster Deterministic Counting Algorithm
Preprint
Abstract
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 $(w\log(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}))}$.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- The Monotone Complexity of k-clique on Random Graphs2010
- Deterministic approximate counting of depth-2 circuits2002
- Boolean Functions With Low Average Sensitivity Depend On Few CoordinatesCombinatorica, 1998
- An O(nlog log n) Learning Algorithm for DNF under the Uniform DistributionJournal of Computer and System Sciences, 1995
- Learning Boolean Functions via the Fourier Transform1994
- Small-Bias Probability Spaces: Efficient Constructions and ApplicationsSIAM Journal on Computing, 1993
- Pseudorandom bits for constant depth circuitsCombinatorica, 1991
- Monte-Carlo approximation algorithms for enumeration problemsJournal of Algorithms, 1989
- Monte-Carlo algorithms for enumeration and reliability problems1983
- Intersection Theorems for Systems of SetsJournal of the London Mathematical Society, 1960