Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNCONDITIONAL PSEUDORANDOM GENERATORS:
Reports tagged with Unconditional Pseudorandom Generators:
TR12-060 | 16th May 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold

DNF Sparsification and a Faster Deterministic Counting

Revisions: 2

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 ... more >>>




ISSN 1433-8092 | Imprint