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 |

- Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
- Explicit Maximally Recoverable Codes with Locality
- Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

> Publications > DNF Sparsification and a faster deterministic counting algorithm