scientific article; zbMATH DE number 7250141
From MaRDI portal
Publication:5121889
Boolean functions (06E30) Sums of independent random variables; random walks (60G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)
Recommendations
- Pseudorandom generators from polarizing random walks
- Random walk tests and pseudorandom number generators
- Pseudorandom Generators and Typically-Correct Derandomization
- scientific article; zbMATH DE number 1736451
- Pseudorandom generators for low degree polynomials
- A random-walk pseudorandom byte generator
- Stochastic investigations of pseudo-random number generators
Cites work
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- Constant depth circuits, Fourier transform, and learnability
- Expander graphs and their applications
- scientific article; zbMATH DE number 3829252 (Why is no real title available?)
- scientific article; zbMATH DE number 6789278 (Why is no real title available?)
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
- Pseudorandom bits for constant depth circuits
- Pseudorandomness for regular branching programs via Fourier analysis
- Simple Constructions of Almost k-wise Independent Random Variables
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
Cited in
(13)- A random-walk pseudorandom byte generator
- Quantum versus randomized communication complexity, with efficient players
- Pseudorandomness via the discrete Fourier transform
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- Pseudorandom generators for low sensitivity functions
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- Circuit lower bounds for MCSP from local pseudorandom generators
- Fourier bounds and pseudorandom generators for product tests
- Near-optimal pseudorandom generators for constant-depth read-once formulas
- Pseudorandom generators from polarizing random walks
- Improved pseudorandom generators from pseudorandom multi-switching lemmas
- An Optimal Separation of Randomized and Quantum Query Complexity
- Quantum versus randomized communication complexity, with efficient players
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5121889)
