Pseudorandomness and Fourier-growth bounds for width-3 branching programs
DOI10.4086/TOC.2017.V013A012zbMATH Open1377.65003arXiv1405.7028OpenAlexW1562469244MaRDI QIDQ4591372FDOQ4591372
Authors: Thomas Steinke, Andrew Wan, Salil Vadhan 
Publication date: 14 November 2017
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1405.7028
Recommendations
- Pseudorandomness and Fourier growth bounds for width-3 branching programs
- Pseudorandomness for regular branching programs via Fourier analysis
- Improved pseudorandomness for unordered branching programs through local monotonicity
- Pseudorandom generators for width-3 branching programs
- Pseudorandom Bits for Oblivious Branching Programs
Random number generation in numerical analysis (65C10) Numerical methods for trigonometric approximation and interpolation (65T40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cited In (11)
- Paradigms for Unconditional Pseudorandom Generators
- Pseudorandom generators for width-3 branching programs
- Pseudorandomness and Fourier growth bounds for width-3 branching programs
- An Optimal Separation of Randomized and Quantum Query Complexity
- Pseudorandomness for width-2 branching programs
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Pseudorandomness for regular branching programs via Fourier analysis
- Pseudorandomness for Linear Length Branching Programs and Stack Machines
- Title not available (Why is that?)
- Approximating iterated multiplication of stochastic matrices in small space
- A polynomial-time construction of a hitting set for read-once branching programs of width 3
This page was built for publication: Pseudorandomness and Fourier-growth bounds for width-3 branching programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4591372)
