Error Reduction for Extractors
Error Reduction for Extractors
Ran Raz,
Omer Reingold ,
and Salil Vadhan.
Abstract
We present a general method to reduce the error of any extractor.
Our method works particularly well in the case that the original
extractor extracts up to a constant fraction of the source
min-entropy and achieves a polynomially small error. In that case,
we are able to reduce the error to (almost) any epsilon,
using only O(log(1/epsilon)) additional truly random bits
(while keeping the other parameters of the original extractor more
or less the same). In other cases (e.g., when the original
extractor extracts all the min-entropy or achieves only a constant
error) our method is not optimal but it is still quite efficient and
leads to improved constructions of extractors.
Using our method, we are able to improve almost all known extractors
in the case where the error required is relatively small (e.g., less
than polynomially small error). In particular, we apply our method
to the new extractors of [Tre99,RRV99a] to get
improved constructions in almost all cases. Specifically, we obtain
extractors that work for sources of any min-entropy on strings of
length n which: (a) extract any 1/n^{gamma} fraction of the
min-entropy using O(log n+log(1/epsilon)) truly random bits
(for any gamma>0), (b) extract any constant fraction of the
min-entropy using O(log^2 n+log(1/epsilon)) truly random
bits, and (c) extract all the min-entropy using
O(log^3 n+(log n)*log(1/epsilon)) truly random bits.
BibTeX entry
@InProceedings{RazReVa99b,
author = {Ran Raz and Omer Reingold and Salil Vadhan},
title = {Error Reduction for Extractors},
booktitle = {Proceedings of the 40th Annual Symposium on the Foundations of Computer Science},
year = {1999},
organization = {IEEE},
month = {October},
address = {New York, NY},
note = {To appear}
}
[ postscript ]
[ back to Salil Vadhan's research interests ]