TY - JOUR

T1 - Extracting all the randomness and reducing the error in Trevisan's extractors

AU - Raz, Ran

AU - Reingold, Omer

AU - Vadhan, Salil

N1 - Funding Information:
1Preliminary versions of this work appeared in STOC ‘99 [RRV99b] and on ECCC [RRV99c]. 2Work supported by an American-Israeli BSF grant 95-00238 and by ESPRIT working group RAND2. 3Research performed while still at the Weizmann Institute, Rehovot, Israel. Research supported by a Clore Scholars award and an Eshkol Fellowship of the Israeli Ministry of Science and by ESPRIT working group RAND2. 4This work was done when the author was at MIT, supported by a DOD/NDSEG Fellowship and partially by DARPA Grant DABT63-96-C-0018.

PY - 1999

Y1 - 1999

N2 - 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(log2 n) additional random bits. The second extracts all the min-entropy using O(log3 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(log3 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.

AB - 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(log2 n) additional random bits. The second extracts all the min-entropy using O(log3 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(log3 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.

UR - http://www.scopus.com/inward/record.url?scp=0032629108&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032629108&partnerID=8YFLogxK

U2 - 10.1145/301250.301292

DO - 10.1145/301250.301292

M3 - Conference article

AN - SCOPUS:0032629108

SP - 149

EP - 158

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0734-9025

T2 - Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99

Y2 - 1 May 1999 through 4 May 1999

ER -