Near-optimal pseudorandom generators for constant-depth read-once formulas
From MaRDI portal
Publication:5091767
DOI10.4230/LIPIcs.CCC.2019.16OpenAlexW2794820917MaRDI QIDQ5091767
Dean Doron, Pooya Hatami, William M. Hoza
Publication date: 27 July 2022
Full work available at URL: https://dblp.uni-trier.de/db/conf/coco/coco2019.html#DoronHH19
Related Items (4)
Unnamed Item ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- DNF sparsification and a faster deterministic counting algorithm
- Pseudorandom bits for constant depth circuits
- Approximate inclusion-exclusion
- Pseudorandom generators for space-bounded computation
- Improved algorithms via approximations of probability distributions
- Pseudorandomness for Regular Branching Programs via Fourier Analysis
- A Simple Proof of Bazzi’s Theorem
- Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
- Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Pseudorandom Generators for Regular Branching Programs
- Parity, circuits, and the polynomial-time hierarchy
- Improved Pseudorandom Generators for Depth 2 Circuits
- Polylogarithmic Independence Can Fool DNF Formulas
- Simple Constructions of Almost k-wise Independent Random Variables
- On polynomial approximations to AC
- Bounded Independence Plus Noise Fools Products
- Pseudorandom generators for width-3 branching programs
- Improved pseudorandomness for unordered branching programs through local monotonicity
- Pseudorandomness for read-k DNF formulas
- Pseudorandomness from Shrinkage
- On derandomizing algorithms that err extremely rarely
- Explicit two-source extractors and resilient functions
- Pseudorandom generators for group products
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Pseudorandomness for Read-Once Formulas
- Automata, Languages and Programming
This page was built for publication: Near-optimal pseudorandom generators for constant-depth read-once formulas
