Papers and Talks
Randomness Extractors and Applications
Other Pseudorandomness and Explicit Constructions
Coding Theory and Curve Fitting
Cryptography, Distributed Computing, and Security
Other Computational Complexity
Random Walks on Graphs
Randomized Algorithms
Finance
Expository
 The Space Complexity of Sampling
Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman
ITCS 2022
 Nearly Optimal Pseudorandomness From Hardness
Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
FOCS 2020
 Extractors and Secret Sharing Against Bounded Collusion Protocols
(merger of these two)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, and David Zuckerman
FOCS 2020
 XOR Lemmas for Resilient Functions Against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
STOC 2020
 Simple Optimal Hitting Sets for SmallSuccess RL
William Hoza and David Zuckerman
Video: Princeton Theory Lunch
SIAM Journal on Computing, 2020
FOCS 2018, preliminary version
 Explicit TwoSource Extractors and Resilient Functions
Eshan Chattopadhyah and David Zuckerman
Annals of Mathematics, 2019
STOC 2016 Best Paper Award
Video: TCS+ 2015
 Survey talks:
 Extractors and Expanders, Four Part Tutorial
David Zuckerman
Video: Simons Institute Pseudorandomness Boot Camp, 2017
 Randomness Extraction: A Survey
David Zuckerman
Video: Institute for Advanced Study, 2012
Slides: Given at the satellite preworkshop of the ELC Tokoyo Complexity Workshop. This is an extended version of earleir talks given at Rutgers University, 2012; the Institute for Advacned Study, 2012; and the IPAM Workshop Mathematics of InformationTheoretic Cryptography, 2012.
For a more detailed introduction to extractors and other aspects of pseudorandomness, see Salil Vadhan's book Pseudorandomness.
 Original Research:
 Extractors and Secret Sharing Against Bounded Collusion Protocols
(merger of these two)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, and David Zuckerman
FOCS 2020
 Improved Extractors for Recognizable and Algebraic Sources
Fu Li and David Zuckerman
RANDOM 2019
 Explicit TwoSource Extractors and Resilient Functions
Eshan Chattopadhyah and David Zuckerman
Annals of Mathematics, 2019
STOC 2016 Best Paper Award
Video: TCS+ 2015
 New Extractors for Interleaved Sources
Eshan Chattopadhyay and David Zuckerman
CCC 2016
 Deterministic Extractors for Additive Sources
Abhishek Bhowmick, Ariel Gabizon, Thai Hoang Le, and David Zuckerman
ITCS 2015
 NonMalleable Codes Against Constant SplitState Teampering
Eshan Chattopadhyay and David Zuckerman
Video: Simons Workshop on Coding: From Practice to Theory, 2015
Also under Coding Theory.
 Privacy Amplification and NonMalleable Extractors Via Character Sums
Yevgeniy Dodis, Xin Li, Trevor D. Wooley, and David Zuckerman
Slides: Given at UT Austin, modified from earlier versions given at Rutgers University and Princeton University, 2011.
SIAM Journal on Computing, 2014
FOCS 2011, preliminary version
 Network Extractor Protocols
Yael Tauman Kalai, Xin Li, Anup Rao, and David Zuckerman
FOCS 2008
 Extractors for Three UnevenLength Sources
Anup Rao and David Zuckerman
RANDOM 2008
 Deterministic Extractors for Small Space Sources
Jesse Kamp, Anup Rao, Salil Vadhan, and David Zuckerman
Slides: Given at the 2006 Banff Workshop on Recent Advances in Computational Complexity(modified from version given at SIAM Conference on Discrete Mathematics 2006).
JCSS 2011
STOC 2006, preliminary version
 Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
David Zuckerman
Slides: Modified from the version given at IBM/NYU/Columbia Theory Day, STOC 2006, and elsewhere.
Theory of Computing, 2007
STOC 2006, preliminary version
 Deterministic Extractors for bitFixing Sources and ExposureResilient Cryptography
Jesse Kamp and David Zuckerman
SIAM Journal on Computing, 2006
FOCS 2003, preliminary version
 Extractors from ReedMuller Codes
Amnon TaShma, David Zuckerman, and Shmuel Safra
JCSS 2006
FOCS 2001
 Extractor Codes
Amnon TaShma and David Zuckerman
IEEE Transactions on Information Theory, 2004
STOC 2001
 Lossless Condensers, Unbalanced Expanders, and Extractors
Amnon TaShma, Christopher Umans, and David Zuckerman
Combinatorica 2007
STOC 2001, preliminary version
 Some Successes and Failures of Algebra in Constructing Extractors
