Randomness Extractors and Applications
Other Pseudorandomness and Explicit Constructions
Coding Theory
Complexity Theory and Compression
Distributed Computing, Cryptography, and Security
Inapproximability
Random Walks on Graphs
Communication Complexity
Randomized Algorithms
Finance
Expository
Randomness Extractors and Applications

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.

A. Bhowmick, A. Gabizon, T.H. Le, and D. Zuckerman,
Deterministic Extractors for Additive Sources (ITCS 2015)
 See
NonMalleable Codes Against Constant SplitState Tampering
under Coding Theory.
 Y. Dodis, X. Li, T.D. Wooley, and D. Zuckerman,
Privacy Amplification and NonMalleable 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 UnevenLength 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 BitFixing Sources
and ExposureResilient Cryptography
(SICOMP, 2006)
(Preliminary version in FOCS 2003)
 A. TaShma, D. Zuckerman, and S. Safra,
Extractors from ReedMuller Codes
(JCSS, 2006)
(Preliminary version in FOCS 2001)
 A. TaShma and D. Zuckerman,
Extractor Codes
(IEEE Transactions on Information Theory, 2004)
(Preliminary version in STOC 2001)
 A. TaShma, 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,
RandomnessOptimal Oblivious Sampling (Random Structures and Algorithms, 1997)
(Preliminary version called "RandomnessOptimal 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.)
Other Pseudorandomness and Explicit Constructions
 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 (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
(SICOMP 2013)
(Preliminary version in STOC 2010)
 R. Meka and D. Zuckerman,
SmallBias Spaces for Group Products
(RANDOM 2009)
 M. Saks, A. Srinivasan, S. Zhou, and D. Zuckerman,
Low Discrepancy Sets Yield Approximate MinWise 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
Coding Theory

E. Chattopadhyay and D. Zuckerman,
NonMalleable Codes Against Constant SplitState Tampering (FOCS 2014)
 A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman,
Optimal Testing of ReedMuller Codes (FOCS 2010)
 P. Gopalan, A.R. Klivans, and D. Zuckerman,
ListDecoding ReedMuller Codes over Small Fields
(STOC 2008)
 C.S. Jutla, A.C. Patthak, A. Rudra, and D. Zuckerman,
Testing LowDegree Polynomials Over Prime Fields
(Random Structures and Algorithms, 2009)
(Preliminary version in FOCS 2004.)
 See Extractor Codes
and Extractors from ReedMuller 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 XORBased ErasureResilient Coding Scheme
(ICSI Technical Report TR95048, 1995)
Complexity Theory and Compression
Distributed Computing, Cryptography, and Security
 See
Robust Pseudorandom Generators under
Other Pseudorandomness and Explicit Constructions, and
Privacy Amplification and NonMalleable Extractors Via Character Sums,
Network Extractor Protocols, and
Deterministic Extractors for BitFixing Sources
and ExposureResilient 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 CoinFlipping 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)
Inapproximability
Random Walks on Graphs
 See
Deterministic Extractors for BitFixing Sources
and ExposureResilient 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.")
Communication Complexity
 M. Goos, S. Lovett, R. Meka, T. Watson, and D. Zuckerman,
Rectangles are Nonnegative Juntas
(STOC 2015)
 H. Klauck, A. Nayak, A. TaShma, and D. Zuckerman,
Interaction in Quantum Communication and the Complexity of Set Disjointness
(IEEE Transactions on Information Theory, 2007)
(Preliminary version in STOC 2001)
Randomized Algorithms
Finance
Expository
Last modified: May 15, 2015