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.