Home Courses People Papers and Talks General Audience


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

Selected Recent Papers

  1. Almost Chor-Goldreich Sources and Adversarial Random Walks
    2. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
    STOC 2023

  2. Extractors for Images of Varieties
    3. Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman
    STOC 2023

  3. The Space Complexity of Sampling
    4. Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman
    ITCS 2022

  4. Nearly Optimal Pseudorandomness From Hardness
    5. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
    Journal of the ACM, 2022
    FOCS 2020

  5. Extractors and Secret Sharing Against Bounded Collusion Protocols (merger of these two)
    6. Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, and David Zuckerman
    FOCS 2020

  6. XOR Lemmas for Resilient Functions Against Polynomials
    7. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
    STOC 2020

  7. Simple Optimal Hitting Sets for Small-Success RL
    8. William Hoza and David Zuckerman
    Video: Princeton Theory Lunch
    SIAM Journal on Computing, 2020
    FOCS 2018, preliminary version

  8. Explicit Two-Source Extractors and Resilient Functions
    9. Eshan Chattopadhyah and David Zuckerman
    Annals of Mathematics, 2019
    STOC 2016 Best Paper Award
    Video: TCS+ 2015

Randomness Extractors and Applications

  1. Survey talks:

  2. Randomness Extraction and Cryptography
    Video: Conference on Information-Theoretic Cryptography (ITC), 2022

  3. Extractors and Expanders, Four Part Tutorial
    Video: Simons Institute Pseudorandomness Boot Camp, 2017

  4. Randomness Extraction: A Survey
    Video: Institute for Advanced Study, 2012
    Slides: Given at the satellite pre-workshop 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 Information-Theoretic Cryptography, 2012.

    For a more detailed introduction to extractors and other aspects of pseudorandomness, see Salil Vadhan's book Pseudorandomness.

  5. Original Research:

  6. Almost Chor-Goldreich Sources and Adversarial Random Walks
    7. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
    STOC 2023

  7. Extractors for Images of Varieties
    8. Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman
    STOC 2023

  8. Extractors and Secret Sharing Against Bounded Collusion Protocols (merger of these two)
    9. Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, and David Zuckerman
    FOCS 2020

  9. Improved Extractors for Recognizable and Algebraic Sources
    10. Fu Li and David Zuckerman
    RANDOM 2019

  10. Explicit Two-Source Extractors and Resilient Functions
    11. Eshan Chattopadhyah and David Zuckerman
    Annals of Mathematics, 2019
    STOC 2016 Best Paper Award
    Video: TCS+ 2015

  11. Existence of Simple Extractors
    12. Xue Chen and David Zuckerman
    ECCC 2018

  12. New Extractors for Interleaved Sources
    13. Eshan Chattopadhyay and David Zuckerman
    CCC 2016

  13. Deterministic Extractors for Additive Sources
    14. Abhishek Bhowmick, Ariel Gabizon, Thai Hoang Le, and David Zuckerman
    ITCS 2015

  14. Non-Malleable Codes Against Constant Split-State Teampering
    15. Eshan Chattopadhyay and David Zuckerman
    Video: Simons Workshop on Coding: From Practice to Theory, 2015
    Also under Coding Theory.

  15. Privacy Amplification and Non-Malleable Extractors Via Character Sums
    16. 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

  16. Network Extractor Protocols
    17. Yael Tauman Kalai, Xin Li, Anup Rao, and David Zuckerman
    FOCS 2008

  17. Extractors for Three Uneven-Length Sources
    18. Anup Rao and David Zuckerman
    RANDOM 2008

  18. Deterministic Extractors for Small Space Sources
    19. 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

  19. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
    20. 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

  20. Deterministic Extractors for bit-Fixing Sources and Exposure-Resilient Cryptography
    21. Jesse Kamp and David Zuckerman
    SIAM Journal on Computing, 2006
    FOCS 2003, preliminary version

  21. Extractors from Reed-Muller Codes
    22. Amnon Ta-Shma, David Zuckerman, and Shmuel Safra
    JCSS 2006
    FOCS 2001

  22. Extractor Codes
    23. Amnon Ta-Shma and David Zuckerman
    IEEE Transactions on Information Theory, 2004
    STOC 2001

  23. Lossless Condensers, Unbalanced Expanders, and Extractors
    24. Amnon Ta-Shma, Christopher Umans, and David Zuckerman
    Combinatorica 2007
    STOC 2001, preliminary version

  24. Some Successes and Failures of Algebra in Constructing Extractors
    25. David Zuckerman
    Slides: 2004, given at the IPAM Workshop on Automorphic Forms, Group Theory and Graph Expansion.

  25. Computational Complexity and Entropy
    26. David Zuckerman
    Slides: 2001, given at the DIMACS Workshop on Computational Complexity, Entropy, and Statistical Physics

  26. Another proof that BPP\subseteq PH (and more)
    27. Oded Goldreich and David Zuckerman
    ECCC 1997

  27. Randomness-Optimal Oblivious Sampling
    28. David Zuckerman
    Random Structures and Algorithms, 1997
    STOC 1996, prelimnary version: "Randomness-Optimal Sampling, Extractors, and Constructive Leader Election"

  28. Computing With Very Weak Random Sources
    29. Aravind Srinivasan and David Zuckerman
    SIAM Journal on Computing, 1999
    FOCS 1994, preliminary version

  29. Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications
    30. Avi Wigderson and David Zuckerman
    Combinatorica 1999
    STOC 1993, preliminary version

  30. Randomness is Linear in Space
    31. Noam Nisan and David Zuckerman
    JCSS 1996
    STOC 1993, preliminary version titled "More Deterministic Simulation in Logspace"

  31. Simulating BPP Using a General Weak Random Source
    32. David Zuckerman
    Algorithmica 1996
    FOCS 1991, preliminary version
    Improves main result of D. Zuckerman, "General Weak Random Sources," FOCS 1990.

  32. Computing Efficiently Using General Weak Random Sources (Thesis)
    33. David Zuckerman
    Ph.D. Dissertation, 1991
    Contains some other results from my FOCS 1990 and 1991 papers.

