### 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

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