loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
Polylogarithmic Independence Can Fool DNF Formulas
Providence, Rhode Island
October 21-October 23
ISBN: 0-7695-3010-9
We show that any k-wise independent probability measure on {0, 1}^n can {\text{O}}(\sqrt {m^{2.2} 2^{ - \sqrt {k/10} } } )-fool any boolean function computable by an m-clauses DNF (or CNF) formula on n variables. Thus, for each constante > 0, there is a constantc > 0 such that any boolean function computable by anm-clauses DNF (or CNF) formula can be {\text{m}}^{ - e} e-fooled by any c\log ^2 m-wise probability measure. This resolves, asymptotically and up to a logm factor, the depth-2 circuits case of a conjecture due to Linial and Nisan (1990). The result is equivalent to a new characterization of DNF (or CNF) formulas by low degree polynomials. It implies a similar statement for probability measures with the small bias property. Using known explicit constructions of small probability spaces having the limited independence property or the small bias property, we directly obtain a large class of explicit PRG?s of {\text{O}}(\log ^2 m\log n) -seed length for m-clauses DNF (or CNF) formulas on n variables, improving previously known seed lengths.
Citation:
Louay M.J. Bazzi, "Polylogarithmic Independence Can Fool DNF Formulas," focs, pp.63-73, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.