__
TR04-099 | 11th November 2004 00:00
__

#### Extractors with Weak Random Seeds

TR04-099
Authors:

Ran Raz
Publication: 18th November 2004 18:25

Downloads: 1448

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