## DNF Sparsification and a Faster Deterministic Counting

by Parikshit Gopalan, Raghu Meka, Omer Reingold

#### Oded's comments

Just see my advocation of this problem
in choice 87 (April 2012).

#### The original abstract

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 $\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}))}$.

Back to
list of Oded's choices.