Pseudorandomness and Fourier-growth bounds for width-3 branching programs

DOI10.4086/TOC.2017.V013A012MaRDI QIDQ4591372zbMATH OpenOpenAlexFDO

Authors Thomas Steinke, Andrew Wan, Salil Vadhan

Publication date 14 November 2017

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1405.7028

zbMATH Keywords

Fourier transformFourier analysispseudorandom generatorsbranching programs

Mathematics Subject Classification ID

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)

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

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
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)
• 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)