David Zuckerman's Publications

• Good starting points for learning about extractors are the following surveys:
  N. Nisan, Extracting Randomness: How and Why -- A Survey
  N. Nisan and A. Ta-Shma, Extracting Randomness: A Survey and New Constructions
  R. Shaltiel, Recent Developments in Explicit Constructions of Extractors
  S. Vadhan, Randomness Extractors and their Many Guises, and other PPT survey talks
• 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)
• 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, A. Rao, S. Vadhan, and D. Zuckerman,
  Deterministic Extractors For Small Space Sources (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. thesis, 1991)
  (Contains some other results from my FOCS 1990 and 1991 papers.)

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

• 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, to appear)
  (Preliminary version in FOCS 2004.)
• L. Trevisan, S. Vadhan, and D. Zuckerman,
  Compression of Samplable Sources (Computational Complexity, 2005)
  (Preliminary version in CCC 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)

• See 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.")

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