Extractors for a Constant Number of Polynomially Small Min-Entropy Independent
Sources
To appear in STOC 2006.
This paper is about extracting randomness from independent
sources.
Many applications in computer science require a source of
true high quality random bits, yet such a source may not be
available. In this work we show how to deterministically extract high
quality randomness from several independent sources of low quality
randomness.
It turns out that this task is equivalent to giving an explicit
deterministic way to color the set [N]^c with M colors so that the
coloring "looks random" in the following sense: for any large enough
rectangle in the set, the number of points in the rectangle colored a
particular color is about what you would expect for a random
coloring. The goal is to maximize M, minimize c and minimize the size
of the rectangles (a.k.a. the entropy of the sources) for which the
extractor succeeds.
In this paper, we construct an extractor that can extract from a
constant (c) number of independent sources of length n (N = 2^n), each
of which have min-entropy that is polynomially small in n (say n^delta
for some arbitrarily small constant delta). Previously the best known
extractors for a constant number of independent sources required the
sources to have min-entropy at least linear in n. Our extractor is
built by composing previous constructions of strong seeded extractors
in simple ways. We introduce a new technique to condense somewhere
random sources that seems like a useful way to manipulate independent
sources. Unlike other recent work for this problem, our main result
does not rely on any results from additive number theory.
Using Bourgain's extractor (which does use results from
additive number theory) as a black box, we show how to obtain a new
extractor for 2 independent blockwise sources with few blocks, even
when the min-entropy is as small as polylog(n). We also show how to
modify the 2 source disperser for linear min-entropy of Barak et
al. and Raz's 3 source extractor to get dispersers/extractors with
exponentially small error and linear output length where previously
both were constant.
