Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR04-099 | 11th November 2004 00:00

#### Extractors with Weak Random Seeds

TR04-099
Authors: Ran Raz
Publication: 18th November 2004 18:25
Keywords:

Abstract:

We show how to extract random bits from two or more independent
weak random sources, in cases where only one source is of linear
min-entropy and all other sources are of logarithmic min-entropy.
We also give improved constructions of mergers and condensers.
In all that comes below, $\delta$ is an arbitrary small constant.
Our main results are as follows:

1) For every seeded-extractor $E$, with seed of length $d$, we
construct an extractor $E'$, with seed of length $O(d)$, that achieves
the same parameters as $E$ but only requires the seed to be of
min-entropy rate $(1/2+\delta)$ (rather than fully random).

2) We show how to extract $\Omega(n)$ bits (with optimal probability
of error) from one source of min-entropy rate $(1/2+\delta)$
and one source of logarithmic min-entropy.

3) We show how to extract $\Omega(n)$ bits (with optimal probability
of error) from one source of min-entropy rate $\delta$
and a constant number of sources of logarithmic min-entropy.

4) We show how to extract $\Omega(n)$ bits, with sub-constant
probability of error, from one source of min-entropy rate $\delta$
and two sources of logarithmic min-entropy.

5) We color the bipartite graph of size $2^n \times 2^n$ with a
constant number of colors, such that any monochromatic subgraph
is of size $< 2^{\delta n} \times n^5$.

6) We show that using a constant number of truly random bits, one
can condense a source of length $n$ and min-entropy rate $\delta$
into a source of length $\Omega(n)$ and min-entropy rate $1-\delta$.

7) We show that using a constant number of truly random bits, one can
merge a constant number of sources of length $n$, such that at least
one of them is of min-entropy rate $1-\delta$, into one source of
length $\Omega(n)$ and min-entropy rate slightly less than $1-\delta$.

ISSN 1433-8092 | Imprint