David Zuckerman's Publications

• For an overview of extractors, see my talk Randomness Extraction: A Survey. For a more detailed introduction to extractors and other aspects of pseudorandomness, see Salil Vadhan's book Pseudorandomness.
• F. Li and D. Zuckerman,
  Improved Extractors for Recognizable and Algebraic Sources (RANDOM 2019)
  
• E. Chattopadhyay and D. Zuckerman,
  Explicit Two-Source Extractors and Resilient Functions (Annals of Mathematics, 2019)
  (Preliminary version won Best Paper Award at STOC 2016)
  
• E. Chattopadhyay and D. Zuckerman,
  New Extractors for Interleaved Sources (CCC 2016)
  
• A. Bhowmick, A. Gabizon, T.H. Le, and D. Zuckerman,
  Deterministic Extractors for Additive Sources (ITCS 2015)
• See Non-Malleable Codes Against Constant Split-State Tampering under Coding Theory.
• Y. Dodis, X. Li, T.D. Wooley, and D. Zuckerman,
  Privacy Amplification and Non-Malleable Extractors Via Character Sums (SICOMP 2014)
  (Preliminary version in FOCS 2011)
• Y. Kalai, X. Li, A. Rao, and D. Zuckerman,
  Network Extractor Protocols (FOCS 2008)
• A. Rao and D. Zuckerman,
  Extractors for Three Uneven-Length Sources (RANDOM 2008)
• J. Kamp, A. Rao, S. Vadhan, and D. Zuckerman,
  Deterministic Extractors For Small Space Sources (JCSS 2010)
  (Preliminary version in STOC 2006)
• D. Zuckerman,
  Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number (Theory of Computing, 2007)
  (Preliminary version in STOC 2006)
  
• J. Kamp and D. Zuckerman,
  Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography (SICOMP, 2006)
  (Preliminary version in FOCS 2003)
• A. Ta-Shma, D. Zuckerman, and S. Safra,
  Extractors from Reed-Muller Codes (JCSS, 2006)
  (Preliminary version in FOCS 2001)
• A. Ta-Shma and D. Zuckerman,
  Extractor Codes (IEEE Transactions on Information Theory, 2004)
  (Preliminary version in STOC 2001)
• A. Ta-Shma, C. Umans, and D. Zuckerman,
  Lossless Condensers, Unbalanced Expanders, and Extractors (Combinatorica, 2007)
  (Preliminary version in STOC 2001)
• O. Goldreich and D. Zuckerman,
  Another proof that BPP \subseteq PH (and more), (ECCC, 1997)
• D. Zuckerman,
  Randomness-Optimal Oblivious Sampling (Random Structures and Algorithms, 1997)
  (Preliminary version called "Randomness-Optimal Sampling, Extractors, and Constructive Leader Election" in STOC 1996)
• A. Srinivasan and D. Zuckerman,
  Computing With Very Weak Random Sources (SICOMP, 1999)
  (Preliminary version in FOCS 1994)
• A. Wigderson and D. Zuckerman,
  Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications (Combinatorica, 1999)
  (Preliminary version in STOC 1993)
• N. Nisan and D. Zuckerman,
  Randomness is Linear in Space (slightly modified from JCSS, 1996)
  (Preliminary version called "More Deterministic Simulation in Logspace" in STOC 1993)
• D. Zuckerman,
  Simulating BPP Using a General Weak Random Source (Algorithmica, 1996)
  (Preliminary version in FOCS 1991. Improves main result of D. Zuckerman, "General Weak Random Sources" from FOCS 1990.)
• D. Zuckerman,
  Computing Efficiently Using General Weak Random Sources (Ph.D. dissertation, 1991)
  (Contains some other results from my FOCS 1990 and 1991 papers.)

• D. Doron, D. Moshkovitz, J. Oh, and D. Zuckerman,
  Nearly Optimal Pseudorandomness From Hardness (FOCS 2020)
  
