Near-optimal pseudorandom generators for constant-depth read-once formulas
From MaRDI portal
Publication:5091767
Recommendations
Cites work
- A simple proof of Bazzi's theorem
- Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
- Approximate inclusion-exclusion
- Automata, Languages and Programming
- Bounded independence plus noise fools products
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- DNF sparsification and a faster deterministic counting algorithm
- Explicit two-source extractors and resilient functions
- scientific article; zbMATH DE number 6351503 (Why is no real title available?)
- scientific article; zbMATH DE number 7250141 (Why is no real title available?)
- Improved algorithms via approximations of probability distributions
- Improved pseudorandom generators for depth 2 circuits
- Improved pseudorandomness for unordered branching programs through local monotonicity
- On derandomizing algorithms that err extremely rarely
- On polynomial approximations to \(\mathrm{AC}^0\)
- Parity, circuits, and the polynomial-time hierarchy
- Polylogarithmic independence can fool DNF formulas
- Pseudorandom bits for constant depth circuits
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Pseudorandom generators for group products, extended abstract
- Pseudorandom generators for regular branching programs
- Pseudorandom generators for space-bounded computation
- Pseudorandom generators for width-3 branching programs
- Pseudorandomness for read-k DNF formulas
- Pseudorandomness for Read-Once Formulas
- Pseudorandomness for regular branching programs via Fourier analysis
- Pseudorandomness for width-2 branching programs
- Pseudorandomness from shrinkage
- Simple Constructions of Almost k-wise Independent Random Variables
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)
Cited in
(9)- Almost Optimal Pseudorandom Generators for Spherical Caps
- scientific article; zbMATH DE number 7561734 (Why is no real title available?)
- scientific article; zbMATH DE number 7087310 (Why is no real title available?)
- Efficient Pseudorandom Generators Based on the DDH Assumption
- A polynomial-time construction of a hitting set for read-once branching programs of width 3
- Improved pseudorandom generators from pseudorandom multi-switching lemmas
- Pseudorandom Generators for Read-Once Monotone Branching Programs
- Paradigms for Unconditional Pseudorandom Generators
- Pseudorandomness, symmetry, smoothing: I
This page was built for publication: Near-optimal pseudorandom generators for constant-depth read-once formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091767)
