Error Reduction for Extractors

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.