Papers and Talks

Randomness Extractors and Applications

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

  2. Randomness Extraction: A Survey
    David Zuckerman
    Video: Presentation at 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.

  3. Improved Extractors for Recognizable and Algebraic Sources
  4. Fu Li and David Zuckerman
    RANDOM 2019

  5. Explicit Two-Source Extractors and Resilient Functions
  6. Eshan Chattopadhyah and David Zuckerman
    Annals Mathematics 2019
    STOC 2016, Won Best Paper Award (preliminary version)
    Video: TCS+ 2015

  7. New Extractors for Interleaved Sources
  8. Eshan Chattopadhyay and David Zuckerman
    CCC 2016

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

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

  13. Privacy Amplification and Non-Malleable Extractors Via Character Sums
  14. 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.
    SICOMP 2014
    IEEE FOCS 2011, preliminary version

  15. Network Extractor Protocols
  16. 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

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

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

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

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

  27. Extractor Codes
  28. Amnon Ta-Shma and David Zuckerman
    IEEE Transactions on Information Theory 2004
    STOC 2001

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

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

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

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

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

  39. Computing With Very Weak Random Sources
  40. Aravind Srinivasan and David Zuckerman
    SICOMP 1999
    FOCS 1994, preliminary version

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

  43. Randomness is Linear in Space
  44. Noam Nisan and David Zuckerman
    JCSS 1996
    STOC 1993, preliminary version: "More Deterministic Simulation in Logspace"

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

  47. Computing Efficiently Using General Weak Random Sources (Thesis)
  48. 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
    FOCS 2020

  3. Simple Optimal Hitting Sets for Small-Success RL
  4. William Hoza and David Zuckerman
    Video: Presenting at Princeton TCS
    FOCS 2018

  5. On Low Discrepancy Samplings in Product Spaces of Motion Groups
  6. 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

  9. Pseudorandomness from Shrinkage
  10. 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.
    FOCS 2012, preliminary version
    To appear at JACM.

  11. Pseudorandom Generators for Combinatorial Shapes
  12. Parikshit Gopalan, Raghu Meka, Omer Reingold and David Zuckerman
    SICOMP 2013
    STOC 2011, preliminary version

  13. Certifiably Pseudorandom Financial Derivatives
  14. David Zuckerman
    EC 2011, revised preliminary version

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

  17. Pseudorandom Generators for Polynomial Threshold Functions
  18. Raghu Meka and David Zuckerman
    SICOMP 2013
    STOC 2010, preliminary version

  19. Small-Bias Spaces for Group Products
  20. Raghu Meka and David Zuckerman
    RANDOM 2009

  21. Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families
  22. Michael Saks, Aravind Srinivasan, Shiyu Zhou and David Zuckerman
    IPL 2000 RANDOM 1999, preliminary version

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

  25. How to Recycle Random Bits
  26. Russell Impagliazzo and David Zuckerman
    FOCS 1989

Coding Theory and Curve Fitting

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

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

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

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

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

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

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

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

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

  18. An XOR-Based Erasure-Resilient Coding Scheme
  19. 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

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

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

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

  9. Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
  10. Alexander Russell, Michael Saks and David Zuckerman
    SICOMP 2002
    STOC 1999, preliminary version

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

  13. Tight Analyses of Two Local Load Balancing Algorithms
  14. Bhaskar Ghosh, F.T. Leighton, Bruce M. Maggs, S. Muthurkrishnan, C. Greg Plaxton, R. Rajaraman, Andrea W. Richa, Robert E. Tarjan and David Zuckerman
    SICOMP 1999
    STOC 1995, preliminary version

  15. Lower Bounds for Randomized Mutual Exclusion
  16. Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin and David Zuckerman
    SICOMP 1998
    STOC 1993, preliminary version

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

Other Computational Complexity

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

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

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

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

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

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

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

  15. On Unapproximable Versions of NP-Complete Problems
  16. David Zuckerman
    SICOMP 1996
    Structures 1993, preliminary version

Random Walks on Graphs

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

  3. On the Time to Traverse all Edges of a Graph
  4. David Zuckerman
    IPS 1991

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

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

Randomized Algorithms

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

Finance

Expository

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

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