Let C be a class of distributions over {0, 1}^n. A deterministic randomness extractor for C is a function E : {0, 1}^n \to {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 that 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, Raz and Shaltiel (FOCS 2004) that present such a transformation for the very restricted class C of "oblivious bit-fixing sources". Loosely speaking 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.
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb