Title: Extractors - Optimal Up to Constant Factos

Speaker: Omer Reingold, AT&T Research and Institute for Advanced Study, Princeton

Date: Tuesday April 8, 2003, 4:30-5:30

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

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.