Hitting sets give two-sided derandomization of small space

DOI10.4086/TOC.2022.V018A021MaRDI QIDQ5040833zbMATH OpenOpenAlexFDO

Authors Kuan Cheng, William M. Hoza

Publication date 18 October 2022

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2022.v018a021

zbMATH Keywords

branching programsderandomizationhitting setpseudorandomnessspace complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Hitting sets give two-sided derandomization of small space
• Simple optimal hitting sets for small-success RL
• Hitting sets with near-optimal error for read-once branching programs
• scientific article; zbMATH DE number 2102761
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs

Cited in

(8)

• Hitting sets when the VC-dimension is small
• Hitting sets give two-sided derandomization of small space
• Paradigms for Unconditional Pseudorandom Generators
• Derandomizing logspace with a small shared hard drive
• Derandomizing logspace with a small shared hard drive
• Pseudodistributions that beat all pseudorandom generators
• Implications of better PRGs for permutation branching programs
• Fooling near-maximal decision trees

This page was built for publication: Hitting sets give two-sided derandomization of small space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5040833)