Simple Optimal Hitting Sets for Small-Success RL

DOI10.1137/19M1268707zbMath1452.68271MaRDI QIDQ5115702

William M. Hoza, David Zuckerman

Publication date: 18 August 2020

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

zbMATH Keywords

derandomizationbranching programshitting setsspace complexitypseudorandom

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Cites Work

• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Pseudorandom generators for space-bounded computation
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Randomness in interactive proofs
• Randomness is linear in space
• Relationships between nondeterministic and deterministic tape complexities
• Pseudorandomness for network algorithms
• Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
• A Sample of Samplers: A Computational Perspective on Sampling
• Pseudorandom Generators for Regular Branching Programs
• Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
• Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
• Pseudorandom generators for width-3 branching programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item