Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

DOI10.1145/3055399.3055414MaRDI QIDQ4978009zbMATH OpenOpenAlexFDO

Authors William M. Hoza, Chris Umans

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01199

zbMATH Keywords

derandomizationspace complexitypseudorandom generators

Mathematics Subject Classification ID

Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this assumption that $$. We strengthen the theorem to an equivalence by considering two generalizations of the concept of a pseudorandom generator against logspace. A targeted pseudorandom generator against logspace takes as input a short uniform random seed and a finite automaton; it outputs a long bitstring that looks random to that particular automaton. A simulation advice generator for logspace stretches a small uniform random seed into a long advice string; the requirement is that there is some logspace algorithm that, given a finite automaton and this advice string, simulates the automaton reading a long uniform random input. We prove that $$ if and only if for every targeted pseudorandom generator against logspace, there is a simulation advice generator for logspace with similar parameters. Finally, we observe that in a certain uniform setting (namely, if we only worry about sequences of automata that can be generated in logspace), targeted pseudorandom generators against logspace can be transformed into simulation advice generators with similar parameters.

Recommendations

• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
• Pseudorandom generators for space-bounded computation
• Hardness vs randomness
• Time-space tradeoff in derandomizing probabilistic logspace
• scientific article; zbMATH DE number 3876586

Cited in

(6)

• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
• scientific article; zbMATH DE number 7561753 (Why is no real title available?)
• scientific article; zbMATH DE number 7701432 (Why is no real title available?)
• Simple optimal hitting sets for small-success RL
• On recycling the randomness of states in space bounded computation
• STACS 2004

This page was built for publication: Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

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