Improved pseudorandomness for unordered branching programs through local monotonicity

DOI10.1145/3188745.3188800MaRDI QIDQ5230303zbMATH OpenOpenAlexFDO

Authors Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3188745.3188800

zbMATH Keywords

Fourier analysispseudorandom generatorsrandom restrictionsbranching programsspace-bounded computationsmall-space computation

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Data structures (68P05)

Recommendations

• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandomness for width-2 branching programs
• Pseudorandom generators for regular branching programs
• Pseudorandomness for Linear Length Branching Programs and Stack Machines
• Pseudorandomness for regular branching programs via Fourier analysis
• Pseudorandom Bits for Oblivious Branching Programs
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• scientific article; zbMATH DE number 2102760
• scientific article; zbMATH DE number 2083801

Cited in

(17)

• Fourier bounds and pseudorandom generators for product tests
• Paradigms for Unconditional Pseudorandom Generators
• Pseudorandom Bits for Oblivious Branching Programs
• 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 and Fourier-growth bounds for width-3 branching programs
• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• Pseudorandomness for regular branching programs via Fourier analysis
• Pseudorandomness, symmetry, smoothing: I
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)
• Near-optimal derandomization of medium-width branching programs
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials

This page was built for publication: Improved pseudorandomness for unordered branching programs through local monotonicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230303)