Improved pseudorandomness for unordered branching programs through local monotonicity

DOI10.1145/3188745.3188800zbMath1427.68058OpenAlexW2809421804MaRDI QIDQ5230303

Eshan Chattopadhyay, Pooya Hatami, Avishay Tal, Omer Reingold

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 generatorsbranching programsrandom restrictionsspace-bounded computationsmall-space computation

Mathematics Subject Classification ID

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

Related Items (8)

An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Unnamed Item

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