Error reduction for extractors

Ran Raz, Omer Reingold, Salil Vadhan

Research output: Contribution to journalConference articlepeer-review

23 Scopus citations

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 ε, using only O(log(1/ε)) 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, RRV99] to get improved construction sin almost all cases. Specifically, we obtain extractors that work for sources of any min-entropy on strings on length n which: (a) extract any 1/ngamma fraction of the min-entroly using O(log n + log (1/ε)) truly random bits (for any γ > O), (b) extract any constant fraction of the min-entropy using O(log2 n + log(1/ε)) truly random bits, and (c) extract all the min-entropy using O(log3 n + log n · log(1/ε)) truly random bits.

Original languageEnglish (US)
Pages (from-to)191-201
Number of pages11
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1999
Externally publishedYes
EventProceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA
Duration: Oct 17 1999Oct 19 1999

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Error reduction for extractors'. Together they form a unique fingerprint.

Cite this