Extracting all the Randomness and Reducing the Error in Trevisan's Extractors
Ran Raz, Omer Reingold, and Salil Vadhan.
Abstract
We give explicit constructions of extractors which work for a source of
any minentropy on strings of length n. These extractors can extract any
constant fraction of the minentropy using O(log^2 n) additional random
bits, and can extract all the minentropy 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 minentropies and extracts a
constant fraction of the minentropy. We then improve our second construction
and show that we can reduce the entropy loss to 2log(1/epsilon)+O(1) bits,
while still using O(log^3 n) truly random bits (where entropy loss is defined
as [(source minentropy)+ (# truly random bits used) (# output bits)],
and epsilon 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 NisanWigderson pseudorandom generator, which underlies
the recent extractor of Trevisan. We give nearoptimal constructions of
such "weak designs" which achieve much better parameters than possible
with the notion of designs used by NisanWigderson and Trevisan. We also
show how to improve our constructions (and Trevisan's construction) when
the required statistical difference epsilon from the uniform distribution
is relatively small. This improvement is obtained by using multilinear
errorcorrecting codes over finite fields, rather than the arbitrary errorcorrecting
codes used by Trevisan.
Versions

Proceedings of 31st Annual ACM Symposium on Theory of Computing,
pp. 149158, May 1999. ACM.

Electronic Colloquium on Computational Complexity Technical Report
TR99046.

Journal of Computer & System Sciences 65, pages 97128,
2002. Special
Issue on STOC `99. [
postscript ][
compressed postscript ][official
JCSS page]
[
back to Salil Vadhan's research interests ]