### Abstract

We give explicit constructions of extractors which work for a source of any min-entropy on strings of length n. The first construction extracts any constant fraction of the min-entropy using O(log^{2} n) additional random bits. The second extracts all the min-entropy using O(log^{3} n) additional random bits. Both of these constructions use fewer truly random bits than any previous construction which works for all min-entropies and extracts a constant fraction of the min-entropy. We then improve our second construction and show that we can reduce the entropy loss to 2 log(1/ε)+O(1) bits, while still using O(log^{3} n) truly random bits (where entropy loss is defined as [(source min-entropy)+(# truly random bits used) - (# output bits)], and ε is the statistical difference from uniform achieved). This entropy loss is optimal up to a constant additive term. Our extractors are obtained by observing that a weaker notion of `combinatorial design' suffices for the Nisan-Wigderson pseudorandom generator, which underlies the recent extractor of Trevisan. We give near-optimal constructions of such `weak designs' which achieve much better parameters than possible with the notion of designs used by Nisan-Wigderson and Trevisan. We also show how to improve our constructions (and Trevisan's construction) when the required statistical difference from uniform distribution ε is relatively small. This improvement is obtained by using multilinear error correcting codes over finite fields, rather than the arbitrary error correcting codes used by Trevisan.

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

Pages (from-to) | 149-158 |

Number of pages | 10 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 1999 |

Externally published | Yes |

Event | Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA Duration: May 1 1999 → May 4 1999 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'Extracting all the randomness and reducing the error in Trevisan's extractors'. Together they form a unique fingerprint.

## Cite this

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*, 149-158. https://doi.org/10.1145/301250.301292