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.
• Y. Dodis, X. Li, T.D. Wooley, and D. Zuckerman,
  Privacy Amplification and Non-Malleable Extractors Via Character Sums (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.)

• R. Impagliazzo, R. Meka, and D. Zuckerman,
  Pseudorandomness from Shrinkage (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,
  Pseudorandom Financial Derivatives (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 (STOC 2010; SICOMP, to appear)
  
• 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

• 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)

• R. Chen, V. Kabanets, A. Kolokolova, R. Shaltiel, and D. Zuckerman,
  Mining Circuit Lower Bounds for Meta-Algorithms (ECCC, 2013)
• L. Trevisan, S. Vadhan, and D. Zuckerman,
  Compression of Samplable Sources (Computational Complexity, 2005)
  (Preliminary version in CCC 2004)

• See 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
• 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)
• B. Ghosh, et.al.,
  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)

• See Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number under Randomness Extractors and Applications
• 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. Includes improvement of main result of D. Zuckerman, "Covering Times of Random Walks on Bounded Degree Trees and Other Graphs.")

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

• 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)
• M. Luby, A. Sinclair, and D. Zuckerman,
  Optimal Speedup of Las Vegas algorithms (IPL, 1993)
  (Preliminary version in ISTCS 93)

• D. Zuckerman,
  Can Random Coin Flips Speed Up a Computer? (arXiv, 2010)

  ---

  Last modified: April 15, 2013