David Zuckerman
Slides: 2004, given at the IPAM Workshop on Automorphic Forms, Group Theory and Graph Expansion.
 Computational Complexity and Entropy
David Zuckerman
Slides: 2001, given at the DIMACS Workshop on Computational Complexity, Entropy, and Statistical Physics
 Another proof that BPP\subseteq PH (and more)
Oded Goldreich and David Zuckerman
ECCC 1997
 RandomnessOptimal Oblivious Sampling
David Zuckerman
Random Structures and Algorithms, 1997
STOC 1996, prelimnary version: "RandomnessOptimal Sampling, Extractors, and Constructive Leader Election"
 Computing With Very Weak Random Sources
Aravind Srinivasan and David Zuckerman
SIAM Journal on Computing, 1999
FOCS 1994, preliminary version
 Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications
Avi Wigderson and David Zuckerman
Combinatorica 1999
STOC 1993, preliminary version
 Randomness is Linear in Space
Noam Nisan and David Zuckerman
JCSS 1996
STOC 1993, preliminary version: "More Deterministic Simulation in Logspace"
 Simulating BPP Using a General Weak Random Source
David Zuckerman
Algorithmica 1996
FOCS 1991, preliminary version
Improves main result of D. Zuckerman, "General Weak Random Sources," FOCS 1990.
 Computing Efficiently Using General Weak Random Sources (Thesis)
David Zuckerman
Ph.D. Dissertation, 1991
Contains some other results from my FOCS 1990 and 1991 papers.
 Nearly Optimal Pseudorandomness From Hardness
Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
FOCS 2020
 Spectral Sparsification via BoundedIndependence Sampling

Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman
ICALP 2020
 Randomness Efficient Noise Stability and Generalized Small Bias Sets
Dana Moshkovitz, Justin Oh, and David Zuckerman
FSTTCS 2020
 Simple Optimal Hitting Sets for SmallSuccess RL
William Hoza and David Zuckerman
Video: Princeton Theory Lunch
SIAM Journal on Computing, 2020
FOCS 2018, preliminary version
 On Low Discrepancy Samplings in Product Spaces of Motion Groups
Chandrajit Bajaj, Abhishek Bhowmick, Eshan Chattopadhyay, and David Zuckerman
arXiv 2014
 Robust Pseudorandom Generators
Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, and David Zuckerman
ICALP 2013
 Pseudorandomness from Shrinkage
Russell Impagliazzo, Raghu Meka, and David Zuckerman
Video: BIRS Workshop on Computational Complexity, 2013
Slides: Talks given at MIT, The Weizmann Institute, ELC Tokyo Complexity Workshop, FOCS 2012, Dagstuhl Workshop on Algebraic and Combinatorial Methods in Computational Complexity and University of Washington.
Journal of the ACM, 2019
FOCS 2012, preliminary version
 Pseudorandom Generators for Combinatorial Shapes
Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman
SIAM Journal on Computing, 2013
STOC 2011, preliminary version
 Certifiably Pseudorandom Financial Derivatives
David Zuckerman
SIAM Journal on Computing, 2019
EC 2011, preliminary version
 Fooling Functions of Halfspaces Under Product Distributions
Parikshit Gopalan, Ryan O'Donnell, Yi Wu, and David Zuckerman
CCC 2010
 Pseudorandom Generators for Polynomial Threshold Functions
Raghu Meka and David Zuckerman
SIAM Journal on Computing, 2013
STOC 2010, preliminary version
 SmallBias Spaces for Group Products
Raghu Meka and David Zuckerman
RANDOM 2009
 Low Discrepancy Sets Yield Approximate MinWise Independent Permutation Families
Michael Saks, Aravind Srinivasan, Shiyu Zhou, and David Zuckerman
Information Processing Letters, 2000
RANDOM 1999, preliminary version
 Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension
Nathan Linial, Michael Luby, Michael Saks, and David Zuckerman
Combinatorica 1997
STOC 1993, preliminary version
 How to Recycle Random Bits
Russell Impagliazzo and David Zuckerman
FOCS 1989
 Survey talks:
 Codes and Pseudorandomness: A Survey
David Zuckerman
Slides: Given at the Workshop on Complexity and Coding Theory, 2014.
 Codes in Theoretical Computer Science
David Zuckerman
Slides: Given at the DIMACS Workshop on Codes and Complexity, 2001.
 Original Research:
 Robust Fourier and Polynomial Curve Fitting
Venkatesan Guruswami and David Zuckerman
FOCS 2016
 NonMalleable Codes Against Constant Split State Tampering
Eshan Chattopadhyay and David Zuckerman
FOCS 2014
 Optimal Testing of Reed Muller Codes
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman
FOCS 2010
 ListDecoding ReedMuller Codes over Small Fields