Other Pseudorandomness and Explicit Constructions

  1. Nearly Optimal Pseudorandomness From Hardness
    2. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
    Journal of the ACM, 2022
    FOCS 2020

  2. Spectral Sparsification via Bounded-Independence Sampling
  3. Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman
    ICALP 2020

  4. Randomness Efficient Noise Stability and Generalized Small Bias Sets
    5. Dana Moshkovitz, Justin Oh, and David Zuckerman
    FSTTCS 2020

  5. Simple Optimal Hitting Sets for Small-Success RL
    6. William Hoza and David Zuckerman
    Video: Princeton Theory Lunch
    SIAM Journal on Computing, 2020
    FOCS 2018, preliminary version

  6. On Low Discrepancy Samplings in Product Spaces of Motion Groups
    7. Chandrajit Bajaj, Abhishek Bhowmick, Eshan Chattopadhyay, and David Zuckerman
    arXiv 2014

  7. Robust Pseudorandom Generators
    8. Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, and David Zuckerman
    ICALP 2013

  8. Pseudorandomness from Shrinkage
    9. 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

  9. Pseudorandom Generators for Combinatorial Shapes
    10. Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman
    SIAM Journal on Computing, 2013
    STOC 2011, preliminary version

  10. Certifiably Pseudorandom Financial Derivatives
    11. David Zuckerman
    SIAM Journal on Computing, 2019
    EC 2011, preliminary version

  11. Fooling Functions of Halfspaces Under Product Distributions
    12. Parikshit Gopalan, Ryan O'Donnell, Yi Wu, and David Zuckerman
    CCC 2010

  12. Pseudorandom Generators for Polynomial Threshold Functions
    13. Raghu Meka and David Zuckerman
    SIAM Journal on Computing, 2013
    STOC 2010, preliminary version

  13. Small-Bias Spaces for Group Products
    14. Raghu Meka and David Zuckerman
    RANDOM 2009

  14. Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families
    15. Michael Saks, Aravind Srinivasan, Shiyu Zhou, and David Zuckerman
    Information Processing Letters, 2000 RANDOM 1999, preliminary version

  15. Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension
    16. Nathan Linial, Michael Luby, Michael Saks, and David Zuckerman
    Combinatorica 1997
    STOC 1993, preliminary version

  16. How to Recycle Random Bits
    17. Russell Impagliazzo and David Zuckerman
    FOCS 1989

