|
Published Articles >> Table of Contents >> Abstract
21st Annual IEEE Conference on Computational Complexity (CCC'06)
pp. 46-60
How to Get More Mileage from Randomness Extractors
Ronen Shaltiel, University of Haifa, Israel
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2006.24
Send link to a friend
| Abstract |
|
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.
|
 Additional Information
|
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
|
|
