TITLE: Extracting Randomness Using Few Independent Sources

SPEAKER: Boaz Barak, IAS Princeton

ABSRTACT:

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