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.

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.

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?

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
Probabilistic encryption
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
Hardness vs randomness
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

Show all 49 references

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

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
Free randomness can be amplified
Colbeck, R., & Renner, R. (2012) · Nature Physics · doi:10.1038/nphys2300 · Cited by 379
Private randomness expansion with untrusted devices
Colbeck, R., & Kent, A. (2011) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/44/9/095305 · Cited by 379
Leftover Hashing Against Quantum Side Information
Tomamichel, M., Schaffner, C., Smith, A., & Renner, R. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2158473 · Cited by 303
Certified randomness in quantum physics
Acín, A., & Masanes, L. (2016) · Nature · doi:10.1038/nature20119 · Cited by 307
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
Guruswami, V., Umans, C., & Vadhan, S. (2009) · Journal of the ACM · doi:10.1145/1538902.1538904 · Cited by 279
Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors
Cramer, R., Dodis, Y., Fehr, S., Padró, C., & Wichs, D. (2008) · Springer eBooks · doi:10.1007/978-3-540-78967-3_27 · Cited by 262
Ultrafast quantum random number generation based on quantum phase fluctuations
Xu, F., Qi, B., Ma, X., Xu, H., Zheng, H., & Lo, H.-K. (2012) · Optics Express · doi:10.1364/oe.20.012366 · Cited by 228
Randomness conductors and constant-degree lossless expanders
Capalbo, M., Reingold, O., Vadhan, S., & Wigderson, A. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.510003 · Cited by 220
List Decoding of Error-Correcting Codes
Guruswami, V. (2005) · Lecture notes in computer science · doi:10.1007/b104335 · Cited by 224
Experimentally generated randomness certified by the impossibility of superluminal signals
Bierhorst, P., Knill, E. H., Glancy, S., Zhang, Y., Mink, A., Jordan, S. P., Rommal, A., Liu, Y.-K., Christensen, B., Nam, S. W., et al. (2018) · RePEc: Research Papers in Economics · Cited by 190
Quantum randomness certified by the uncertainty principle
Vallone, G., Marangon, D. G., Tomasin, M., & Villoresi, P. (2014) · Physical Review A · doi:10.1103/physreva.90.052327 · Cited by 189
Authenticated Key Exchange from Ideal Lattices
Zhang, J., Zhang, Z., Ding, J., Snook, M., & Dagdelen, Ö. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46803-6_24 · Cited by 184
Experimentally generated randomness certified by the impossibility of superluminal signals
Bierhorst, P., Knill, E. H., Glancy, S., Zhang, Y., Mink, A., Jordan, S. P., Rommal, A., Liu, Y.-K., Christensen, B., Nam, S. W., et al. (2018) · Nature · doi:10.1038/s41586-018-0019-0 · Cited by 242
Memory Attacks on Device-Independent Quantum Cryptography
Barrett, J., Colbeck, R., & Kent, A. (2013) · Physical Review Letters · doi:10.1103/physrevlett.110.010503 · Cited by 172
Quantum key distribution with entangled photons generated on demand by a quantum dot
Basset, F. B., Valeri, M., Roccia, E., Muredda, V., Poderini, D., Neuwirth, J., Spagnolo, N., Rota, M. B., Carvacho, G., Sciarrino, F., et al. (2021) · Science Advances · doi:10.1126/sciadv.abe6379 · Cited by 185
Trevisan's Extractor in the Presence of Quantum Side Information
De, A., Portmann, C., Vidick, T., & Renner, R. (2012) · SIAM Journal on Computing · doi:10.1137/100813683 · Cited by 161
Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model
Vadhan, S. (2003) · Journal of Cryptology · doi:10.1007/s00145-003-0237-x · Cited by 155
Position Based Cryptography
Chandran, N., Goyal, V., Moriarty, R., & Ostrovsky, R. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03356-8_23 · Cited by 154
Source-Independent Quantum Random Number Generation
Cao, Z., Zhou, H., Yuan, X., & Ma, X. (2016) · Physical Review X · doi:10.1103/physrevx.6.011020 · Cited by 155
Simple extractors for all min-entropies and a new pseudorandom generator
Shaltiel, R., & Umans, C. (2005) · Journal of the ACM · doi:10.1145/1059513.1059516 · Cited by 153
Fully device independent quantum key distribution
Vazirani, U. V., & Vidick, T. (2019) · Communications of the ACM · doi:10.1145/3310974 · Cited by 156
Explicit two-source extractors and resilient functions
Chattopadhyay, E., & Zuckerman, D. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897528 · Cited by 131
Boosting textual compression in optimal linear time
Ferragina, P., Giancarlo, R., Manzini, G., & Sciortino, M. (2005) · Journal of the ACM · doi:10.1145/1082036.1082043 · Cited by 125
Randomness in quantum mechanics: philosophy, physics and technology
Bera, M. N., Acín, A., Kuś, M., Mitchell, M. W., & Lewenstein, M. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa8731 · Cited by 122
Extractors
Lu, C.-J., Reingold, O., Vadhan, S., & Wigderson, A. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780630 · Cited by 108
Pseudo-random generators for all hardnesses
Umans, C. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509997 · Cited by 107
Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices
Miller, C. A., & Shi, Y. (2016) · Journal of the ACM · doi:10.1145/2885493 · Cited by 122
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
Cheraghchi, M., Guruswami, V., & Velingker, A. (2012) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 99
Pseudorandomness and Average-Case Complexity Via Uniform Reductions
Trevisan, L., & Vadhan, S. (2007) · Computational Complexity · doi:10.1007/s00037-007-0233-x · Cited by 100
Self-citation
Power from Random Strings
Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., & Ronneburger, D. (2006) · SIAM Journal on Computing · doi:10.1137/050628994 · Cited by 94
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes
Guruswami, V., Umans, C., & Vadhan, S. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.38 · Cited by 91
An Introduction to Randomness Extractors
Shaltiel, R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22012-8_2 · Cited by 90
Quantum generators of random numbers
Jacak, M. M., Jóźwiak, P. P., Niemczuk, J., & Jacak, J. E. (2021) · Scientific Reports · doi:10.1038/s41598-021-95388-7 · Cited by 93
Non-malleable extractors and codes, with their many tampered extensions
Chattopadhyay, E., Goyal, V., & Li, X. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897547 · Cited by 85
More Efficient Privacy Amplification With Less Random Seeds via Dual Universal Hash Function
Hayashi, M., & Tsurumaru, T. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2526018 · Cited by 84
The complexity of constructing pseudorandom generators from hard functions
Viola, E. (2005) · Computational Complexity · doi:10.1007/s00037-004-0187-1 · Cited by 82
Certifiable quantum dice: or, true random number generation secure against quantum adversaries
Vazirani, U., & Vidick, T. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2213984 · Cited by 80
“A.1 The t-XOR extractor The t-XOR extractor Et, parametrized by an integer t, follows Trevisan s general construction paradigm [29].”
BackgroundMethodInfluential
Hardness Amplification Proofs Require Majority
Shaltiel, R., & Viola, E. (2008) · SIAM Journal on Computing · doi:10.1137/080735096 · Cited by 78
Derandomizing Arthur–Merlin Games using Hitting Sets
Miltersen, P. B., & Vinodchandran, N. V. (2005) · Computational Complexity · doi:10.1007/s00037-005-0197-7 · Cited by 76
Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices
Miller, C. A., & Shi, Y. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591843 · Cited by 72
Encryption against Storage-Bounded Adversaries from On-Line Strong Extractors
Lu, C.-J. (2003) · Journal of Cryptology · doi:10.1007/s00145-003-0217-1 · Cited by 70
Derandomization in Cryptography
Barak, B., Ong, S. J., & Vadhan, S. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45146-4_18 · Cited by 69
Quantifying Resources in General Resource Theory with Catalysts
Anshu, A., Hsieh, M.-H., & Jain, R. (2018) · Physical Review Letters · doi:10.1103/physrevlett.121.190504 · Cited by 64
Dual Projective Hashing and Its Applications — Lossy Trapdoor Functions and More
Wee, H. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29011-4_16 · Cited by 62
Pseudo-random generators for all hardnesses
Umans, C. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00046-1 · Cited by 66
Experimental Low-Latency Device-Independent Quantum Randomness
Zhang, Y., Shalm, L. K., Bienfang, J. C., Stevens, M. J., Mazurek, M. D., Nam, S. W., Abellán, C., Amaya, W., Mitchell, M. W., Fu, H., et al. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.010505 · Cited by 69
Secure Wireless Communication with Dynamic Secrets
Xiao, S., Gong, W., & Towsley, D. (2010) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2010.5461974 · Cited by 62
Pseudorandomness and average-case complexity via uniform reductions
Trevisan, L., & Vadhan, S. (2003) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2002.1004348 · Cited by 62
Self-citation
Extractor Codes
Ta‐Shma, A., & Zuckerman, D. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.838377 · Cited by 59
Derandomization in Cryptography
Barak, B., Ong, S. J., & Vadhan, S. (2007) · SIAM Journal on Computing · doi:10.1137/050641958 · Cited by 57
Extractors for a constant number of polynomially small min-entropy independent sources
Rao, A. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132589 · Cited by 56
Extractors for Circuit Sources
Viola, E. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.20 · Cited by 55
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Gopalan, P., Meka, R., Reingold, O., Trevisan, L., & Vadhan, S. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.77 · Cited by 54
Self-citation
Invertible Extractors and Wiretap Protocols
Cheraghchi, M., Didier, F., & Shokrollahi, A. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2170660 · Cited by 52
Noise-Resilient Group Testing: Limitations and Constructions
Cheraghchi, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03409-1_7 · Cited by 52
SoK: Distributed Randomness Beacons
Choi, K. K., Manoj, A., & Bonneau, J. (2023) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46215.2023.10179419 · Cited by 50
Strong experimental guarantees in ultrafast quantum random number generation
Mitchell, M. W., Abellán, C., & Amaya, W. (2015) · Physical Review A · doi:10.1103/physreva.91.012314 · Cited by 48
Noise-resilient group testing: Limitations and constructions
Cheraghchi, M. (2012) · Discrete Applied Mathematics · doi:10.1016/j.dam.2012.07.022 · Cited by 49
Extractors for Low-Weight Affine Sources
Rao, A. (2009) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2009.36 · Cited by 48
2-source dispersers for n^o(1) entropy, and Ramsey graphs beating the Frankl-Wilson construction
Barak, B., Rao, A., Shaltiel, R., & Wigderson, A. (2012) · Annals of Mathematics · doi:10.4007/annals.2012.176.3.3 · Cited by 48
On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model
Vadhan, S. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45146-4_4 · Cited by 48
Deterministic extractors for small-space sources
Kamp, J., Rao, A., Vadhan, S., & Zuckerman, D. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132613 · Cited by 48
Non-Black-Box Worst-Case to Average-Case Reductions within NP
Hirahara, S. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00032 · Cited by 47
A New Approach to Affine Extractors and Dispersers
Li, X. (2011) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2011.27 · Cited by 47
A Framework for Quantum-Secure Device-Independent Randomness Expansion
Brown, P. J., Ragy, S., & Colbeck, R. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2960252 · Cited by 53
Efficient randomness certification by quantum probability estimation
Zhang, Y., Fu, H., & Knill, E. H. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.013016 · Cited by 49
Extractors from Reed–Muller codes
Ta‐Shma, A., Zuckerman, D., & Safra, M. (2006) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2005.05.010 · Cited by 47
Non-malleable Extractors, Two-Source Extractors and Privacy Amplification
Li, X. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.26 · Cited by 46
True randomness from realistic quantum devicesPreprint
Frauchiger, D., Renner, R., & Troyer, M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.4547 · Cited by 46
Robustness of quantum-randomness expansion protocols in the presence of noise
Mironowicz, P., & Pawłowski, M. (2013) · Physical Review A · doi:10.1103/physreva.88.032319 · Cited by 45
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
Fortnow, L., Hitchcock, J. M., Pavan, A., Vinodchandran, N. V., & Wang, F. (2006) · Lecture notes in computer science · doi:10.1007/11786986_30 · Cited by 44
Daylight entanglement-based quantum key distribution with a quantum dot source
Basset, F. B., Valeri, M., Neuwirth, J., Polino, E., Rota, M. B., Poderini, D., Pardo, C., Rodari, G., Roccia, E., da Silva, S. F. C., et al. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/acae3d · Cited by 44
Physical Randomness Extractors: Generating Random Numbers with Minimal AssumptionsPreprint
Chung, K.-M., Shi, Y., & Wu, X. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.4797 · Cited by 73
Extracting Randomness via Repeated Condensing
Reingold, O., Shaltiel, R., & Wigderson, A. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539703431032 · Cited by 39
New Constructions of WOM Codes Using the Wozencraft Ensemble
Shpilka, A. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2251455 · Cited by 38
Leftover Hashing against quantum side information
Tomamichel, M., Renner, R., Schaffner, C., & Smith, A. (2010) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2010.5513652 · Cited by 38
2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness
Kalai, Y. T., Li, X., & Rao, A. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.61 · Cited by 38
Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
Rao, A. (2009) · SIAM Journal on Computing · doi:10.1137/060671218 · Cited by 37
A Lower Bound on List Size for List Decoding
Guruswami, V., & Vadhan, S. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2070170 · Cited by 37
One-Way Permutations, Interactive Hashing and Statistically Hiding Commitments
Wee, H. (2007) · Springer eBooks · doi:10.1007/978-3-540-70936-7_23 · Cited by 37
Deterministic extractors for small-space sources
Kamp, J., Rao, A., Vadhan, S., & Zuckerman, D. (2010) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2010.06.014 · Cited by 36
40 Gb/s quantum random number generation based on optically sampled amplified spontaneous emission
Guo, Y., Cai, Q., Li, P., Jia, Z., Xu, B., Zhang, Q., Zhang, Y., Zhang, R., Gao, Z., Shore, K. A., et al. (2021) · APL Photonics · doi:10.1063/5.0040250 · Cited by 36
Hyper-encryption against Space-Bounded Adversaries from On-Line Strong Extractors
Lu, C.-J. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45708-9_17 · Cited by 36
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification
Impagliazzo, R., Jaiswal, R., & Kabanets, V. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.13 · Cited by 36
On the distribution of the number of roots of polynomials and explicit weak designs
Hartman, T., & Raz, R. (2003) · Random Structures and Algorithms · doi:10.1002/rsa.10095 · Cited by 34
Improved Constructions of Three Source Extractors
Li, X. (2011) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2011.26 · Cited by 33
A simple low-latency real-time certifiable quantum random number generator
Zhang, Y., Lo, H.-P., Mink, A., Ikuta, T., Honjo, T., Takesue, H., & Munro, W. J. (2021) · Nature Communications · doi:10.1038/s41467-021-21069-8 · Cited by 37
Certifiable Quantum Dice - Or, testable exponential randomness expansionPreprint
Vazirani, U. V., & Vidick, T. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.6054 · Cited by 33
Non-malleable codes and extractors for small-depth circuits, and affine functions
Chattopadhyay, E., & Li, X. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055483 · Cited by 32
Experimental device-independent certified randomness generation with an instrumental causal structure
Agresti, I., Poderini, D., Guerini, L., Mancusi, M., Carvacho, G., Aolita, L., Cavalcanti, D., Chaves, R., & Sciarrino, F. (2020) · Communications Physics · doi:10.1038/s42005-020-0375-6 · Cited by 34
Certifying quantum randomness by probability estimation
Zhang, Y., Knill, E. H., & Bierhorst, P. (2018) · Physical Review A · doi:10.1103/physreva.98.040304 · Cited by 34
A Quantum Random Number Generator Based on the 100-Mbit/s Poisson Photocount Statistics
Balygin, K. A., Zaitsev, V. Y., Klimov, A. N., Kulik, S. P., & Molotkov, S. N. (2018) · Journal of Experimental and Theoretical Physics · doi:10.1134/s1063776118060018 · Cited by 29
A Primer on Pseudorandom Generators
Goldreich, O. (2010) · University lecture series · doi:10.1090/ulect/055 · Cited by 30
Robust, low-cost, auditable random number generation for embedded system security
Lampert, B., Wahby, R. S., Leonard, S., & Levis, P. (2016) · Proceedings of the 14th ACM Conference on Embedded Networked Sensor Systems CD-ROM · doi:10.1145/2994551.2994568 · Cited by 27
Computational Extractors and Pseudorandomness
Dachman-Soled, D., Gennaro, R., Krawczyk, H., & Malkin, T. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28914-9_22 · Cited by 27

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

Extractors and pseudorandom generators

Abstract

Overview

Integrity signals

Verification

Claims the paper makes

Claims other papers make about this one

Citations

Cites

Cited by

Related

Metadata

Record

About these checks