loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
ASCII Text
x 
 
Ronen Shaltiel, "How to Get More Mileage from Randomness Extractors," Computational Complexity, Annual IEEE Conference on, pp. 46-60, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2006.24,
author = {Ronen Shaltiel},
title = {How to Get More Mileage from Randomness Extractors},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2006},
issn = {1093-0159},
pages = {46-60},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.24},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - How to Get More Mileage from Randomness Extractors
SN - 1093-0159
SP46
EP60
A1 - Ronen Shaltiel,
PY - 2006
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Ronen Shaltiel, University of Haifa, Israel
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.