Pseudorandom generators for width-3 branching programs

DOI10.1145/3313276.3316319zbMath1433.68604arXiv1806.04256OpenAlexW2963619305MaRDI QIDQ5212804

Avishay Tal, Raghu Meka, Omer Reingold

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

random restrictionsread-once branching programsepsilon-biased generatorpseudorandom generators for small-space computationpseudorandom generators for space-bounded computation

Mathematics Subject Classification ID

Data structures (68P05) Randomized algorithms (68W20)

Related Items (14)

Unnamed Item ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Simple Optimal Hitting Sets for Small-Success RL ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

This page was built for publication: Pseudorandom generators for width-3 branching programs