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

Randomness Extractors and Applications

  1. Survey talks:

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

  3. 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.

  4. Original Research:

  5. 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

  6. Improved Extractors for Recognizable and Algebraic Sources
  7. Fu Li and David Zuckerman
    RANDOM 2019

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

  10. New Extractors for Interleaved Sources
  11. Eshan Chattopadhyay and David Zuckerman
    CCC 2016

  12. Deterministic Extractors for Additive Sources
  13. 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.

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

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

  20. Extractors for Three Uneven-Length Sources
  21. Anup Rao and David Zuckerman
    RANDOM 2008

  22. Deterministic Extractors for Small Space Sources
  23. 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

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

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

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

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

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

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

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

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

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

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

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

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

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

  50. Computing Efficiently Using General Weak Random Sources (Thesis)
  51. 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. Spectral Sparsification via Bounded-Independence Sampling
  4. Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman
    ICALP 2020

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

  7. Simple Optimal Hitting Sets for Small-Success RL
  8. William Hoza and David Zuckerman
    Video: Presenting at Princeton Theory Lunch
    FOCS 2018

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

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

  13. Pseudorandomness from Shrinkage
  14. 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.

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

  17. Certifiably Pseudorandom Financial Derivatives
  18. David Zuckerman
    EC 2011, revised preliminary version

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

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

  23. Small-Bias Spaces for Group Products
  24. Raghu Meka and David Zuckerman
    RANDOM 2009

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

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

  29. How to Recycle Random Bits
  30. 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.

  5. Original Research:

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

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

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

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

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

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

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

  20. An XOR-Based Erasure-Resilient Coding Scheme
  21. 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. Compression of Samplable Sources
  8. Luca Trevisan, Salil Vadhan, and David Zuckerman
    Computational Complexity 2005
    CCC 2004, preliminary version

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

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

  13. On Unapproximable Versions of NP-Complete Problems
  14. David Zuckerman
    SICOMP 1996
    CCC 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. How random is your randomness, and why does it matter?
  2. David Zuckerman and Eshan Chattopadhyay
    The Conversation, 2016

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