#
Extractors: Optimal up to Constant Factors

Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson

###
Abstract

This paper provides the first explicit construction of extractors which are simultaneously optimal up to constant factors in
*both* seed length and output length. More precisely, for every n,k, our extractor uses a random seed of length
O(log n) to transform any random source on n bits with (min-)entropy k, into a distribution on
(1-alpha)k bits that is eps-close to uniform. Here alpha and eps can be taken to be any positive
constants. (In fact, eps can be almost polynomially small).

Our improvements are obtained via three new techniques, each of which may be of independent interest. The first is a general
construction of *mergers* [TaS96] from locally decodable error-correcting codes. The second introduces new
*condensers* that have *constant seed length* (and retain a constant fraction of the min-entropy in the random source). The
third is a way to augment the "win-win repeated condensing" paradigm of
[RSW00] with error reduction techniques like [RRV99] so that the our constant seed-length
condensers can be used without error accumulation.

###
Versions

[
back to Salil Vadhan's research]