SPEAKER: Emanuele Viola, Institute of Advanced Studies TITLE: Pseudorandomness: New Results and Applications ABSTRACT: 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.