CaltechAUTHORS
  A Caltech Library Service

Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

Hoza, William M. and Umans, Chris (2017) Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017. ACM , New York, NY, pp. 629-640. ISBN 978-1-4503-4528-6. https://resolver.caltech.edu/CaltechAUTHORS:20170705-173204335

[img] PDF - Submitted Version
See Usage Policy.

286Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170705-173204335

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 BPL ⊆ ⋂_(α>0) DSPACE(log^(1 +α) n). 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 ⋂_(α>0) prBPSPACE(log^(1+α)n) = ⋂_(α>0)prDSPACE(log^(1+α)n) 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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3055399.3055414DOIArticle
https://arxiv.org/abs/1610.01199arXivDiscussion Paper
Additional Information:© 2017 ACM. The first author is supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1610403. The second author is supported by National Science Foundation Grant No. CCF-1423544 and by a Simons Investigator grant.
Funders:
Funding AgencyGrant Number
NSFDGE-1610403
NSFCCF-1423544
Simons FoundationUNSPECIFIED
Subject Keywords:Theory of computation → Pseudorandomness and derandomization; Complexity classes; pseudorandom generators, derandomization, space complexity
Record Number:CaltechAUTHORS:20170705-173204335
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170705-173204335
Official Citation:William M. Hoza and Chris Umans. 2017. Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017). ACM, New York, NY, USA, 629-640. DOI: https://doi.org/10.1145/3055399.3055414
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78787
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:06 Jul 2017 21:10
Last Modified:15 Nov 2019 22:39

Repository Staff Only: item control page