Simple optimal hitting sets for small-success RL

DOI10.1137/19M1268707MaRDI QIDQ5115702zbMATH OpenFDO

Authors William M. Hoza, David Zuckerman

Publication date 18 August 2020

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

zbMATH Keywords

derandomizationhitting setsspace complexitypseudorandombranching programs

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1301964 (Why is no real title available?)
• scientific article; zbMATH DE number 7561738 (Why is no real title available?)
• scientific article; zbMATH DE number 7561753 (Why is no real title available?)
• A sample of samplers: a computational perspective on sampling
• Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Pseudorandom generators for regular branching programs
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators for width-3 branching programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandomness for network algorithms
• Pseudorandomness for width-2 branching programs
• Randomness in interactive proofs
• Randomness is linear in space
• Relationships between nondeterministic and deterministic tape complexities
• Space pseudorandom generators by communication complexity lower bounds
• Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)

Cited in

(7)

• Paradigms for Unconditional Pseudorandom Generators
• Hitting sets with near-optimal error for read-once branching programs
• scientific article; zbMATH DE number 7561738 (Why is no real title available?)
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)
• Near-optimal derandomization of medium-width branching programs
• A polynomial-time construction of a hitting set for read-once branching programs of width 3
• Hitting sets give two-sided derandomization of small space

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)