Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-051 | 9th April 2019 16:46

Pseudorandom bits and lower bounds for randomized Turing machines

RSS-Feed




TR19-051
Authors: Emanuele Viola
Publication: 9th April 2019 16:47
Downloads: 224
Keywords: 


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 polynomial lower bound for the stronger Turing machine model where we also have a two-way read-only input tape. This is the first lower bound for this model.



ISSN 1433-8092 | Imprint