CoChat
Sign Up
Cited by 324Computability, Logic, AI AlgorithmsComplexity and Algorithms in GraphsCoding theory and cryptography

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

Luca Trevisan·2001·Journal of the ACM
DOI 10.1145/502090.502099
Open this paper in CoChat — free account

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

Crossref · 10.1145/502090.502099

Cites

47 of 47 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

Citations

Cites

Show all 49 references

Research works printed but not linked: 7

  1. ARVIND V., Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, 235
  2. 10.5555/795662.796290 · DOI
  3. IMPAGLIAZZO R., 1998, Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 734
  4. 10.1145/301250.301428 · DOI
  5. NISAN N., 1996, Proceedings of the 11th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., 44
  6. 10.5555/795663.796348 · DOI
  7. VON NEUMANN J., 1951, Various techniques used in connection with random digits. NBS, Appl. Math. Seri., 12, 36

Cited by

Sorted by citations

Items 301–322 of 322

Related

See all

Metadata

Authors
Trevisan, L.
Affiliations
University of California, Berkeley (US)
Corresponding author
Luca Trevisan
ORCID
Luca Trevisan
Venue
Journal of the ACM
Publisher
Association for Computing Machinery (ACM)
Published
2001-07
Volume
48
Issue
4
Pages
860-879
ISSN
  • 0004-5411 (ISSN-L)
  • 1557-735X
DOI
10.1145/502090.502099
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
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
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