Coding Theory and Curve Fitting

  1. Survey talks:

  2. Codes and Pseudorandomness: A Survey
    David Zuckerman
    Slides: Given at the Workshop on Complexity and Coding Theory, 2014.

  3. Codes in Theoretical Computer Science
    4. David Zuckerman
    Slides: Given at the DIMACS Workshop on Codes and Complexity, 2001.

  4. Original Research:

  5. Robust Fourier and Polynomial Curve Fitting
    6. Venkatesan Guruswami and David Zuckerman
    FOCS 2016

  6. Non-Malleable Codes Against Constant Split State Tampering
    7. Eshan Chattopadhyay and David Zuckerman
    FOCS 2014

  7. Optimal Testing of Reed Muller Codes
    8. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman
    FOCS 2010

  8. List-Decoding Reed-Muller Codes over Small Fields
    9. 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

  9. Testing Low - Degree Polynomials Over Prime Fields
    10. Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman
    Random Structures and Algorithms, 2009
    FOCS 2004, preliminary version

  10. Combinatorial Bounds for List Decoding
    11. Venkatesan Guruswami, Johan Hastad, Madhu Sudan, and David Zuckerman
    IEEE Transactions on Information Theory, 2002
    Allerton 2000, preliminary version

  11. Asymptotically Good Codes Correcting Insertions, Deletions and Transpositions
    12. Leonard J. Schulman and David Zuckerman
    IEEE Transactions on Information Theory, 1999
    SODA 1997, preliminary version

  12. An XOR-Based Erasure-Resilient Coding Scheme
    13. Johannes Blomer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, and David Zuckerman
    ICSI Technical Report TR-95048, 1995

Cryptography, Distributed Computing, and Security

  1. Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions
    2. Yuval Filmus, Lianna Hamardzumyan, Hamed Hatami, Pooya Hatami, and David Zuckerman
    ICALP 2019

  2. Bitcoin Beacon
    3. Iddo Bentov, Ariel Gabizon, and David Zuckerman
    arXiv 2016

  3. Random Selection with an Adversarial Majority
    4. Ronen Gradwohl, Salil Vadhan, and David Zuckerman
    CRYPTO 2006, revised 06/19/2006

  4. Expander Graphs for Digital Stream Authentication and Robust Overlay Networks
    5. Dawn Song, David Zuckerman, and J.D. Tugar
    IEEE Security and Privacy 2002

  5. Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
    6. Alexander Russell, Michael Saks, and David Zuckerman
    SIAM Journal on Computing, 2002
    STOC 1999, preliminary version

  6. Perfect Information Leader Election in log*n+O(1) Rounds
    7. Alexander Russell and David Zuckerman
    JCSS 2001
    FOCS 1998, preliminary version

  7. Tight Analyses of Two Local Load Balancing Algorithms
    8. 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

  8. Lower Bounds for Randomized Mutual Exclusion
    9. Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, and David Zuckerman
    SIAM Journal on Computing, 1998
    STOC 1993, preliminary version

  9. Security preserving amplification of hardness
    10. Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, and David Zuckerman
    FOCS 1990

Other Computational Complexity

  1. The Space Complexity of Sampling
    2. Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman
    ITCS 2022

  2. XOR Lemmas for Resilient Functions Against Polynomials
    3. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
    STOC 2020

  3. Rectangles are Nonnegative Juntas
    4. Mika Goos, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman
    SIAM Journal on Computing, 2016
    STOC 2015, preliminary version

  4. Mining Circuit Lower Bounds for Meta-Algorithms
    5. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman
    Computational Complexity 2015
    CCC 2014, preliminary version

  5. Compression of Samplable Sources
    6. Luca Trevisan, Salil Vadhan, and David Zuckerman
    Computational Complexity 2005
    CCC 2004, preliminary version

  6. Interaction in Quantum Communication and the Complexity of Set Disjointness
    7. Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman
    IEEE Transactions on Information Theory, 2007
    STOC 2001, preliminary version

  7. Derandomized Graph Products
    8. Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman
    Computational Complexity 1995

  8. On Unapproximable Versions of NP-Complete Problems
    9. David Zuckerman
    SIAM Journal on Computing, 1996
    CCC 1993, preliminary version

Random Walks on Graphs

  1. Multiple Cover Time
    2. Peter Winkler and David Zuckerman
    Random Structures and Algorithms, 1996

  2. On the Time to Traverse all Edges of a Graph
    3. David Zuckerman
    Information Processing Letters 1991

  3. A Technique for Lower Bounding the Cover Time
    4. David Zuckerman
    SIAM Journal on Discrete Mathematics 1992
    STOC 1990, preliminary version

  4. Covering Times of Random Walks on Bounded Degree Trees and Other Graphs
    5. David Zuckerman
    Journal of Theoretical Probability 1998

Randomized Algorithms

  1. Optimal Speedup of Las Vegas Algorithms
    2. Michael Luby, Alistair Sinclair, and David Zuckerman
    Information Processing Letters, 1993
    ISTCS 1993, prelimnary version

Finance

Expository

  1. How random is your randomness, and why does it matter?
    2. David Zuckerman and Eshan Chattopadhyay
    The Conversation, 2016

  2. Can Random Coin Flips Speed Up a Computer?
    3. David Zuckerman
    arXiv 2010