Pseudorandom Generators for Regular Branching Programs

DOI10.1137/120875673zbMath1301.68192OpenAlexW2141149699MaRDI QIDQ3190691

Anup Rao, Mark Braverman, Amir Yehudayoff, Ran Raz

Publication date: 18 September 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120875673

zbMATH Keywords

pseudorandom generatorsbranching programsbounded space computation

Mathematics Subject Classification ID

Related Items (18)

A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Simple Optimal Hitting Sets for Small-Success RL ⋮ Amplification and Derandomization without Slowdown ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Learning Read-Constant Polynomials of Constant Degree Modulo Composites ⋮ Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs ⋮ Advice Coins for Classical and Quantum Computation ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Optimal $\varepsilon$-Biased Sets with Just a Little Randomness ⋮ Unnamed Item ⋮ 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 Regular Branching Programs