Pseudorandom Generators for Regular Branching Programs
From MaRDI portal
Publication:3190691
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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