Extracting Randomness Using Few Independent Sources

Abstract

In this work we give the first deterministic extractors from a constant number of weak sources whose entropy rate is less than 1/2. Specifically, for every /spl delta/ > 0 we give an explicit construction for extracting randomness from a constant (depending polynomially on 1//spl delta/) number of distributions over {0, l}n, each having min-entropy /spl delta/n. These extractors output n bits, which are 2/sup -n/ close to uniform. This construction uses several results from additive number theory, and in particular a recent one by Bourgain, Katz and Tao (2003) and of Konyagin (2003). We also consider the related problem of constructing randomness dispersers. For any constant output length m, our dispersers use a constant number of identical distributions, each with min-entropy /spl Omega/(log n) and outputs every possible m-bit string with positive probability. The main tool we use is a variant of the "stepping-up lemma" used in establishing lower bound on the Ramsey number for hyper-graphs (Erdos and Hajnal, 1980).