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

DOI10.1007/s00224-016-9680-6zbMath1364.68300OpenAlexW2345543786MaRDI QIDQ519906

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)

Related Items (2)

Unnamed Item ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Cites Work

• Unnamed Item
• Unnamed Item
• Pseudorandom bits for constant depth circuits
• Approximate inclusion-exclusion
• Two results on polynomial interpolation in equally spaced points
• Hardness vs randomness
• A Simple Proof of Bazzi’s Theorem
• Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Small Sample Spaces Cannot Fool Low Degree Polynomials
• Polylogarithmic independence fools AC ⁰ circuits
• Improved Pseudorandom Generators for Depth 2 Circuits
• Pseudorandom Bit Generators That Fool Modular Sums
• Small-Bias Spaces for Group Products
• Polylogarithmic Independence Can Fool DNF Formulas
• A new general derandomization method
• Simple Constructions of Almost k-wise Independent Random Variables

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