Simple optimal hitting sets for small-success RL
From MaRDI portal
Publication:5115702
DOI10.1137/19M1268707zbMATH Open1452.68271MaRDI QIDQ5115702FDOQ5115702
Authors: William M. Hoza, David Zuckerman 
Publication date: 18 August 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
- Hitting sets with near-optimal error for read-once branching programs
- Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
- A polynomial-time construction of a hitting set for read-once branching programs of width 3
- Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
- Pseudorandom generators for regular branching programs
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Analysis of algorithms (68W40) Data structures (68P05)
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Pseudorandomness for network algorithms
- A sample of samplers: a computational perspective on sampling
- Randomness is linear in space
- Randomness in interactive proofs
- Pseudorandom generators for space-bounded computation
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- Pseudorandomness for width-2 branching programs
- Title not available (Why is that?)
- Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pseudorandom generators for regular branching programs
- Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
- Pseudorandom generators for width-3 branching programs
- Space pseudorandom generators by communication complexity lower bounds
- Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
Cited In (6)
- Paradigms for Unconditional Pseudorandom Generators
- Hitting sets with near-optimal error for read-once branching programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Near-optimal derandomization of medium-width branching programs
- A polynomial-time construction of a hitting set for read-once branching programs of width 3
This page was built for publication: Simple optimal hitting sets for small-success RL
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115702)
