In the Spring Semester of 2003, I plan to offer an advanced graduate course on new interconnections between pseudorandom number generation and computational complexity theory. This course covers very recent research, most of which can only be found in journal articles. The breakthroughs we discuss will be of great interest to students specializing in randomized algorithms and complexity, cryptography, discrete mathematics, and statistics.
We say that a generator is pseudorandom with respect to a complexity class C if no algorithm in class C can substantially distinguish the generator's output from a truly random bitstream. It follows, for example, that any pseudorandom generator that can ``fool'' any polynomial time Turing machine can be substituted for the random bit stream fed to any randomized polynomial-time algorithm without noticeable degradation in performance. (This leads naturally to the open question: ``Is P=BPP?'') The existence of such a generator hinges on the existence of predicates which are hard on average (relative to class C). After introducing the collage of subject areas that play a part in this drama, we will explore complexity-theoretic issues in pseudorandomness. Though we will approach the problems from a mathematical viewpoint, we will occasionally discuss applications to cryptography and derandomization of algorithms. Along the way, we will also learn about the most recent advances in error-control coding, which has an important and surprising role in all this.
The student who takes on this challenge should either already know or commit to becoming familiar with: