Computer Science Colloquium

Princeton University

Pseudorandomness: Connections and Constructions

Salil Vadhan
MIT

Wed. March 22, 2000 4:00pm
Computer Science Building 105 (small auditorium)

The power of randomness in computer science and combinatorics is a striking 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 topic of this talk.

Our approach to this issue is to use the 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 problems of derandomizing probabilistic algorithms, extracting randomness from weak (i.e. biased and correlated) sources of random bits, and constructing various kinds of expander graphs.

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 computational 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)