ECCC-Report TR04-099https://eccc.weizmann.ac.il/report/2004/099Comments and Revisions published for TR04-099en-usThu, 18 Nov 2004 18:25:28 +0200
Paper TR04-099
| Extractors with Weak Random Seeds |
Ran Raz
https://eccc.weizmann.ac.il/report/2004/099We 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$.
Thu, 18 Nov 2004 18:25:28 +0200https://eccc.weizmann.ac.il/report/2004/099