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.
Integrity signals
Registry
Cites
Statistics
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?
Trevisan's extractor is a strong extractor (its seed can be reused) and its seed length is the polylogarithmic function of the input.
“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]
Trevisan's extractor has been proven to be secure against quantum adversaries.
“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]
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 · see citing works
The Theory of Error-Correcting Codes
(1977) · North-Holland mathematical library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,875 · see citing works
Goldwasser, S., & Micali, S. M. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,667 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 977 · see citing works
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 814 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Introduction to Parallel Algorithms and Architectures
(1992) · Elsevier eBooks · doi:10.1016/c2013-0-08299-0 · Cited by 277 · see citing works
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 · see citing works
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 · see citing works
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 270 · see citing works
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 · see citing works
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 · see citing works
Pseudorandom bits for constant depth circuits
Nisan, N. (1991) · COMBINATORICA · doi:10.1007/bf01375474 · Cited by 184 · see citing works
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 · see citing works
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 · see citing works
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 159 · see citing works
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 · see citing works
On Unapproximable Versions of $NP$-Complete Problems
Zuckerman, D. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539794266407 · Cited by 116 · see citing works
Zuckerman, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89574 · Cited by 105 · see citing works
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 · see citing works
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 · see citing works
Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications
Wigderson, A., & Zuckerman, D. (1999) · COMBINATORICA · doi:10.1007/s004930050049 · Cited by 101 · see citing works
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 · see citing works
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 · see citing works
P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma
Impagliazzo, R., & Wigderson, A. (1997) · Cited by 69 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
On Extracting Randomness From Weak Random SourcesPreprint
Ta‐Shma, A. (1995) · Electronic colloquium on computational complexity · Cited by 47 · see citing works
On resource-bounded measure and pseudorandomness
Arvind, V., & Köbler, J. (1997) · Lecture notes in computer science · doi:10.1007/bfb0058034 · Cited by 45 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Ta‐Shma, A. (1998) · doi:10.1145/276698.276736 · Cited by 28 · see citing works
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 · see citing works
Isolation, matching, and counting
Allender, E., & Reinhardt, K. (2002) · doi:10.1109/ccc.1998.694594 · Cited by 10 · see citing works
Flagged first, then by citations
2 of the 49 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,375 · see citing works
The Physics of Quantum Information
Bouwmeester, D., EKERT, A. K., & Zeilinger, A. (2000) · Springer eBooks · doi:10.1007/978-3-662-04209-0 · Cited by 1,988 · see citing works
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 802 · see citing works
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 · see citing works
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 · see citing works
Free randomness can be amplified
Colbeck, R., & Renner, R. (2012) · Nature Physics · doi:10.1038/nphys2300 · Cited by 379 · see citing works
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 376 · see citing works
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 · see citing works
Certified randomness in quantum physics
Acín, A., & Masanes, L. (2016) · Nature · doi:10.1038/nature20119 · Cited by 291 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
List Decoding of Error-Correcting Codes
Guruswami, V. (2005) · Lecture notes in computer science · doi:10.1007/b104335 · Cited by 210 · see citing works
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 · see citing works
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 182 · see citing works
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 · see citing works
Experimentally generated randomness certified by the impossibility of superluminal signals
Bierhorst, P., Knill, E., 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 226 · see citing works
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 174 · see citing works
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 173 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 153 · see citing works
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 · see citing works
Fully device independent quantum key distribution
Vazirani, U. V., & Vidick, T. (2019) · Communications of the ACM · doi:10.1145/3310974 · Cited by 151 · see citing works
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 · see citing works
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 · see citing works
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 114 · see citing works
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 · see citing works
Pseudo-random generators for all hardnesses
Umans, C. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509997 · Cited by 107 · see citing works
Miller, C. A., & Shi, Y. (2016) · Journal of the ACM · doi:10.1145/2885493 · Cited by 103 · see citing works
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 · see citing works
Pseudorandomness and Average-Case Complexity Via Uniform Reductions
Trevisan, L., & Vadhan, S. (2007) · Computational Complexity · doi:10.1007/s00037-007-0233-x · Cited by 96 · see citing works
Self-citationAllender, E., Buhrman, H., Koucký, M., van Melkebeek, D., & Ronneburger, D. (2006) · SIAM Journal on Computing · doi:10.1137/050628994 · Cited by 94 · see citing works
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 · see citing works
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 · see citing works
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 87 · see citing works
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 · see citing works
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 · see citing works
The complexity of constructing pseudorandom generators from hard functions
Viola, E. (2005) · Computational Complexity · doi:10.1007/s00037-004-0187-1 · Cited by 82 · see citing works
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 · see citing works
Hardness Amplification Proofs Require Majority
Shaltiel, R., & Viola, E. (2008) · SIAM Journal on Computing · doi:10.1137/080735096 · Cited by 78 · see citing works
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 · see citing works
Miller, C. A., & Shi, Y. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591843 · Cited by 70 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 62 · see citing works
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 · see citing works
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 61 · see citing works
Self-citationTa‐Shma, A., & Zuckerman, D. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.838377 · Cited by 59 · see citing works
Derandomization in Cryptography
Barak, B., Ong, S. J., & Vadhan, S. (2007) · SIAM Journal on Computing · doi:10.1137/050641958 · Cited by 57 · see citing works
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 · see citing works
Extractors for Circuit Sources
Viola, E. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.20 · Cited by 55 · see citing works
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 · see citing works
Self-citationInvertible 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 · see citing works
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 · see citing works
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 · see citing works
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 46 · see citing works
Noise-resilient group testing: Limitations and constructions
Cheraghchi, M. (2012) · Discrete Applied Mathematics · doi:10.1016/j.dam.2012.07.022 · Cited by 49 · see citing works
Extractors for Low-Weight Affine Sources
Rao, A. (2009) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2009.36 · Cited by 48 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 47 · see citing works
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 45 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 44 · see citing works
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 · see citing works
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 · see citing works
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 40 · see citing works
Extracting Randomness via Repeated Condensing
Reingold, O., Shaltiel, R., & Wigderson, A. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539703431032 · Cited by 39 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Improved Constructions of Three Source Extractors
Li, X. (2011) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2011.26 · Cited by 33 · see citing works
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 33 · see citing works
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 · see citing works
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 · see citing works
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 31 · see citing works
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 30 · see citing works
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 · see citing works
A Primer on Pseudorandom Generators
Goldreich, O. (2010) · University lecture series · doi:10.1090/ulect/055 · Cited by 30 · see citing works
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 · see citing works
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 · see citing works
- 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 › Computer Science › Artificial Intelligence › 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