• D. Doron, J. Murtagh, S. Vadhan, and D. Zuckerman,
  Spectral Sparsification via Bounded-Independence Sampling (ICALP 2020)
  
• W. Hoza and D. Zuckerman,
  Simple Optimal Hitting Sets for Small-Success RL (FOCS 2018)
  
• C. Bajaj, A. Bhowmick, E. Chattopadhyay, and D. Zuckerman,
  On Low Discrepancy Samplings in Product Spaces of Motion Groups (arXiv 2014)
  
• Y. Ishai, E. Kushilevitz, X. Li, R. Ostrovsky, M. Praghakaran, A. Sahai, and D. Zuckerman,
  Robust Pseudorandom Generators (ICALP 2013)
  
• R. Impagliazzo, R. Meka, and D. Zuckerman,
  Pseudorandomness from Shrinkage (JACM)
  (Preliminary version in FOCS 2012)
  
• P. Gopalan, R. Meka, O. Reingold, and D. Zuckerman,
  Pseudorandom Generators for Combinatorial Shapes (SICOMP 2013)
  (Preliminary version in STOC 2011)
• D. Zuckerman,
  Certifiably Pseudorandom Financial Derivatives (revised from preliminary version in EC 2011)
• P. Gopalan, R. O'Donnell, Y. Wu, and D. Zuckerman,
  Fooling Functions of Halfspaces Under Product Distributions (CCC, 2010)
  
• R. Meka and D. Zuckerman,
  Pseudorandom Generators for Polynomial Threshold Functions (SICOMP 2013)
  (Preliminary version in STOC 2010)
• R. Meka and D. Zuckerman,
  Small-Bias Spaces for Group Products (RANDOM 2009)
  
• M. Saks, A. Srinivasan, S. Zhou, and D. Zuckerman,
  Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families (IPL, 2000)
  (Preliminary version in RANDOM 1999)
• N. Linial, M. Luby, M. Saks, and D. Zuckerman,
  Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension (Combinatorica, 1997)
  (Preliminary version in STOC 1993)
• R. Impagliazzo and D. Zuckerman,
  How to Recycle Random Bits (FOCS 1989)
• See also Derandomized Graph Products under Inapproximability

• V. Guruswami and D. Zuckerman,
  Robust Fourier and Polynomial Curve Fitting (FOCS 2016)
• E. Chattopadhyay and D. Zuckerman,
  Non-Malleable Codes Against Constant Split-State Tampering (FOCS 2014)
• A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman,
  Optimal Testing of Reed-Muller Codes (FOCS 2010)
• P. Gopalan, A.R. Klivans, and D. Zuckerman,
  List-Decoding Reed-Muller Codes over Small Fields (STOC 2008)
• C.S. Jutla, A.C. Patthak, A. Rudra, and D. Zuckerman,
  Testing Low-Degree Polynomials Over Prime Fields (Random Structures and Algorithms, 2009)
  (Preliminary version in FOCS 2004.)
• See Extractor Codes and Extractors from Reed-Muller Codes under Randomness Extractors and Applications
• V. Guruswami, J. Hastad, M. Sudan, and D. Zuckerman,
  Combinatorial Bounds for List Decoding (IEEE Transactions on Information Theory, 2002)
  (Preliminary version in Allerton 2000)
• L. Schulman and D. Zuckerman,
  Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (IEEE Transactions on Information Theory, 1999)
  (Preliminary version in SODA 97)
• J. Blomer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, and D. Zuckerman,
  An XOR-Based Erasure-Resilient Coding Scheme (ICSI Technical Report TR-95-048, 1995)

• Y. Filmus, L. Hambardzumyan, H. Hatami, P. Hatami, and D. Zuckerman,
  Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions (ICALP 2019)
  
• See Robust Pseudorandom Generators under Other Pseudorandomness and Explicit Constructions, and Privacy Amplification and Non-Malleable Extractors Via Character Sums, Network Extractor Protocols, and Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography under Randomness Extractors and Applications.
• I. Bentov, A. Gabizon, and D. Zuckerman,
  Bitcoin Beacon (arXiv, 2016)
  
