Extractors with weak random seeds

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. Our main results are as follows: 1. A long line of research, starting by Nisan and Zuckerman [14], gives explicit constructions of seeded-extractors, that is, extractors that use a short seed of truly random bits to extract randomness from a weak random source. For every such extractor E, with seed of length d, we construct an extractor E', with seed of length d' = O(d), that achieves the same parameters as E but only requires the seed to be of min-entropy larger than (1/2 + δ)-d' (rather than fully random), where δ is an arbitrary small constant. 2. Fundamental results of Chor and Goldreich and Vazirani [6, 21] show how to extract Ω(n) random bits from two (independent) sources of length n and minentropy larger than (1/2+δ).n, where 5 is an arbitrary small constant. We show how to extract Ω(n) random bits (with optimal probability of error) when only one source is of min-entropy (1/2 + δ) · n and the other source is of logarithmic min-entropy. ¹ 3. A recent breakthrough of Barak, Impagliazzo and Wigderson [4] shows how to extract Ω(n) random bits from a constant number of (independent) sources of length n and min-entropy larger than δn, where δ is an arbitrary small constant. We show how to extract Ω(n) random bits (with optimal probability of error) when only one source is of min-entropy δn and all other (constant number of) sources are of logarithmic minentropy. 4. A very recent result of Barak, Kindler, Shaltiel, Sudakov and Wigderson [5] shows how to extract a constant number of random bits from three (independent) sources of length n and min-entropy larger than δn, where 5 is an arbitrary small constant. We show how to extract Ω(n) random bits, with sub-constant probability of error, from one source of min-entropy on and two sources of logarithmic min-entropy. 5. In the same paper, Barak, Kindler, Shaltiel, Sudakov and Wigderson [5] give an explicit coloring of the complete bipartite graph of size 2 ⁿ × 2 ⁿ with two colors, such that there is no monochromatic subgraph of size larger than 2 ^δn x 2 ^δn, where δ is an arbitrary small constant. We give an explicit coloring of the complete bipartite graph of size 2 ⁿ × 2 ⁿ with a constant number of colors, such that there is no monochromatic subgraph of size larger than 2 ^δn × n ⁵. We also give improved constructions of mergers and condensers. In particular, 1. We show that using a constant number of truly random bits, one can condense a source of length n and min-entropy rate 6 into a source of length Ω(n) and min-entropy rate 1 -δ, where δ is an arbitrary small constant. 2. 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 minentropy rate 1-δ, into one source of length Ω(n) and min-entropy rate slightly less than 1-δ, where δ is any small constant.