How to get more mileage from randomness extractors
Let C be a class of distributions over {0, 1}(n). A deterministic randomness extractor for C is a function E : {0, 1}(n) -> {0, 1}(m) such that for any X in C the distribution E(X) is statistically close to the uniform distribution. A long line of research deals with explicit constructions of such extractors for various classes C while trying to maximize m. In this paper we give a general transformation that transforms a deterministic extractor E which extracts "few" bits into an extractor E' that extracts "almost all the bits present in the source distribution." More precisely, we prove a general theorem saying that if E and C satisfy certain properties, then we can transform E into an extractor E'. Our methods build on (and generalize) a technique of Gabizon et al. [FOCS (2004) 394-403] that presents such a transformation for the very restricted class C of "oblivious bit-fixing sources." The high level idea is to find properties of E and C which allow "recycling" the output of E so that it can be "reused" to operate on the source distribution. An obvious obstacle is that the output of E is correlated with the source distribution. Using our transformation we give an explicit construction of a two-source extractor E : {0, 1}(n) x {0, 1}(n) -> {0, 1}(m) such that for every two independent distributions X-1 and X-2 over {0, 1}(n) with minentropy at least k = (1/2 + delta)n and epsilon <= 2(-log4) (n), E(X-1, X-2) is epsilon-close to the uniform distribution on m = 2k - C-delta log(1/epsilon) bits. This result is optimal except for the precise constant C-delta and improves previous results by Chor and Goldreich [SICOMP 17 (1988) 230-261], Vazirani [Combinatorica 7 (1987) 375-392], and Dodis et al. [RANDOM (2004) 334-344]. We also give explicit constructions of extractors for samplable distributions that extract many bits even out of "low-entropy" samplable distributions. These constructions rely on average case hardness assumptions and extend some previous results by Trevisan and Vadhan [FOCS (2000) 32-42] which give such extractors only for distributions with "high entropy." (C) 2008 Wiley Periodicals, Inc.
randomness extractors explicit construction samplable distributions 2-source extractors