## 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/n^{gamma} 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(log^{2} n + log(1/ε)) truly random bits, and (c) extract all the min-entropy using O(log^{3} n + log n · log(1/ε)) truly random bits.

Original language | English (US) |
---|---|

Pages (from-to) | 191-201 |

Number of pages | 11 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

State | Published - Dec 1 1999 |

Externally published | Yes |

Event | Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA Duration: Oct 17 1999 → Oct 19 1999 |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture