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