David Zuckerman

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman: Mining Circuit Lower Bound Proofs for Meta-Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 20: 57 (2013)

Russell Impagliazzo, Raghu Meka, David Zuckerman: Pseudorandomness from Shrinkage. FOCS 2012: 111-119

Russell Impagliazzo, Raghu Meka, David Zuckerman: Pseudorandomness from Shrinkage. Electronic Colloquium on Computational Complexity (ECCC) 19: 57 (2012)

Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman: Deterministic extractors for small-space sources. J. Comput. Syst. Sci. 77(1): 191-220 (2011)

Oded Goldreich, David Zuckerman: Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More). Studies in Complexity and Cryptography 2011: 40-53

Yevgeniy Dodis, Xin Li, Trevor D. Wooley, David Zuckerman: Privacy Amplification and Non-malleable Extractors via Character Sums. FOCS 2011: 668-677

David Zuckerman: Pseudorandom financial derivatives. ACM Conference on Electronic Commerce 2011: 315-320

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman: Pseudorandom generators for combinatorial shapes. STOC 2011: 253-262

Trevor D. Wooley, David Zuckerman: Non-malleable extractors via character sums. CoRR abs/1102.5415 (2011)

Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman: Fooling Functions of Halfspaces under Product Distributions. IEEE Conference on Computational Complexity 2010: 223-234

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman: Optimal Testing of Reed-Muller Codes. FOCS 2010: 488-497

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman: Optimal Testing of Reed-Muller Codes. Property Testing 2010: 269-275

Raghu Meka, David Zuckerman: Pseudorandom generators for polynomial threshold functions. STOC 2010: 427-436

Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman: Fooling functions of halfspaces under product distributions. CoRR abs/1001.1593 (2010)

David Zuckerman: Pseudorandom Financial Derivatives. CoRR abs/1006.0469 (2010)

David Zuckerman: Can Random Coin Flips Speed Up a Computer? CoRR abs/1007.1678 (2010)

Yi Wu, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan: Fooling functions of halfspaces under product distributions. Electronic Colloquium on Computational Complexity (ECCC) 17: 6 (2010)

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman: Pseudorandom Generators for Combinatorial Shapes. Electronic Colloquium on Computational Complexity (ECCC) 17: 176 (2010)

Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman: Testing low-degree polynomials over prime fields. Random Struct. Algorithms 35(2): 163-193 (2009)

Raghu Meka, David Zuckerman: Small-Bias Spaces for Group Products. APPROX-RANDOM 2009: 658-672

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman: Optimal Testing of Reed-Muller Codes. CoRR abs/0910.0641 (2009)

Raghu Meka, David Zuckerman: Pseudorandom Generators for Polynomial Threshold Functions. CoRR abs/0910.4122 (2009)

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman: Optimal testing of Reed-Muller codes. Electronic Colloquium on Computational Complexity (ECCC) 16: 86 (2009)

Anup Rao, David Zuckerman: Extractors for Three Uneven-Length Sources. APPROX-RANDOM 2008: 557-570

Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman: Network Extractor Protocols. FOCS 2008: 654-663

Parikshit Gopalan, Adam R. Klivans, David Zuckerman: List-decoding reed-muller codes over small fields. STOC 2008: 265-274

Amnon Ta-Shma, Christopher Umans, David Zuckerman: Lossless Condensers, Unbalanced Expanders, And Extractors. Combinatorica 27(2): 213-240 (2007)

Jesse Kamp, David Zuckerman: Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. SIAM J. Comput. 36(5): 1231-1247 (2007)

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman: Interaction in Quantum Communication. IEEE Transactions on Information Theory 53(6): 1970-1982 (2007)

David Zuckerman: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing 3(1): 103-128 (2007)

Amnon Ta-Shma, David Zuckerman, Shmuel Safra: Extractors from Reed-Muller codes. J. Comput. Syst. Sci. 72(5): 786-812 (2006)

Ronen Gradwohl, Salil P. Vadhan, David Zuckerman: Random Selection with an Adversarial Majority. CRYPTO 2006: 409-426

David Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number. STOC 2006: 681-690

Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman: Deterministic extractors for small-space sources. STOC 2006: 691-700

Ronen Gradwohl, Salil P. Vadhan, David Zuckerman: Random Selection with an Adversarial Majority. Electronic Colloquium on Computational Complexity (ECCC) 13(026) (2006)

Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. Computational Complexity 14(3): 186-227 (2005)

Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. Electronic Colloquium on Computational Complexity (ECCC)(012) (2005)

David Zuckerman: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Electronic Colloquium on Computational Complexity (ECCC)(100) (2005)

Amnon Ta-Shma, David Zuckerman: Extractor codes. IEEE Transactions on Information Theory 50(12): 3015-3025 (2004)

Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. IEEE Conference on Computational Complexity 2004: 1-14

Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman: Testing Low-Degree Polynomials over Prime Fields. FOCS 2004: 423-432

Jesse Kamp, David Zuckerman: Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. FOCS 2003: 92-101

Alexander Russell, Michael E. Saks, David Zuckerman: Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. SIAM J. Comput. 31(6): 1645-1662 (2002)

Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman: Combinatorial bounds for list decoding. IEEE Transactions on Information Theory 48(5): 1021-1034 (2002)

