Speaker: Salil Vadhan
Affiliation: MIT
Date: 2/29/00
Time and Place: 4:15 PM, B14 Hollister
Host: Dexter Kozen
Title: Pseudorandomness: Connections and
Constructions
The power of randomness in computer science and combinatorics is a fascinating phenomenon. By allowing algorithms to "flip coins", we are able to efficiently solve problems that we do not know how to solve efficiently otherwise. Randomization is also a powerful tool for proving the existence of useful combinatorial objects, such as error-correcting codes and expander graphs (sparse graphs with very strong connectivity properties).
However, we still do not know to what extent the randomness is really *necessary* in these settings and understanding this is the goal addressed in this talk. More concretely, we are interested in questions such as: Can all randomized algorithms be simulated deterministically with only a small loss in efficiency? Can we extract truly random bits from weak random sources? Can we give explicit (efficient & deterministic) constructions of combinatorial objects such as error-correcting codes and expander graphs?
Our approach to answering these question is to use the unifying paradigm of *pseudorandomness*, which is concerned with efficiently generating objects that "look random" despite being constructed deterministically, or at least using a reduced amount of randomness. Within this paradigm, some beautiful connections have been discovered between the above questions. In this talk, I will survey some of the work I have done exploiting these connections to yield:
- More efficient constructions of pseudorandom generators from hard compuational problems. (joint work with Madhu Sudan and Luca Trevisan)
- The best known methods for extracting all the randomness from a weak random source. (joint work with Ran Raz and Omer Reingold)
- A new Composition Theorem for expander graphs, which gives the first explicit construction of constant-degree expander graphs with an
"elementary" analysis. For one measure of expansion, we obtain graphs with the best degree-expansion relationship among existing explicit constructions. (joint work with Omer Reingold and Avi Wigderson)