Polylogarithmic Independence Can Fool DNF Formulas

DOI10.1137/070691954zbMath1188.68156OpenAlexW1995851745MaRDI QIDQ3654376

Louay Bazzi

Publication date: 6 January 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070691954

zbMATH Keywords

polynomial approximationBoolean functionsharmonic analysisposetspseudorandomnessDNF formulaslimited independence

Mathematics Subject Classification ID

Related Items (16)

Fooling Polytopes ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields] ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Unnamed Item ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ The work of Mark Braverman ⋮ Bounded Independence Plus Noise Fools Products ⋮ Small-bias is not enough to hit read-once CNF ⋮ Bounded-depth circuits cannot sample good codes ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ Mining circuit lower bound proofs for meta-algorithms

This page was built for publication: Polylogarithmic Independence Can Fool DNF Formulas