Small-bias is not enough to hit read-once CNF
From MaRDI portal
Publication:519906
DOI10.1007/S00224-016-9680-6zbMATH Open1364.68300OpenAlexW2345543786MaRDI QIDQ519906FDOQ519906
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
Recommendations
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?)
- 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
- Title not available (Why is that?)
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) 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)
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)
