DIMACS Theoretical Computer Science Seminar

Title: Extracting Randomness Using Few Independent Sources

Speaker: Boaz Barak, IAS Princeton

Date: November 22, 2004 3:30-4:30pm

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


We consider the problem of extracting truly random bits from several independent weak random sources. Previous constructions either required a large number of sources (polynomial in the input length), or required the entropy of each source to be large. Specifically, the best previous explicit construction using a constant number of n-bit sources required that at least one of the sources contains more than n/2 bits of (min-)entropy. In contrast, the optimal, non-explicit construction only requires the min-entropy to be more than log n.

In this work we give the first deterministic extractor from a constant number of weak sources whose entropy rate is less than 1/2. Specifically, for every r>0 we give an explicit construction for extracting randomness from a constant (depending polynomially on 1/r) number of distributions over n-bit strings, each having min-entropy r*n. Our extractor outputs n bits, which are 2^{-n} close to the uniform distribution.

Our construction uses several results from additive number theory, and in particular a recent one by Bourgain, Katz and Tao and of Konyagin.

Joint work with Russell Impagliazo (UCSD) and Wvi Wigderson (IAS).