David Zuckerman

According to our database1, David Zuckerman authored at least 80 papers between 1989 and 2020.

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

2020
Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing.
Electronic Colloquium on Computational Complexity (ECCC), 2020

Spectral Sparsification via Bounded-Independence Sampling.
Electronic Colloquium on Computational Complexity (ECCC), 2020

2019
Certifiably Pseudorandom Financial Derivatives.
SIAM J. Comput., 2019

Pseudorandomness from Shrinkage.
J. ACM, 2019

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions.
Electronic Colloquium on Computational Complexity (ECCC), 2019

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

XOR Lemmas for Resilient Functions Against Polynomials.
Electronic Colloquium on Computational Complexity (ECCC), 2019

2018
Improved Extractors for Recognizable and Algebraic Sources.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Simple Optimal Hitting Sets for Small-Success RL.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Existence of Simple Extractors.
Electronic Colloquium on Computational Complexity (ECCC), 2018

2016
Bitcoin Beacon.
CoRR, 2016

Special issue "Computational Complexity Conference 2015" Guest Editors' Foreword.
Comput. Complex., 2016

Robust Fourier and Polynomial Curve Fitting.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015
New Extractors for Interleaved Sources.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Explicit Two-Source Extractors and Resilient Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Mining Circuit Lower Bound Proofs for Meta-Algorithms.
Comput. Complex., 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

Rectangles Are Nonnegative Juntas.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Non-Malleable Codes Against Constant Split-State Tampering.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Deterministic Extractors for Additive Sources.
CoRR, 2014

On Low Discrepancy Samplings in Product Spaces of Motion Groups.
CoRR, 2014

2013
Pseudorandom Generators for Polynomial Threshold Functions.
SIAM J. Comput., 2013

Robust Pseudorandom Generators.
Electronic Colloquium on Computational Complexity (ECCC), 2013

2011
Deterministic extractors for small-space sources.
J. Comput. Syst. Sci., 2011

Non-malleable extractors via character sums
CoRR, 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 <i>BPP</i> Í <i>PH</i>\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 Combinatorial Shapes.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Can Random Coin Flips Speed Up a Computer?
CoRR, 2010

Optimal Testing of Reed-Muller Codes.
Proceedings of the Property Testing - Current Research and Surveys, 2010

2009
Testing low-degree polynomials over prime fields.
Random Struct. Algorithms, 2009

Optimal testing of Reed-Muller codes.
Electronic Colloquium on Computational Complexity (ECCC), 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
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number.
Theory Comput., 2007

Interaction in Quantum Communication.
IEEE Trans. Inf. Theory, 2007

Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography.
SIAM J. Comput., 2007

Lossless Condensers, Unbalanced Expanders, And Extractors.
Comb., 2007

2006
Extractors from Reed-Muller codes.
J. Comput. Syst. Sci., 2006

Random Selection with an Adversarial Majority.
Electronic Colloquium on Computational Complexity (ECCC), 2006

2005
Compression of Samplable Sources.
Comput. Complex., 2005

2004
Extractor codes.
IEEE Trans. Inf. Theory, 2004

2002
Combinatorial bounds for list decoding.
IEEE Trans. Inf. Theory, 2002

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model.
SIAM J. Comput., 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

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

2000
Low discrepancy sets yield approximate min-wise independent permutation families.
Inf. Process. Lett., 2000

Interaction in Quantum Communication Complexity
CoRR, 2000

1999
Asymptotically good codes correcting insertions, deletions, and transpositions.
IEEE Trans. Inf. Theory, 1999

Computing with Very Weak Random Sources.
SIAM J. Comput., 1999

Tight Analyses of Two Local Load Balancing Algorithms.
SIAM J. Comput., 1999

Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications.
Comb., 1999

1998
Lower Bounds for Randomized Mutual Exclusion.
SIAM J. Comput., 1998

Extractors for Weak Random Sources and Their Applications.
Proceedings of the Algorithm Theory, 1998

Perfect Information Leader Election in log*<i>n</i> + <i>O</i>(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

Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension.
Comb., 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.
Comput. Complex., 1995

1993
Optimal Speedup of Las Vegas Algorithms.
Inf. Process. Lett., 1993

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

NP-Complete Problems Have a Version That's Hard to Approximate.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, 1993

1992
A Technique for Lower Bounding the Cover Time.
SIAM J. Discret. Math., 1992

1991
On the Time to Traverse all Edges of a Graph.
Inf. Process. Lett., 1991

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...