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.
展开▼