Dawn Xiaodong Song, J. D. Tygar, David Zuckerman: Expander Graphs for Digital Stream Authentication and Robust Overlay Networks. IEEE Symposium on Security and Privacy 2002: 258-270

Alexander Russell, David Zuckerman: Perfect Information Leader Election in log* n+O (1) Rounds. J. Comput. Syst. Sci. 63(4): 612-626 (2001)

Amnon Ta-Shma, David Zuckerman, Shmuel Safra: Extractors from Reed-Muller Codes. FOCS 2001: 638-647

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman: Interaction in quantum communication and the complexity of set disjointness. STOC 2001: 124-133

Amnon Ta-Shma, Christopher Umans, David Zuckerman: Loss-less condensers, unbalanced expanders, and extractors. STOC 2001: 143-152

Amnon Ta-Shma, David Zuckerman: Extractor codes. STOC 2001: 193-199

Amnon Ta-Shma, David Zuckerman, Shmuel Safra: Extractors from Reed-Muller Codes. Electronic Colloquium on Computational Complexity (ECCC) 8(36) (2001)

Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman: Low discrepancy sets yield approximate min-wise independent permutation families. Inf. Process. Lett. 73(1-2): 29-32 (2000)

Ashwin Nayak, Amnon Ta-Shma, David Zuckerman: Interaction in Quantum Communication Complexity. CoRR quant-ph/0005106 (2000)

Avi Wigderson, David Zuckerman: Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. Combinatorica 19(1): 125-138 (1999)

Aravind Srinivasan, David Zuckerman: Computing with Very Weak Random Sources. SIAM J. Comput. 28(4): 1433-1459 (1999)

Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman: Tight Analyses of Two Local Load Balancing Algorithms. SIAM J. Comput. 29(1): 29-64 (1999)

Leonard J. Schulman, David Zuckerman: Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE Transactions on Information Theory 45(7): 2552-2557 (1999)

Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman: Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families. RANDOM-APPROX 1999: 11-15

Alexander Russell, Michael E. Saks, David Zuckerman: Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. STOC 1999: 339-347

Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman: Lower Bounds for Randomized Mutual Exclusion. SIAM J. Comput. 27(6): 1550-1563 (1998)

Alexander Russell, David Zuckerman: Perfect Information Leader Election in log*n + O(1) Rounds. FOCS 1998: 576-583

David Zuckerman: Extractors for Weak Random Sources and Their Applications. SWAT 1998: 155-157

Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman: Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension. Combinatorica 17(2): 215-234 (1997)

David Zuckerman: Randomness-optimal oblivious sampling. Random Struct. Algorithms 11(4): 345-367 (1997)

Leonard J. Schulman, David Zuckerman: Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (Preliminary Version). SODA 1997: 669-674

Oded Goldreich, David Zuckerman: Another proof that BPP subseteq PH (and more). . Electronic Colloquium on Computational Complexity (ECCC) 4(45) (1997)

David Zuckerman: Simulating BPP Using a General Weak Random Source. Algorithmica 16(4/5): 367-391 (1996)

Noam Nisan, David Zuckerman: Randomness is Linear in Space. J. Comput. Syst. Sci. 52(1): 43-52 (1996)

Peter Winkler, David Zuckerman: Multiple cover time. Random Struct. Algorithms 9(4): 403-411 (1996)

David Zuckerman: On Unapproximable Versions of NP-Complete Problems. SIAM J. Comput. 25(6): 1293-1304 (1996)

David Zuckerman: Randomness-Optimal Sampling, Extractors, and Constructive Leader Election. STOC 1996: 286-295

Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman: Derandomized Graph Products. Computational Complexity 5(1): 60-75 (1995)

Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman: Tight analyses of two local load balancing algorithms. STOC 1995: 548-558

Aravind Srinivasan, David Zuckerman: Computing with Very Weak Random Sources. FOCS 1994: 264-275

Michael Luby, Alistair Sinclair, David Zuckerman: Optimal Speedup of Las Vegas Algorithms. Inf. Process. Lett. 47(4): 173-180 (1993)

David Zuckerman: NP-Complete Problems Have a Version That's Hard to Approximate. Structure in Complexity Theory Conference 1993: 305-312

Michael Luby, Alistair Sinclair, David Zuckerman: Optimal Speedup of Las Vegas Algorithms. ISTCS 1993: 128-133

Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman: Lower bounds for randomized mutual exclusion. STOC 1993: 154-163

Noam Nisan, David Zuckerman: More deterministic simulation in logspace. STOC 1993: 235-244

Avi Wigderson, David Zuckerman: Expanders that beat the eigenvalue bound: explicit construction and applications. STOC 1993: 245-251

Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. STOC 1993: 258-267

David Zuckerman: A Technique for Lower Bounding the Cover Time. SIAM J. Discrete Math. 5(1): 81-87 (1992)

David Zuckerman: On the Time to Traverse all Edges of a Graph. Inf. Process. Lett. 38(6): 335-337 (1991)

David Zuckerman: Simulating BPP Using a General Weak Random Source. FOCS 1991: 79-89

Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman: Security Preserving Amplification of Hardness. FOCS 1990: 318-326

David Zuckerman: General Weak Random Sources. FOCS 1990: 534-543

David Zuckerman: A Technique for Lower Bounding the Cover Time. STOC 1990: 254-259

Russell Impagliazzo, David Zuckerman: How to Recycle Random Bits. FOCS 1989: 248-253