2016/10/04 by William M. Hoza, Hoza, William M., Chris Umans +1
Computer Science · Mathematics · #Advanced Algebra and Logic #Advice (programming) #Algorithm #Combinatorics #Computational Complexity (cs.CC) #Computer science #Discrete mathematics #FOS: Computer and information sciences #Generator (circuit theory) #Logic, Reasoning, and Knowledge #Mathematics #Physics #Programming language #Pseudorandom number generator #Random number generation #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1610.01199
published in arXiv (Cornell University) (Cornell University) · 24 pages, 2 figures; added more commentary and references, fixed typos, changed notation and formatting
openalex publication_date 2016/10/04 · arxiv created 2017/04/09 · arxiv updated 2017/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Assume that for every derandomization result for logspace algorithms, there\nis a pseudorandom generator strong enough to nearly recover the derandomization\nby iterating over all seeds and taking a majority vote. We prove under a\nprecise version of this assumption that \BPL \⊆ bigcap\α\n> 0 \DSPACE(\log1 + \α n).\n We strengthen the theorem to an equivalence by considering two\ngeneralizations of the concept of a pseudorandom generator against logspace. A\ntargeted pseudorandom generator against logspace takes as input a short uniform\nrandom seed and a finite automaton; it outputs a long bitstring that looks\nrandom to that particular automaton. A simulation advice generator for logspace\nstretches a small uniform random seed into a long advice string; the\nrequirement is that there is some logspace algorithm that, given a finite\nautomaton and this advice string, simulates the automaton reading a long\nuniform random input. We prove that bigcap\α > 0\n\promise\-BPSPACE(\log1 + \α n) = bigcap\α > 0\n\promise\-DSPACE(\log1 + \α n) if and only if for every\ntargeted pseudorandom generator against logspace, there is a simulation advice\ngenerator for logspace with similar parameters.\n Finally, we observe that in a certain uniform setting (namely, if we only\nworry about sequences of automata that can be generated in logspace), targeted\npseudorandom generators against logspace can be transformed into simulation\nadvice generators with similar parameters.\n