David Zuckerman
According to our database^{1},
David Zuckerman
authored at least 76 papers
between 1989 and 2019.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2013, "For contributions to randomness extraction, pseudorandomness, and their role in complexity theory.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at dl.acm.org
On csauthors.net:
Bibliography
2019
Nearly Optimal Pseudorandomness From Hardness.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Biasing Boolean Functions and Collective CoinFlipping Protocols over Arbitrary Product Distributions.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
2018
Improved Extractors for Recognizable and Algebraic Sources.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Existence of Simple Extractors.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Simple Optimal Hitting Sets for SmallSuccess RL.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
2016
Special issue "Computational Complexity Conference 2015" Guest Editors' Foreword.
Computational Complexity, 2016
Explicit twosource extractors and resilient functions.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Robust Fourier and Polynomial Curve Fitting.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
New Extractors for Interleaved Sources.
Proceedings of the 31st Conference on Computational Complexity, 2016
2015
Rectangles Are Nonnegative Juntas.
Proceedings of the FortySeventh Annual ACM on Symposium on Theory of Computing, 2015
Deterministic Extractors for Additive Sources: Extended Abstract.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015
2014
Privacy Amplification and Nonmalleable Extractors Via Character Sums.
SIAM J. Comput., 2014
Nonmalleable Codes against Constant SplitState Tampering.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014
Mining Circuit Lower Bound Proofs for Metaalgorithms.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014
2013
Robust Pseudorandom Generators.
Proceedings of the Automata, Languages, and Programming  40th International Colloquium, 2013
2012
Pseudorandomness from Shrinkage.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
2011
Pseudorandom generators for combinatorial shapes.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011
Pseudorandom financial derivatives.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC2011), 2011
Privacy Amplification and Nonmalleable Extractors via Character Sums.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More).
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
2010
Fooling functions of halfspaces under product distributions.
Electronic Colloquium on Computational Complexity (ECCC), 2010
Pseudorandom generators for polynomial threshold functions.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
Optimal Testing of ReedMuller Codes.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
Fooling Functions of Halfspaces under Product Distributions.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010
2009
SmallBias Spaces for Group Products.
Proceedings of the Approximation, 2009
2008
Listdecoding reedmuller codes over small fields.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
Network Extractor Protocols.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Extractors for Three UnevenLength Sources.
Proceedings of the Approximation, 2008
2007
Interaction in Quantum Communication.
IEEE Trans. Information Theory, 2007
Lossless Condensers, Unbalanced Expanders, And Extractors.
Combinatorica, 2007
2006
Linear degree extractors and the inapproximability of max clique and chromatic number.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Deterministic extractors for smallspace sources.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Random Selection with an Adversarial Majority.
Proceedings of the Advances in Cryptology, 2006
2005
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
Electronic Colloquium on Computational Complexity (ECCC), 2005
Compression of Samplable Sources
Electronic Colloquium on Computational Complexity (ECCC), 2005
2004
Testing LowDegree Polynomials over Prime Fields.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004
Compression of Samplable Sources.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004
2003
Deterministic Extractors for BitFixing Sources and ExposureResilient Cryptography.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
2002
Combinatorial bounds for list decoding.
IEEE Trans. Information Theory, 2002
Expander Graphs for Digital Stream Authentication and Robust Overlay Networks.
Proceedings of the 2002 IEEE Symposium on Security and Privacy, 2002
2001
Perfect Information Leader Election in log* n+O (1) Rounds.
J. Comput. Syst. Sci., 2001
Extractors from ReedMuller Codes
Electronic Colloquium on Computational Complexity (ECCC), 2001
Extractor codes.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Lossless condensers, unbalanced expanders, and extractors.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Interaction in quantum communication and the complexity of set disjointness.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Extractors from ReedMuller Codes.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
1999
Asymptotically good codes correcting insertions, deletions, and transpositions.
IEEE Trans. Information Theory, 1999
Computing with Very Weak Random Sources.
SIAM J. Comput., 1999
Lower Bounds for Leader Election and Collective CoinFlipping in the Perfect Information Model.
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
Low Discrepancy Sets Yield Approximate MinWise Independent Permutation Families.
Proceedings of the Randomization, 1999
1998
Extractors for Weak Random Sources and Their Applications.
Proceedings of the Algorithm Theory, 1998
Perfect Information Leader Election in log*n + O(1) Rounds.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
1997
Randomnessoptimal oblivious sampling.
Random Struct. Algorithms, 1997
Another proof that BPP subseteq PH (and more).
Electronic Colloquium on Computational Complexity (ECCC), 1997
Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (Preliminary Version).
Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms, 1997
1996
On Unapproximable Versions of NPComplete Problems.
SIAM J. Comput., 1996
Multiple cover time.
Random Struct. Algorithms, 1996
Randomness is Linear in Space.
J. Comput. Syst. Sci., 1996
Simulating BPP Using a General Weak Random Source.
Algorithmica, 1996
RandomnessOptimal Sampling, Extractors, and Constructive Leader Election.
Proceedings of the TwentyEighth Annual ACM Symposium on the Theory of Computing, 1996
1995
Derandomized Graph Products.
Computational Complexity, 1995
Tight analyses of two local load balancing algorithms.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
1994
Computing with Very Weak Random Sources
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994
1993
Expanders that beat the eigenvalue bound: explicit construction and applications.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
More deterministic simulation in logspace.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
Efficient construction of a small hitting set for combinatorial rectangles in high dimension.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
Lower bounds for randomized mutual exclusion.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
Optimal Speedup of Las Vegas Algorithms.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993
NPComplete Problems Have a Version That's Hard to Approximate.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993
1992
A Technique for Lower Bounding the Cover Time.
SIAM J. Discrete Math., 1992
1991
On the Time to Traverse all Edges of a Graph.
Inf. Process. Lett., 1991
Simulating BPP Using a General Weak Random Source
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
1990
A Technique for Lower Bounding the Cover Time
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
General Weak Random Sources
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
Security Preserving Amplification of Hardness
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
1989
How to Recycle Random Bits
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989