pdf icon
Volume 18 (2022) Article 10 pp. 1-12
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines
Received: August 5, 2019
Revised: January 24, 2022
Published: May 20, 2022
Download article from ToC site:
[PDF (279K)] [PS (1007K)] [Source ZIP]
Keywords: lower bound, Turing machine, pseudorandom generator, tape
ACM Classification: F.2.3
AMS Classification: 68Q17

Abstract: [Plain Text Version]

$ $

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.