2012/05/16 by Gopala, Parikshit, Meka, Raghu, Reingold, Omer
#Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1205.3534
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 ε-approximated by a width w DNF with at most (wlog(1/ε))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^O(log log(n)) time algorithm that computes an additive ε approximation to the fraction of satisfying assignments of f for ε= 1/\poly(log n). The previous best result due to Luby and Velickovic from nearly two decades ago had a run-time of nexp(O(√(log log n))).