Theory of Computing
-------------------
Title     : Pseudorandom Bits and Lower Bounds for Randomized Turing Machines
Authors   : Emanuele Viola
Volume    : 18
Number    : 10
Pages     : 1-12
URL       : https://theoryofcomputing.org/articles/v018a010

Abstract
--------

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.