Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

DSpace/Manakin Repository

Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

Citable link to this page


Title: Extracting All the Randomness and Reducing the Error in Trevisan's Extractors
Author: Raz, Ran; Vadhan, Salil; Reingold, Omer

Note: Order does not necessarily reflect citation order of authors.

Citation: Raz, Ran, Omer Reingold, and Salil Vadhan. 2002. Extracting all the randomness and reducing the error in Trevisan's extractors. Journal of Computer and System Sciences 65(1): 97-128.
Full Text & Related Files:
Abstract: We give explicit constructions of extractors which work for a source of any min-entropy on strings of length n. These extractors can extract any constant fraction of the min-entropy using O(log2 n) additional random bits, and can extract 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 2log(1/epsilon)+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 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 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 epsilon from the 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.
Published Version: http://dx.doi.org/10.1006/jcss.2002.1824
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2958609
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search