David Zuckerman

According to our database1, David Zuckerman authored at least 76 papers between 1989 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

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 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Nearly Optimal Pseudorandomness From Hardness.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Biasing Boolean Functions and Collective Coin-Flipping 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 Small-Success 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 two-source 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 Forty-Seventh 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

Non-malleable Codes against Constant Split-State Tampering.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Mining Circuit Lower Bound Proofs for Meta-algorithms.
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 (EC-2011), 2011

Privacy Amplification and Non-malleable 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 Reed-Muller 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
Small-Bias Spaces for Group Products.
Proceedings of the Approximation, 2009

2008
List-decoding reed-muller 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 Uneven-Length 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 small-space 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 Low-Degree 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 Bit-Fixing Sources and Exposure-Resilient 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 Reed-Muller Codes
Electronic Colloquium on Computational Complexity (ECCC), 2001

Extractor codes.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Loss-less 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 Reed-Muller 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 Coin-Flipping in the Perfect Information Model.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Low Discrepancy Sets Yield Approximate Min-Wise 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
Randomness-optimal 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 ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
On Unapproximable Versions of NP-Complete 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

Randomness-Optimal Sampling, Extractors, and Constructive Leader Election.
Proceedings of the Twenty-Eighth 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 Twenty-Seventh 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 Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

More deterministic simulation in logspace.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Efficient construction of a small hitting set for combinatorial rectangles in high dimension.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Lower bounds for randomized mutual exclusion.
Proceedings of the Twenty-Fifth 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

NP-Complete 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


  Loading...