The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
Pseudorandom Generators without the XOR Lemma
Open accessOverview
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
Verification
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.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Elements of Information Theory
Jacobs, K. (1992) · Discrete Stochastics · doi:10.1007/978-3-0348-8645-1_7 · Cited by 2,918
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,322
A hard-core predicate for all one-way functions
Goldreich, O., & Levin, L. A. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73010 · Cited by 1,193
Improved decoding of Reed-Solomon and algebraic-geometry codes
Guruswami, V., & Sudan, M. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.782097 · Cited by 998
Self-citationTheory and application of trapdoor functions
Yao, A. C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.45 · Cited by 968
The Complexity of Boolean Functions
Wegener, I. (1987) · Cited by 882
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 808
Decoding of Reed Solomon Codes beyond the Error-Correction Bound
Sudan, M. (1997) · Journal of Complexity · doi:10.1006/jcom.1997.0439 · Cited by 723
Self-citationNisan, N., & Zuckerman, D. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0004 · Cited by 634
Elements of Information Theory, Wiley Series in Telecommunications
Cover, T. M., & Allen, T. (1991) · Cited by 623
P = BPP if E requires exponential circuits: derandomizing the XOR lemma
Impagliazzo, R., & Wigderson, A. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258590 · Cited by 534
Razborov, A. A., & Rudich, S. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1494 · Cited by 479
The Complexity of Boolean Functions
(2005) · Complexity Theory · doi:10.1007/3-540-27477-4_16 · Cited by 376
The bit extraction problem or t-resilient functions
Chor, B., Goldreich, O., Hasted, J., Freidmann, J., Rudich, S., & Smolensky, R. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.55 · Cited by 361
Two theorems on random polynomial time
Adleman, L. (1978) · 19th Annual Symposium on Foundations of Computer Science (sfcs 1978) · doi:10.1109/sfcs.1978.37 · Cited by 316
BPP 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 310
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Klivans, A. R., & van Melkebeek, D. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700389652 · Cited by 270
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
Lipton, R. (1991) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/002/13 · Cited by 255
Hard-core distributions for somewhat hard problems
Impagliazzo, R. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492584 · Cited by 254
Hiding instances in multioracle queries
Beaver, D., & Feigenbaum, J. (1990) · Lecture Notes in Computer Science · doi:10.1007/3-540-52282-4_30 · Cited by 235
On the power of two-point based sampling
Chor, B., & Goldreich, O. (1989) · Journal of Complexity · doi:10.1016/0885-064x(89)90015-0 · Cited by 191
Dispersers, deterministic amplification, and weak random sources
Cohen, A., & Wigderson, A. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63449 · Cited by 182
Self-testing/correcting for polynomials and for approximate functions
Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., & Wigderson, A. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103429 · Cited by 181
Self-citationHighly resilient correctors for polynomials
Gemmell, P., & Sudan, M. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90195-2 · Cited by 169
Self-citationRandom-Self-Reducibility of Complete Sets
Feigenbaum, J., & Fortnow, L. (1993) · SIAM Journal on Computing · doi:10.1137/0222061 · Cited by 162
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
Improved low-degree testing and its applications
Arora, S., & Sudan, M. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258642 · Cited by 150
Self-citationSimulating BPP Using a General Weak Random Source
Zuckerman, D. (1996) · Algorithmica · doi:10.1007/bf01940870 · Cited by 147
Randomness-optimal oblivious sampling
Zuckerman, D. (1997) · Random Structures and Algorithms · Cited by 145
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
Computing with Very Weak Random Sources
Srinivasan, A., & Zuckerman, D. (1999) · SIAM Journal on Computing · doi:10.1137/s009753979630091x · Cited by 85
On Yao's XOR-LemmaPreprint
Goldreich, O., Nisan, N., & Wigderson, A. (1995) · Electronic colloquium on computational complexity · Cited by 80
Construction of extractors using pseudo-random generators (extended abstract)
Trevisan, L. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301289 · Cited by 78
Self-citationCai, J., Pavan, A., & Sivakumar, D. (1999) · Lecture notes in computer science · doi:10.1007/3-540-49116-3_8 · Cited by 70
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-citationReconstructing Algebraic Functions from Mixed Data
Ar, S., Lipton, R. J., Rubinfeld, R., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796297577 · Cited by 59
Self-citationExtractors and pseudo-random generators with optimal seed length
Impagliazzo, R., Shaltiel, R., & Wigderson, A. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335306 · Cited by 58
On the hardness of computing the permanent of random matrices
Feige, U., & Lund, C. (1996) · Computational Complexity · doi:10.1007/bf01262928 · Cited by 53
Vazirani, U. V. (1985) · doi:10.1145/22145.22186 · Cited by 49
On resource-bounded measure and pseudorandomness
Arvind, V., & Köbler, J. (1997) · Lecture notes in computer science · doi:10.1007/bfb0058034 · Cited by 45
How to Reduce your Enemy’s Information (extended abstract)
Bennett, C. H., Gilles Brassard, A., & Robert, J. (2007) · Springer eBooks · doi:10.1007/3-540-39799-x_37 · Cited by 27
Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract)
Cohen, A., & Wigderson, A. (1989) · Cited by 25
Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs
Andreev, A. E., Clementi, A. E. F., & Roli, A. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63165-8_175 · Cited by 24
Constructions of Near-Optimal Extractors Using Pseudo-Random Generators
Trevisan, L. (1998) · Cited by 17
Self-citationValiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Extractors and pseudorandom generators
(2001) · Journal of the ACM · doi:10.1145/502090.502099 · Cited by 324
Self-citationGraph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Klivans, A. R., & van Melkebeek, D. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700389652 · Cited by 270
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
Self-citation
Metadata
- Authors
- Sudan, M., Trevisan, L., & Vadhan, S.
- Venue
- Journal of Computer and System Sciences
- Publisher
- Elsevier BV
- Published
- 2001-03
- Volume
- 62
- Issue
- 2
- Pages
- 236-266
- ISSN
- 0022-0000 (ISSN-L)
- OpenAlex
- W1901622511
- Cited by
- 393
- References
- 49
- FWCI
- 27.71
- Type
- journal article
- Language
- en
- Open access
- bronze
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
