David I. Zuckerman

GDC 4.508
(512) 471-9729
diz [at] cs [dot] utexas [dot] edu

Zuckerman does research in the role of randomness in computation. In particular, much of his research has focused on randomness extraction, pseudorandomness, coding theory, cryptography, and other aspects of complexity theory.

UTCS Research Areas: 
Selected Awards & Honors: 
  • John S. Guggenheim Memorial Foundation Fellowship, 2004-05
  • Radcliffe Institute for Advanced Study Fellowship, 2004-05 
  • David and Lucile Packard Fellowship for Science and Engineering, 1996-2006
  • Alfred P. Sloan Research Fellowship, 1996-2000
  • NSF Young Investigator Award, 1994-2000
  • Machtey Award (Best Student Paper Award), FOCS 1990 
  • Putnam Fellow (William Lowell Putnam Mathematical Competition co-winner), 1986
Selected Publications: 
  • R. Meka and D. Zuckerman, Pseudorandom generators for polynomial threshold functions, 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010, pp. 427-436.  Invited to special SICOMP issue on STOC 2010.
  • D. Zuckerman, Linear degree extractors and the inapproximability of Max Clique and Chromatic Number, Theory of Computing, 3 (2007): 103-128. Preliminary version in STOC 2006.
  • D. Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, 11 (1997): 345-367.  Preliminary version in STOC 1996.
  • N. Nisan and D. Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, 52 (1996): 43-52.  Special issue on STOC 1993.
  • D. Zuckerman, Simulating BPP using a general weak random source, Algorithmica, 16 (1996): 367-391.  Preliminary version in FOCS 1991.
Professional Activities: 

Member of the following editorial boards:

  • Theory of Computing
  • ACM Transactions on Computation Theory
  • SIAM Journal on Discrete Mathematics, 2003-08

Program committee member of the following conferences:

  • IEEE Symposium on Foundations of Computer Science (FOCS)
  • ACM Symposium on Theory of Computing (STOC)
  • IEEE Conference on Computational Complexity (CCC)
  • International Workshop on Randomization and Computation (RANDOM)

Principal Organizer, DIMACS Workshop Pseudorandomness and Explicit Combinatorial Constructions