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
Revised: January 24, 2022
Published: May 20, 2022
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.
Licensed under a Creative Commons Attribution License (CC-BY)