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
P = BPP if E requires exponential circuits
Impagliazzo, R., & Wigderson, A. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258590 · Cited by 540
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 454
Pseudorandom Generators without the XOR Lemma
Sudan, M., Trevisan, L., & Vadhan, S. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1730 · Cited by 399
Self-citationBPP has subexponential time simulations unlessEXPTIME has publishable proofs
Babai, L., Fortnow, L., Nisan, N., & Wigderson, A. (1993) · Computational Complexity · doi:10.1007/bf01275486 · Cited by 311
Introduction to Parallel Algorithms and Architectures
(1992) · Elsevier eBooks · doi:10.1016/c2013-0-08299-0 · Cited by 277
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Klivans, A. R., & van Melkebeek, D. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539700389652 · Cited by 275
Free bits, PCPs and non-approximability-towards tight results
Bellare, M., Goldreich, O., & Sudan, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492573 · Cited by 271
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 270
Generating quasi-random sequences from semi-random sources
Santha, M., & Vazirani, U. V. (1986) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(86)90044-9 · Cited by 256
Hard-core distributions for somewhat hard problems
Impagliazzo, R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492584 · Cited by 255
Pseudorandom bits for constant depth circuits
Nisan, N. (1991) · COMBINATORICA · doi:10.1007/bf01375474 · Cited by 184
Dispersers, deterministic amplification, and weak random sources
Cohen, A., & Wigderson, A. (1989) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63449 · Cited by 182
Extracting all the randomness and reducing the error in Trevisan's extractors
Raz, R., Reingold, O., & Vadhan, S. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301292 · Cited by 171
Extracting Randomness: A Survey and New Constructions
Nisan, N., & Ta‐Shma, A. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1546 · Cited by 158
Randomness-efficient oblivious sampling
Bellare, M., & Rompel, J. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365687 · Cited by 157
On Unapproximable Versions of $NP$-Complete Problems
Zuckerman, D. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539794266407 · Cited by 115
Zuckerman, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89574 · Cited by 105
Tiny families of functions with random properties: A quality-size trade-off for hashing
Goldreich, O., & Wigderson, A. (1997) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(199712)11:4 · Cited by 103
Generating Quasi-Random Sequences From Slightly-Random Sources
Sántha, M., & Vazirani, U. V. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1984.715945 · Cited by 101
Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications
Wigderson, A., & Zuckerman, D. (1999) · COMBINATORICA · doi:10.1007/s004930050049 · Cited by 101
Randomness vs. time: de-randomization under a uniform assumption
Impagliazzo, R., & Wigderson, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743524 · Cited by 91
Random polynomial time is equal to slightly-random polynomial time
Vazirani, U. V., & Vazirani, V. V. (1985) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1985.45 · Cited by 90
P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma
Impagliazzo, R., & Wigderson, A. (1997) · Cited by 69
More deterministic simulation in logspace
Nisan, N., & Zuckerman, D. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167162 · Cited by 67
Pseudorandom generators without the XOR Lemma (extended abstract)
Sudan, M., Trevisan, L., & Vadhan, S. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301397 · Cited by 60
Self-citationTight bounds for depth-two superconcentrators
Radhakrishnan, J., & Ta‐Shma, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646148 · Cited by 58
Weak Random Sources, Hitting Sets, and BPP Simulations
Andreev, A. E., Clementi, A. E. F., Rolim, J. D. P., & Trevisan, L. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539797325636 · Cited by 53
Self-citationA new general derandomization method
Andreev, A. E., Clementi, A. E. F., & Roli, A. (1998) · Journal of the ACM · doi:10.1145/273865.273933 · Cited by 50
On extracting randomness from weak random sources (extended abstract)
Ta‐Shma, A. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.237877 · Cited by 48
On Extracting Randomness From Weak Random SourcesPreprint
Ta‐Shma, A. (1995) · Electronic colloquium on computational complexity · Cited by 47
On resource-bounded measure and pseudorandomness
Arvind, V., & Köbler, J. (1997) · Lecture notes in computer science · doi:10.1007/bfb0058034 · Cited by 45
Computing with very weak random sources
Srinivasan, A., & Zuckerman, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365688 · Cited by 36
Randomness-optimal sampling, extractors, and constructive leader election
Zuckerman, D. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.237878 · Cited by 34
Explicit OR-dispersers with polylogarithmic degree
Saks, M., Srinivasan, A., & Zhou, S. (1998) · Journal of the ACM · doi:10.1145/273865.273915 · Cited by 29
Ta‐Shma, A. (1998) · doi:10.1145/276698.276736 · Cited by 28
Expanders that beat the eigenvalue bound
Wigderson, A., & Zuckerman, D. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167163 · Cited by 26
Isolation, matching, and counting
Allender, E., & Reinhardt, K. (2002) · doi:10.1109/ccc.1998.694594 · Cited by 10
Flagged first, then by citations
2 of the 49 references couldn’t be matched to a known paper.
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
