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

DOI10.1007/S00224-016-9680-6zbMATH Open1364.68300OpenAlexW2345543786MaRDI QIDQ519906FDOQ519906

Nagi H. Nahas, Louay Bazzi

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)

Cites Work

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

Cited In (2)

• A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3
• Title not available (Why is that?)

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)