Error Reduction for Extractors

DSpace/Manakin Repository

Error Reduction for Extractors

Citable link to this page


Title: Error Reduction for Extractors
Author: Reingold, Omer; Raz, Ran; Vadhan, Salil

Note: Order does not necessarily reflect citation order of authors.

Citation: Raz, Ran, Omer Reingold, and Salil Vadhan. Error reduction for extractors. In Proceedings of the 40th Annual Symposium on the Foundations of Computer Science (FOCS 1999), October 17-19, 1999, New York, NY, ed. FOCS 1999, 191-201. Los Alamitos, Calif: IEEE Computer Society.
Full Text & Related Files:
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.
Published Version:
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search