21st Annual IEEE Conference on Computational Complexity (CCC'06) How to Get More Mileage from Randomness Extractors Prague, Czech Republic July 16-July 20 ISBN: 0-7695-2596-2
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2006.24
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.
Citation:
Ronen Shaltiel, "How to Get More Mileage from Randomness Extractors," ccc, pp.46-60, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb