Small-bias is not enough to hit read-once CNF
From MaRDI portal
Publication:519906
DOI10.1007/s00224-016-9680-6zbMath1364.68300OpenAlexW2345543786MaRDI QIDQ519906
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
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 0 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