ECCC-Report TR12-060https://eccc.weizmann.ac.il/report/2012/060Comments and Revisions published for TR12-060en-usWed, 09 Jan 2013 16:43:21 +0200
Revision 2
| DNF Sparsification and a Faster Deterministic Counting |
Parikshit Gopalan,
Raghu Meka,
Omer Reingold
https://eccc.weizmann.ac.il/report/2012/060#revision2Given 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 small 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 $n^{O(1)}$ 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 \geq 1/(\log n)^{O(1)}$. 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}))}$.Wed, 09 Jan 2013 16:43:21 +0200https://eccc.weizmann.ac.il/report/2012/060#revision2
Revision 1
| DNF Sparsification and a Faster Deterministic Counting Algorithm |
Parikshit Gopalan,
Raghu Meka,
Omer Reingold
https://eccc.weizmann.ac.il/report/2012/060#revision1Given 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 $\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 $n^{O(1)}$ 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 \geq 1/(\log n)^{O(1)}$. 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}))}$.Wed, 16 May 2012 04:14:42 +0300https://eccc.weizmann.ac.il/report/2012/060#revision1
Paper TR12-060
| DNF Sparsification and a Faster Deterministic Counting |
Parikshit Gopalan,
Raghu Meka,
Omer Reingold
https://eccc.weizmann.ac.il/report/2012/060Given 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 $\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 $n^{O(1)}$ 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 \geq 1/(\log n)^{O(1)}$. 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}))}$.Wed, 16 May 2012 01:58:28 +0300https://eccc.weizmann.ac.il/report/2012/060