DNF Sparsification and a faster deterministic counting algorithm

Parikshit Gopalan, Raghu Meka, and Omer Reingold

June 2012

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/eps))^{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^{O}(loglog(n)) time algorithm that computes an additive approximation to the fraction of satisfying assignments of f. This improves the previous best result due to Luby and Velickovic from nearly two decades ago.

Publication type | Inproceedings |

Published in | CCC'11 |

Publisher | IEEE |

- A New Interactive Hashing Theorem
- From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs
- Inequalities and tail bounds for elementary symmetric polynomials

> Publications > DNF Sparsification and a faster deterministic counting algorithm