The DOI matches its Crossref record; 47 of the 49 references it cites were found in a registry or an index.
Extractors and pseudorandom generators
Abstract
We introduce a new approach to constructing extractors. Extractors are algorithms that transform a “weakly random” distribution into an almost uniform distribution. Explicit constructions of extractors have a variety of important applications, and tend to be very difficult to obtain.We demonstrate an unsuspected connection between extractors and pseudorandom generators. In fact, we show that every pseudorandom generator of a certain kind is an extractor.A pseudorandom generator construction due to Impagliazzo and Wigderson, once reinterpreted via our connection, is already an extractor that beats most known constructions and solves an important open question. We also show that, using the simpler Nisan--Wigderson generator and standard error-correcting codes, one can build even better extractors with the additional advantage that both the construction and the analysis are simple and admit a short self-contained description.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“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 [97]
In the citing paper
“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 [97]
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot the international journal of robotics research and application · doi:10.1108/ir.1999.04926fae.001 · Cited by 39,228
The Theory of Error-Correcting Codes
(1977) · North-Holland mathematical library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,891
Goldwasser, S., & Micali, S. M. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,667
Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
Leighton, F. T. (1991) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,467
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. M. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,309
A hard-core predicate for all one-way functions
Goldreich, O., & Levin, L. A. (1989) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/73007.73010 · Cited by 1,192
Theory and application of trapdoor functions
Yao, A. C.-C. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.45 · Cited by 1,019
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 814
Limits on the provable consequences of one-way permutations
Impagliazzo, R., & Rudich, S. (1989) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/73007.73012 · Cited by 580
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
Chor, B., & Goldreich, O. (1988) · SIAM Journal on Computing · doi:10.1137/0217015 · Cited by 551
Research works printed but not linked: 7
- ARVIND V., Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, 235
- 10.5555/795662.796290 · DOI
- IMPAGLIAZZO R., 1998, Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 734
- 10.1145/301250.301428 · DOI
- NISAN N., 1996, Proceedings of the 11th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., 44
- 10.5555/795663.796348 · DOI
- VON NEUMANN J., 1951, Various techniques used in connection with random digits. NBS, Appl. Math. Seri., 12, 36
Cited by
Sorted by citations
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,374
The Physics of Quantum Information
(2000) · doi:10.1007/978-3-662-04209-0 · Cited by 1,086
Quantum random number generators
Herrero-Collantes, M., & García-Escartín, J. C. (2017) · Reviews of Modern Physics · doi:10.1103/revmodphys.89.015004 · Cited by 850
Detection-Loophole-Free Test of Quantum Nonlocality, and Applications
Christensen, B. G., McCusker, K. T., Altepeter, J. B., Calkins, B., Gerrits, T., Lita, A. E., Miller, A., Shalm, L. K., Zhang, Y., Nam, S. W., et al. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.130406 · Cited by 477
Quantum random number generation
Ma, X., Yuan, X., Cao, Z., Qi, B., & Zhang, Z. (2016) · npj Quantum Information · doi:10.1038/npjqi.2016.21 · Cited by 445
Metadata
- Authors
- Trevisan, L.
- Affiliations
- University of California, Berkeley (US)
- Corresponding author
- Luca Trevisan
- ORCID
- Luca Trevisan
- Venue
- Journal of the ACM
- Published
- 2001-07
- Volume
- 48
- Issue
- 4
- Pages
- 860-879
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1967175855
- Cited by
- 324
- References
- 49
- Citations by year
- 2026: 7 · 2025: 7 · 2024: 10 · 2023: 9 · 2022: 16 · 2021: 8 · 2020: 25 · 2019: 14 · 2018: 9 · 2017: 13 · 2016: 17 · 2015: 9 · 2014: 16 · 2013: 16 · 2012: 21
- FWCI
- 9.54
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Journal of the ACM (publishedVersion)
- Archivio istituzionale della Ricerca - Bocconi (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
- Keywords
- extractors, pseudorandom generators, weak randomness, explicit constructions, error-correcting codes, randomness extraction, pseudorandomness
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
