George Karakostas, Princeton University
Pseudorandom Generators for Space Bounded Computations
Abstarct:
Pseudorandom generators (PRG) are functions that extend a random string
into a bigger one that "looks" random to algorithms from a
particular complexity class. In this talk we are going to
describe some of these PRG and their applications. We are going
to focus on those of them that work for bounded space
computations. Nisan has described the best (in some ways) known generator
for space $O(S)$ machines. This generator uses $O(S * \log R)$ truly
random bits in order to produce $R$ pseudorandom bits, and it has
many applications especially in results that address the question
of how much randomness (if any) is really needed in the
applications that use it. For example, using Nisan's generator,
Saks \& Zhou show that $RSPACE(S) \subset SPACE(S^{3/2})$ and Armoni,
TaShma, Wigderson \& Zhou show that $SL \subset L^{4/3}$.