Extracting all the randomness and reducing the error in Trevisan's extractors
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Trevisan's extractor is a strong extractor (its seed can be reused) and its seed length is the polylogarithmic function of the input.
“Moreover, it is a strong extractor (its seed can be reused) and its seed length is the polylogarithmic function of the input.”
From Quantum random number generation (2016) · cites this paper as [98]
The Extractors section’s comparison table gives Trevisan’s extractor a seed length expressed in logarithms of the input size, supporting the polylogarithmic-seed claim. The Trevisan extractor section describes its seed, but the passages found do not say that the extractor is strong or that its seed can be reused. (LLM, conf=0.82)
Experimental — accuracy not yet measuredTrevisan's extractor has been proven to be secure against quantum adversaries.
“Trevisan ' s extractor 97,98 has been proven to be secure against quantum adversaries. 99”
From Quantum random number generation (2016) · cites this paper as [98]
The Trevisan extractor section (page unavailable) discusses a classical indistinguishability proof and security reduction, but does not address quantum adversaries. Searches for quantum adversaries and quantum side information found no passage establishing the claimed security result. (LLM, conf=0.76)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
References 51 · Cited by 171
Research works printed but not linked: 8
- AK921 E.F. Assmus and J.D. Key. Designs and (heir codes. Number 103 in Cambridge Tracts in Mathematics. Cambridge University Press, 1992.
- Noga Alon, Joel H. Spencer. and Paul Erd& The Prob- abilistic Merhod. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley and Sons, Inc., 1992.
- Rajeev Motwani and Prabhakar Raghavan. Random- izedrllgorifkms. Cambridge University Press, 1995.
- Noam Nisan and Avi Wigderson. Hardness vs ran domness. Journal of Computer and Sysrem Sciences, 49(2):149-167, October 1994.
- Umesh V. Vazirani. Randomness, Adversaties, and Compurorion. PhD thesis, University of California, Berkeley, 1984.
- Umesh V. Vazirani. Strong communication complex- ity or generating quasirandom sequences from two communicating semirandom sources. Combinaforica, 7(4):375-392. 1987.
- Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annwrl Sympo- sium on Foundations of Cornpurer Science, pages SO- 91, Chicago, Illinois, 3-5 November 1982. IEEE.
- David Zuckerman. Randomness-optimal oblivi- ous sampling. 11(4):345-367, i Algotitkms,
- Authors
- Raz, R., Reingold, O., & Vadhan, S.
- Affiliations
- Weizmann Institute of Science (IL)
- Massachusetts Institute of Technology (US)
- Venue
- Proceedings of the thirty-first annual ACM symposium on Theory of Computing
- Publisher
- ACM
- Published
- 1999-05
- Pages
- 149-158
- OpenAlex
- W2119913278
- Cited by
- 171
- References
- 51
- Citations by year
- 2025: 1 · 2023: 1 · 2022: 3 · 2021: 3 · 2020: 5 · 2019: 4 · 2018: 4 · 2017: 2 · 2016: 6 · 2015: 3 · 2014: 3 · 2013: 5 · 2012: 16
- FWCI
- 8.83
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Symposium on Theory of Computing (STOC) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- randomness extractors, min-entropy, pseudorandom generators, combinatorial designs, finite fields, entropy loss, explicit constructions
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