• R. Gradwohl, S. Vadhan, and D. Zuckerman,
  Random Selection with an Adversarial Majority (CRYPTO 2006, revised 6/19/06)
  
• D. Song, D. Zuckerman, and J. D. Tygar,
  Expander Graphs for Digital Stream Authentication and Robust Overlay Networks (IEEE Security and Privacy 2002)
• A. Russell, M. Saks, and D. Zuckerman,
  Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model (SICOMP, 2002)
  (Preliminary version in STOC 1999)
• A. Russell and D. Zuckerman,
  Perfect Information Leader Election in log* n + O(1) Rounds (JCSS, 2001)
  (Preliminary version in FOCS 1998)
• Ghosh, Leighton, Maggs, Muthukrishnan, Plaxton, Rajaraman, Richa, Tarjan, and Zuckerman,
  Tight Analyses of Two Local Load Balancing Algorithms (SICOMP, 1999)
  (Preliminary version in STOC 1995)
• E. Kushilevitz, Y. Mansour, M.O. Rabin, and D. Zuckerman,
  Lower Bounds for Randomized Mutual Exclusion (SICOMP, 1998)
  (Preliminary version in STOC 1993)
• O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman,
  Security preserving amplification of hardness (FOCS 1990)

• E. Chattopadhyay, P. Hatami, K. Hosseini, S.Lovett, and D. Zuckerman,
  XOR Lemmas for Resilient Functions Against Polynomials (STOC 2020)
  
• M. Goos, S. Lovett, R. Meka, T. Watson, and D. Zuckerman,
  Rectangles are Nonnegative Juntas (SICOMP 2016)
  (Preliminary version in STOC 2015)
• R. Chen, V. Kabanets, A. Kolokolova, R. Shaltiel, and D. Zuckerman,
  Mining Circuit Lower Bounds for Meta-Algorithms (Computational Complexity 2015)
  (Preliminary version in CCC 2014)
• See Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number under Randomness Extractors and Applications
• L. Trevisan, S. Vadhan, and D. Zuckerman,
  Compression of Samplable Sources (Computational Complexity, 2005)
  (Preliminary version in CCC 2004)
• H. Klauck, A. Nayak, A. Ta-Shma, and D. Zuckerman,
  Interaction in Quantum Communication and the Complexity of Set Disjointness (IEEE Transactions on Information Theory, 2007)
  (Preliminary version in STOC 2001)
• N. Alon, U. Feige, A. Wigderson, and D. Zuckerman,
  Derandomized Graph Products (Computational Complexity, 1995)
• D. Zuckerman,
  On Unapproximable Versions of NP-Complete Problems (SICOMP, 1996)
  (Preliminary version in Structures 93)

• See Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography, How to Recycle Random Bits, Derandomized Graph Products, and Lower Bounds for Randomized Mutual Exclusion
• P. Winkler and D. Zuckerman,
  Multiple Cover Time (Random Structures and Algorithms, 1996)
• D. Zuckerman,
  On the Time to Traverse All Edges of a Graph (IPL, 1991)
• D. Zuckerman,
  A Technique for Lower Bounding the Cover Time (SIAM Journal on Discrete Mathematics, 1992)
  (Preliminary version in STOC 1990)
• D. Zuckerman,
  "Covering Times of Random Walks on Bounded Degree Trees and Other Graphs" (Journal of Theoretical Probability, 1989)

• M. Luby, A. Sinclair, and D. Zuckerman,
  Optimal Speedup of Las Vegas algorithms (IPL, 1993)
  (Preliminary version in ISTCS 93)

• See Certifiably Pseudorandom Financial Derivatives under Other Pseudorandomness and Explicit Constructions.

• D. Zuckerman and E. Chattopadhyay,
  How random is your randomness, and why does it matter? (The Conversation, 2016)
• D. Zuckerman,
  Can Random Coin Flips Speed Up a Computer? (arXiv, 2010)

  ---