Extracting all the randomness and reducing the error in Trevisan's extractors
Ran Raz, Omer Reingold, Salil Vadhan · 1999
We give explicit constructions of extractors which work for a source of any min.entropyon strings of length n.The first construction extracts any constant fraction of the min-entropy using O(log* n) additional random bits, The second extracts all the tin-entropy using O(log3 n) additional random bits.Both of these constmcdons use fewer truly random bits than any previous construction which works for all min.entropiesand 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(l/e) +0(l) bits, while still using O(log3 n) truly random bits (where entropy loss is defined as [(source min-entropy) + (# truly random bits used) -(#output bits)], and E 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 Trevisa 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 E 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.