Parikshit Gopalan, Adam R. Klivans, and David Zuckerman
Slides: Given at CMU, modified from version given at 2008 Banff Workshop on Analytic Tools in Computational Complexity, UC Berkeley, and IAS.
STOC 2008
 Testing Low  Degree Polynomials Over Prime Fields
Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman
Random Structures and Algorithms, 2009
FOCS 2004, preliminary version
 Combinatorial Bounds for List Decoding
Venkatesan Guruswami, Johan Hastad, Madhu Sudan, and David Zuckerman
IEEE Transactions on Information Theory, 2002
Allerton 2000, preliminary version
 Asymptotically Good Codes Correcting Insertions, Deletions and Transpositions
Leonard J. Schulman and David Zuckerman
IEEE Transactions on Information Theory, 1999
SODA 1997, preliminary version
 An XORBased ErasureResilient Coding Scheme
Johannes Blomer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, and David Zuckerman
ICSI Technical Report TR95048, 1995
 Biasing Boolean Functions and Collective CoinFlipping Protocols over Arbitrary Product Distributions
Yuval Filmus, Lianna Hamardzumyan, Hamed Hatami, Pooya Hatami, and David Zuckerman
ICALP 2019
 Bitcoin Beacon
Iddo Bentov, Ariel Gabizon, and David Zuckerman
arXiv 2016
 Random Selection with an Adversarial Majority
Ronen Gradwohl, Salil Vadhan, and David Zuckerman
CRYPTO 2006, revised 06/19/2006
 Expander Graphs for Digital Stream Authentication and Robust Overlay Networks
Dawn Song, David Zuckerman, and J.D. Tugar
IEEE Security and Privacy 2002
 Lower Bounds for Leader Election and Collective CoinFlipping in the Perfect Information Model
Alexander Russell, Michael Saks, and David Zuckerman
SIAM Journal on Computing, 2002
STOC 1999, preliminary version
 Perfect Information Leader Election in log*n+O(1) Rounds
Alexander Russell and David Zuckerman
JCSS 2001
FOCS 1998, preliminary version
 Tight Analyses of Two Local Load Balancing Algorithms
Bhaskar Ghosh, F.T. Leighton, Bruce M. Maggs, S. Muthurkrishnan, C. Greg Plaxton, R. Rajaraman, Andrea W. Richa, Robert E. Tarjan, and David Zuckerman
SIAM Journal on Computing, 1999
STOC 1995, preliminary version
 Lower Bounds for Randomized Mutual Exclusion
Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, and David Zuckerman
SIAM Journal on Computing, 1998
STOC 1993, preliminary version
 Security preserving amplification of hardness
Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, and David Zuckerman
FOCS 1990
 The Space Complexity of Sampling
Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman
ITCS 2022
 XOR Lemmas for Resilient Functions Against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
STOC 2020
 Rectangles are Nonnegative Juntas
Mika Goos, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman
SIAM Journal on Computing, 2016
STOC 2015, preliminary version
 Mining Circuit Lower Bounds for MetaAlgorithms
Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman
Computational Complexity 2015
CCC 2014, preliminary version
 Compression of Samplable Sources
Luca Trevisan, Salil Vadhan, and David Zuckerman
Computational Complexity 2005
CCC 2004, preliminary version
 Interaction in Quantum Communication and the Complexity of Set Disjointness
Hartmut Klauck, Ashwin Nayak, Amnon TaShma, and David Zuckerman
IEEE Transactions on Information Theory, 2007
STOC 2001, preliminary version
 Derandomized Graph Products
Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman
Computational Complexity 1995
 On Unapproximable Versions of NPComplete Problems
David Zuckerman
SIAM Journal on Computing, 1996
CCC 1993, preliminary version
 Multiple Cover Time
Peter Winkler and David Zuckerman
Random Structures and Algorithms, 1996
 On the Time to Traverse all Edges of a Graph
David Zuckerman
Information Processing Letters 1991
 A Technique for Lower Bounding the Cover Time
David Zuckerman
SIAM Journal on Discrete Mathematics 1992
STOC 1990, preliminary version
 Covering Times of Random Walks on Bounded Degree Trees and Other Graphs
David Zuckerman
Journal of Theoretical Probability 1998
 Optimal Speedup of Las Vegas Algorithms
Michael Luby, Alistair Sinclair, and David Zuckerman
Information Processing Letters, 1993
ISTCS 1993, prelimnary version
 How random is your randomness, and why does it matter?
David Zuckerman and Eshan Chattopadhyay
The Conversation, 2016
 Can Random Coin Flips Speed Up a Computer?
David Zuckerman
arXiv 2010
