Emanuele Viola, 
Institute of Advanced Studies

Pseudorandomness: New Results and Applications

Pseudorandomness is the theory that studies probability distributions
that ``look random'' despite having little entropy. Besides addressing
the philosophical problem of the nature of randomness,
pseudorandomness has a striking variety of applications. For example,
most modern cryptography relies on pseudorandom distributions, and the
study of pseudorandomness has led to several algorithmic
breakthroughs, such as Reingold's space-efficient algorithm for
finding the exit from a given maze.

In this talk we survey some of our results in pseudorandomness,
focusing on pseudorandom generators, which are objects that stretch a
short truly random seed into a longer sequence that ``looks random.''

First we address cryptographic pseudorandom generators, interpreting
``looks random'' as ``random enough for cryptography.'' We present new
trade-offs between the (parallel) complexity of the generator and its
output length. Then we move to special-purpose pseudorandom
generators, interpreting ``looks random'' as ``looks random to a
restricted computational model.'' We develop a new application of such
generators to the study of the foundations of cryptography,
specifically to the study of the average-case complexity of NP: We
show how to take any function in NP that is `mildly' hard on average
and transform it into one that is `extremely' hard on
average. Finally, we discuss some new state-of-the-art pseudorandom
generators whose output looks random to constant-depth circuits and
low-degree polynomials.

No previous knowledge of cryptography or complexity theory is required
for this talk.