Volume 18 (2022) Article 10 pp. 1-12
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines

We exhibit a pseudorandom generator with nearly quadratic stretch for randomized Turing machines, which have a one-way random tape and a two-way work tape. This is the first generator for this model. Its stretch is essentially the best possible given current lower bounds. We use the generator to prove a time lower bound in the above Turing machine model extended with a two-way read-only input tape. The lower bound is of the form $n^{1+\Omega(1)}$ and is for a function computable in linear time with two quantifier alternations. Previously lower bounds were not known even for functions computable in simply exponential time.