文章基本信息

标题：DNF Sparsification and a Faster Deterministic Counting Algorithm
本地全文：下载
作者：Parikshit Gopalan ; Raghu Meka ; Omer Reingold 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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))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 for 1(logn)O(1) . The previous best result due to Luby and Velickovic from nearly two decades ago had a run-time of nexp(O(loglogn)) .