Near-optimal derandomization of medium-width branching programs

DOI10.1145/3564246.3585108MaRDI QIDQ6499213

Aaron L Putterman, Edward Pyne

Publication date: 8 May 2024

zbMATH Keywords

branching programspseudorandomnessspace-bounded computation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Pseudorandom generators for space-bounded computation
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Randomness is linear in space
• Relationships between nondeterministic and deterministic tape complexities
• Pseudorandomness for network algorithms
• Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
• Simple Optimal Hitting Sets for Small-Success RL
• Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
• Pseudorandom generators for width-3 branching programs
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Error reduction for weighted PRGs against read once branching programs
• Pseudodistributions that beat all pseudorandom generators (extended abstract)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Near-optimal derandomization of medium-width branching programs