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:
We thank Robert Cardiff for advice on histology and Cory Abate-Shen, Laura Crowley, Maximilian Marhold, Maho Shibata, and Roxanne Toivanen for insightful discussions and comments on the manuscript. Our studies used the CCTI Flow Cytometry Core (supported in part by the Office of the Director, National Institutes of Health under awards S10RR027050), and the HICCC Molecular Pathology Shared Resource. This work was supported by post-doctoral fellowships from the DOD Prostate Cancer Research Program (CWC, BIL), by a Rutgers SHP Dean’s Research Intramural grant (AM), and by grants from the Prostate Cancer Foundation (MMS) and the National Institutes of Health (MMS). National Institute of Diabetes and Digestive and Kidney Diseases DK076602 Michael M Shen. National Cancer Institute CA1966692 Michael M Shen U.S. Department of Defense Prostate Cancer Research Program PC101820 Chee Wai Chua. U.S. Department of Defense Prostate Cancer Research Program PC141064 Bo I Li. Prostate Cancer Foundation Michael M Shen Rutgers SHP Dean’s Intramural Grant Antonina Mitrofanova.
Funding Information:
We thank Robert Cardiff for advice on histology and Cory Abate-Shen, Laura Crowley, Maximilian Marhold, Maho Shibata, and Roxanne Toivanen for insightful discussions and comments on the manuscript. Our studies used the CCTI Flow Cytometry Core (supported in part by the Office of the Director, National Institutes of Health under awards S10RR027050), and the HICCC Molecular Pathology Shared Resource. This work was supported by post-doctoral fellowships from the DOD Prostate Cancer Research Program (CWC, BIL), by a Rutgers SHP Dean’s Research Intramural grant (AM), and by grants from the Prostate Cancer Foundation (MMS) and the National Institutes of Health (MMS).

PY - 2002/8

Y1 - 2002/8

N2 - 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 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 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.

AB - 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 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 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.

KW - Combinatorial designs

KW - Expander graphs

KW - Extractors

KW - Probabilistic method

KW - Pseudorandom generators

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

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

U2 - 10.1006/jcss.2002.1824

DO - 10.1006/jcss.2002.1824

M3 - Article

AN - SCOPUS:0038309373

VL - 65

SP - 97

EP - 128

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 1

ER -