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}$.