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
Abstract:
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).