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
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
Items 101–200 of 322
Shakhovoy, R., Васильевич, С. Д., Sharoglazova, V., Udaltsov, A., Fedorov, A. K., & Kurochkin, Y. (2020) · Optics Express · doi:10.1364/oe.380156 · Cited by 27
The unified theory of pseudorandomness
Vadhan, S. (2007) · ACM SIGACT News · doi:10.1145/1324215.1324225 · Cited by 27
Near-optimal extractors against quantum storage
De, A., & Vidick, T. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806713 · Cited by 26
Randomness and dependencies extraction via polarization
Abbe, E. A. (2011) · Information Theory and Applications Workshop (ITA) · doi:10.1109/ita.2011.5743556 · Cited by 25
Dispersers for Affine Sources with Sub-polynomial Entropy
Shaltiel, R. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.37 · Cited by 24
Restricted isometry of fourier matrices and list decodability of random linear codes
Cheraghchi, M., Guruswami, V., & Velingker, A. (2013) · Symposium on Discrete Algorithms · doi:10.5555/2627817.2627848 · Cited by 24
Bootstrapping results for threshold circuits “just beyond” known lower bounds
Chen, L., & Tell, R. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316333 · Cited by 24
Short seed extractors against quantum storage
Ta‐Shma, A. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536470 · Cited by 24
Improved bounds for universal one-bit compressive sensing
Acharya, J., Bhattacharyya, A., & Kamath, P. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006950 · Cited by 24
Design extractors, non-malleable condensers and privacy amplification
Li, X. (2012) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2213977.2214052 · Cited by 23
On derandomizing algorithms that err extremely rarely
Goldreich, O., & Widgerson, A. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591808 · Cited by 22
On Medium-Uniformity and Circuit Lower Bounds
Santhanam, R., & Williams, R. (2013) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2013.40 · Cited by 23
Extractors and Lower Bounds for Locally Samplable Sources
De, A., & Watson, T. W. (2012) · ACM Transactions on Computation Theory · doi:10.1145/2141938.2141941 · Cited by 22
Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., & Ronneburger, D. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181992 · Cited by 22
Experimental study of a quantum random-number generator based on two independent lasers
Sun, S., & Xu, F. (2017) · Physical Review A · doi:10.1103/physreva.96.062314 · Cited by 19
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
Cheraghchi, M., Guruswami, V., & Velingker, A. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973105.31 · Cited by 20
Hardness as randomness: a survey of universal derandomizationPreprint
Impagliazzo, R. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0304040 · Cited by 20
Certified Randomness from Quantum Supremacy
Aaronson, S., & Hung, S.-H. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585145 · Cited by 38
Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors
Gabizon, A., & Shaltiel, R. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32512-0_47 · Cited by 19
Quantified derandomization of linear threshold circuits
Tell, R. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188822 · Cited by 19
Tsurumaru, T. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.2969656 · Cited by 19
Limitations of Hardness vs. Randomness under Uniform Reductions
Gutfreund, D., & Vadhan, S. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85363-3_37 · Cited by 19
Reducing The Seed Length In The Nisan-Wigderson Generator*
Impagliazzo, R., Shaltiel, R., & Wigderson, A. (2006) · COMBINATORICA · doi:10.1007/s00493-006-0036-8 · Cited by 19
Better extractors for better codes?
Guruswami, V. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007422 · Cited by 19
Nearly Optimal Pseudorandomness from Hardness
Doron, D., Moshkovitz, D., Oh, J., & Zuckerman, D. (2022) · Journal of the ACM · doi:10.1145/3555307 · Cited by 18
Quantum Random Number Generation
Kollmitzer, C., Schauer, S., Raß, S., & Rainer, B. (2020) · Quantum science and technology · doi:10.1007/978-3-319-72596-3 · Cited by 22
Resource bounded symmetry of information revisited
Lee, T., & Romashchenko, A. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.07.017 · Cited by 18
Language compression and pseudorandom generators
Buhrman, H., Lee, T., & van Melkebeek, D. (2005) · Computational Complexity · doi:10.1007/s00037-005-0199-5 · Cited by 18
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
Impagliazzo, R., Jaiswal, R., & Kabanets, V. (2009) · SIAM Journal on Computing · doi:10.1137/070683994 · Cited by 17
Non-interactive Timestamping in the Bounded-Storage Model
Moran, T., Shaltiel, R., & Ta‐Shma, A. (2009) · Journal of Cryptology · doi:10.1007/s00145-008-9035-9 · Cited by 17
Completely device-independent quantum key distribution
Aguilar, E. A., Ramanathan, R., Kofler, J., & Pawłowski, M. (2016) · Physical Review A · doi:10.1103/physreva.94.022305 · Cited by 17
Local List Recovery of High-Rate Tensor Codes and Applications
Hemenway, B., Ron‐Zewi, N., & Wootters, M. K. (2019) · SIAM Journal on Computing · doi:10.1137/17m116149x · Cited by 16
Practical randomness amplification and privatisation with implementations on quantum computers
Foreman, C., Wright, S., Edgington, A., Berta, M., & Curchod, F. J. (2023) · Quantum · doi:10.22331/q-2023-03-30-969 · Cited by 20
On Uniformity and Circuit Lower Bounds
Santhanam, R., & Williams, R. (2014) · Computational Complexity · doi:10.1007/s00037-014-0087-y · Cited by 15
Nonmalleable Extractors and Codes, with Their Many Tampered Extensions
Chattopadhyay, E., Goyal, V., & Li, X. (2020) · SIAM Journal on Computing · doi:10.1137/18m1176622 · Cited by 15
Pseudorandomness and combinatorial constructions
Trevisan, L. (2007) · Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006 · doi:10.4171/022-3/54 · Cited by 15
Self-citationA Lower Bound on List Size for List Decoding
Guruswami, V., & Vadhan, S. (2005) · Lecture notes in computer science · doi:10.1007/11538462_27 · Cited by 15
Pseudorandom Generators and Typically-Correct Derandomization
Kinne, J., van Melkebeek, D., & Shaltiel, R. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03685-9_43 · Cited by 14
THE PHYSICS OF QUANTUM INFORMATION: COMPLEMENTARITY, UNCERTAINTY, AND ENTANGLEMENT
Renes, J. M. (2013) · International Journal of Quantum Information · doi:10.1142/s0219749913300027 · Cited by 14
Buresh-Oppenheim, J., & Santhanam, R. (2006) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2006.26 · Cited by 14
Nearly Optimal Pseudorandomness From Hardness
Doron, D., Moshkovitz, D., Oh, J., & Zuckerman, D. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00102 · Cited by 14
Lecture Notes on Computational Complexity
Trevisan, L. (2004) · Cited by 16
Self-citationCertified random-number generation from quantum steering
Joch, D. J., Slussarenko, S., Wang, Y., Pepper, A., Xie, S., Xu, B.-B., Berkman, I. R., Rogge, S. M. J., & Pryde, G. J. (2022) · Physical Review A · doi:10.1103/physreva.106.l050401 · Cited by 16
Polarization and randomness extraction
Abbe, E. A. (2011) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2011.6033870 · Cited by 13
A framework for quantum-secure device-independent randomness expansion
Brown, P. J., Ragy, S., & Colbeck, R. (2020) · White Rose Research Online (University of Leeds, The University of Sheffield, University of York) · Cited by 13
Hardness vs. randomness within alternating time
Viola, E. (2004) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2003.1214410 · Cited by 13
Invertible extractors and wiretap protocols
Cheraghchi, M., Didier, F., & Shokrollahi, A. (2009) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2009.5205583 · Cited by 12
Efficient methods for one-shot quantum communication
Anshu, A., & Jain, R. (2022) · npj Quantum Information · doi:10.1038/s41534-022-00608-1 · Cited by 17
Short Leakage Resilient and Non-malleable Secret Sharing Schemes
Chandran, N., Kanukurthi, B., Obbattu, S. L. B., & Sekar, S. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-15802-5_7 · Cited by 12
Better lossless condensers through derandomized curve samplers
Ta‐Shma, A., & Umans, C. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.18 · Cited by 12
Chattopadhyay, E., & Li, X. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897643 · Cited by 12
List Decoding Barnes-Wall Lattices
Grigorescu, E., & Peikert, C. (2012) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2012.33 · Cited by 12
How NP got a new definition: a survey of probabilistically checkable proofsPreprint
Arora, S. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0304038 · Cited by 12
Traceable random numbers from a non-local quantum advantage
Kavuri, G. A., Palfree, J., Reddy, D. V., Zhang, Y., Bienfang, J. C., Mazurek, M. D., Alhejji, M. A., Siddiqui, A. U., Cavanagh, J., Dalal, A., et al. (2025) · Nature · doi:10.1038/s41586-025-09054-3 · Cited by 21
Minimalist design of a robust real-time quantum random number generator
Kravtsov, K., Radchenko, I. V., Kulik, S. P., & Molotkov, S. N. (2015) · Journal of the Optical Society of America B · doi:10.1364/josab.32.001743 · Cited by 11
Quantum Random Number Generation Based on Quantum Phase Noise
Tang, G., Jiang, M.-S., Sun, S., Ma, X.-C., Li, C., & Liang, L.-M. (2013) · Chinese Physics Letters · doi:10.1088/0256-307x/30/11/114207 · Cited by 11
Quantum-Proof Multi-Source Randomness Extractors in the Markov Model
Arnon-Friedman, R., Portmann, C., & Scholz, V. B. (2016) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.3929/ethz-b-000121403 · Cited by 11
Chandran, N., Goyal, V., Moriarty, R., & Ostrovsky, R. (2014) · SIAM Journal on Computing · doi:10.1137/100805005 · Cited by 11
The Unified Theory of Pseudorandomness
Vadhan, S. (2011) · International Congress of Mathematicians (ICM) · doi:10.1142/9789814324359_0165 · Cited by 11
Applications of Derandomization Theory in CodingPreprint
Cheraghchi, M. (2010) · arXiv (Cornell University) · doi:10.5075/epfl-thesis-4767 · Cited by 11
Average Case Lower Bounds for Monotone Switching Networks
Filmus, Y., Pitassi, T., Robere, R., & Cook, S. A. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.70 · Cited by 10
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP
Arvind, V., & Torán, J. (2011) · ACM Transactions on Computation Theory · doi:10.1145/1944857.1944859 · Cited by 10
Implementation of a quantum random number generator based on the optimal clustering of photocounts
Balygin, K. A., Zaitsev, V. Y., Klimov, A. N., Kulik, S. P., & Molotkov, S. N. (2017) · Journal of Experimental and Theoretical Physics Letters · doi:10.1134/s0021364017190043 · Cited by 10
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
Chen, L., & Ren, H. (2022) · SIAM Journal on Computing · doi:10.1137/20m1364886 · Cited by 12
Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time
Zimand, M. (2008) · Computational Complexity · doi:10.1007/s00037-008-0243-3 · Cited by 10
Multi-Source Randomness Extractors Against Quantum Side Information, and their ApplicationsPreprint
Chung, K.-M., Li, X., & Wu, X. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.2315 · Cited by 10
Bicorn: An Optimistically Efficient Distributed Randomness Beacon
Choi, K. K., Arun, A., Tyagi, N., & Bonneau, J. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-47754-6_14 · Cited by 9
New concepts and construction of quantum random number generators
Jóźwiak, P. P., Jacak, J. E., & Jacak, W. A. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04335-8 · Cited by 10
Capacity Achieving Two-Write WOM Codes
Shpilka, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29344-3_53 · Cited by 9
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
Tell, R. (2019) · Computational Complexity · doi:10.1007/s00037-019-00179-2 · Cited by 9
Near-Optimal Erasure List-Decodable Codes
Ben-Aroya, A., Doron, D., & Ta‐Shma, A. (2020) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ccc.2020.1 · Cited by 9
Two-Source Extractors Secure against Quantum Adversaries
Kasher, R., & Kempe, J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15369-3_49 · Cited by 9
Locally testable codes via high-dimensional expandersPreprint
Dikstein, Y., Dinur, I., Harsha, P., & Ron‐Zewi, N. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.01045 · Cited by 9
Bounds on semi-device-independent quantum random-number expansion capabilities
Mannalath, V., & Pathak, A. (2022) · Physical Review A · doi:10.1103/physreva.105.022435 · Cited by 8
Characterization of Real-Life PRNGs under Partial State Corruption
Cornejo, M., & Ruhault, S. (2014) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2660267.2660377 · Cited by 8
Affine Extractors for Almost Logarithmic Entropy
Chattopadhyay, E., Goodman, J., & Liao, J.-J. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs52979.2021.00067 · Cited by 8
Better short-seed quantum-proof extractors
Ben-Aroya, A., & Ta‐Shma, A. (2011) · Theoretical Computer Science · doi:10.1016/j.tcs.2011.11.036 · Cited by 8
Short Seed Extractors against Quantum Storage
Ta‐Shma, A. (2011) · SIAM Journal on Computing · doi:10.1137/09076787x · Cited by 8
On Derandomizing Probabilistic Sublinear-Time Algorithms
Zimand, M. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.19 · Cited by 8
Zimand, M. (2006) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2006.19 · Cited by 8
Simple Extractors via Constructions of Cryptographic Pseudo-random Generators
Zimand, M. (2005) · Lecture notes in computer science · doi:10.1007/11523468_10 · Cited by 8
Seed Renewable Parallel and Real-Time Toeplitz Post-Processing for QRNG
Lin, F., Ge, W., Song, Z., Cui, X., Guo, Y., Guo, X., & Xiao, L. (2024) · Journal of Lightwave Technology · doi:10.1109/jlt.2024.3445327 · Cited by 7
List-Decoding Barnes–Wall Lattices
Grigorescu, E., & Peikert, C. (2017) · Computational Complexity · doi:10.1007/s00037-016-0151-x · Cited by 7
Capacity achieving codes From randomness conductors
Cheraghchi, M. (2009) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2009.5205931 · Cited by 7
Derandomization and group testing
Cheraghchi, M. (2010) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2010.5707017 · Cited by 7
Continuous-variable random-number generation from an amplified spontaneous emission light source
Tomaru, T. (2020) · Applied Optics · doi:10.1364/ao.386855 · Cited by 7
Cryptography from One-Way Communication: On Completeness of Finite Channels
Agrawal, S., Ishai, Y., Eyal Kushilevitz, Z., Narayanan, V., Prabhakaran, M., Prabhakaran, V. M., & Rosen, A. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-64840-4_22 · Cited by 7
Deterministic Extractors for Independent-Symbol Sources
Lee, C.-J., Lu, C.-J., & Tsai, S. (2006) · Lecture notes in computer science · doi:10.1007/11786986_9 · Cited by 7
Cryptomite: A versatile and user-friendly library of randomness extractors
Foreman, C., Yeung, R., Edgington, A., & Curchod, F. J. (2025) · Quantum · doi:10.22331/q-2025-01-08-1584 · Cited by 11
The complexity of the matroid–greedoid partition problem
Asodi, V., & Umans, C. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.11.019 · Cited by 6
Tight bounds for monotone switching networks via fourier analysis
Chan, S. M., & Potechin, A. H. (2012) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2213977.2214024 · Cited by 6
Secret Sharing with Binary Shares
Lin, F., Cheraghchi, M., Guruswami, V., Safavi–Naini, R., & Wang, H. (2018) · DR-NTU (Nanyang Technological University) · doi:10.4230/lipics.itcs.2019.53 · Cited by 6
The m -least significant bits operation for quantum random number generation
Chen, Z., Li, Z., Xu, B., Zhang, Y., & Guo, H. (2019) · Journal of Physics B Atomic Molecular and Optical Physics · doi:10.1088/1361-6455/ab3c01 · Cited by 7
Fan, Z., Li, J., & Yang, T. (2022) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3519935.3520010 · Cited by 6
Extractors Using Hardness Amplification
De, A., & Trevisan, L. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03685-9_35 · Cited by 6
Self-citationMusatov, D. (2012) · Theory of Computing Systems · doi:10.1007/s00224-012-9432-1 · Cited by 6
Pseudorandomness When the Odds are Against You
Artemenko, S., Impagliazzo, R., Kabanets, V., & Shaltiel, R. (2016) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ccc.2016.9 · Cited by 6
Chattopadhyay, E., & Li, X. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-64381-2_21 · Cited by 6
Pseudorandom Generators: A Primer
Goldreich, O. (2008) · Cited by 7
The Complexity of Entangled Games
Vidick, T. (2011) · eScholarship (California Digital Library) · Cited by 10
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
