Randomness "extractors" are functions that extract almost-uniform bits from sources of biased and correlated bits, using a small number of additional uniform bits (known as the "seed") as a catalyst. Extractors play a fundamental role in the theory of pseudorandomness and have a wide variety of applications. Thus coming up with explicit constructions has been the focus of a large body of work over the past decade.

In this talk, we will describe a new construction of extractors from joint work with Chi-Jen Lu, Salil Vadhan, and Avi Wigderson (to appear in STOC 03). These extractors can extract any constant fraction of the min-entropy from an n-bit source, using a seed of length O(log n). This is the first explicit construction of extractors that works for all min-entropies and is simultaneously optimal up to constant factors in both the seed length and output length.