Small-bias is not enough to hit read-once CNF

DOI10.1007/S00224-016-9680-6MaRDI QIDQ519906zbMATHOpenAlexFDO

Authors Louay Bazzi, Nagi H. Nahas

Publication date 31 March 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-016-9680-6

zbMATH Keywords

harmonic analysispseudorandomnesshitting setread-once CNF formulassmall-bias

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Small bias requires large formulas
• Some limitations of the sum of small-bias distributions
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Pseudorandomness for read-\(k\) DNF formulas
• Improved pseudorandom generators for depth 2 circuits

Cites work

• scientific article; zbMATH DE number 3477793 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• A new general derandomization method
• A simple proof of Bazzi's theorem
• Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
• Approximate inclusion-exclusion
• Hardness vs randomness
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Improved pseudorandom generators for depth 2 circuits
• Polylogarithmic independence can fool DNF formulas
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Pseudorandom Bit Generators That Fool Modular Sums
• Pseudorandom bits for constant depth circuits
• Simple Constructions of Almost k-wise Independent Random Variables
• Small Sample Spaces Cannot Fool Low Degree Polynomials
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Small-Bias Spaces for Group Products
• Two results on polynomial interpolation in equally spaced points

Cited in

(4)

• Entropy of weight distributions of small-bias spaces and pseudobinomiality
• A polynomial-time construction of a hitting set for read-once branching programs of width 3
• Small bias requires large formulas
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)

This page was built for publication: Small-bias is not enough to hit read-once CNF

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q519906)