David Zuckerman

2008
65	EE	Anup Rao, David Zuckerman: Extractors for Three Uneven-Length Sources. APPROX-RANDOM 2008: 557-570
64	EE	Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman: Network Extractor Protocols. FOCS 2008: 654-663
63	EE	Parikshit Gopalan, Adam R. Klivans, David Zuckerman: List-decoding reed-muller codes over small fields. STOC 2008: 265-274
2007
62	EE	Amnon Ta-Shma, Christopher Umans, David Zuckerman: Lossless Condensers, Unbalanced Expanders, And Extractors. Combinatorica 27(2): 213-240 (2007)
61	EE	Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman: Interaction in Quantum Communication. IEEE Transactions on Information Theory 53(6): 1970-1982 (2007)
60	EE	Jesse Kamp, David Zuckerman: Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. SIAM J. Comput. 36(5): 1231-1247 (2007)
59	EE	David Zuckerman: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing 3(1): 103-128 (2007)
2006
58	EE	Ronen Gradwohl, Salil P. Vadhan, David Zuckerman: Random Selection with an Adversarial Majority. CRYPTO 2006: 409-426
57	EE	David Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number. STOC 2006: 681-690
56	EE	Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman: Deterministic extractors for small-space sources. STOC 2006: 691-700
55	EE	Ronen Gradwohl, Salil P. Vadhan, David Zuckerman: Random Selection with an Adversarial Majority. Electronic Colloquium on Computational Complexity (ECCC) 13(026): (2006)
54	EE	Amnon Ta-Shma, David Zuckerman, Shmuel Safra: Extractors from Reed-Muller codes. J. Comput. Syst. Sci. 72(5): 786-812 (2006)
2005
53	EE	Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. Computational Complexity 14(3): 186-227 (2005)
52	EE	Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources Electronic Colloquium on Computational Complexity (ECCC)(012): (2005)
51	EE	David Zuckerman: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number Electronic Colloquium on Computational Complexity (ECCC)(100): (2005)
2004
50	EE	Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman: Testing Low-Degree Polynomials over Prime Fields. FOCS 2004: 423-432
49	EE	Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. IEEE Conference on Computational Complexity 2004: 1-14
48	EE	Amnon Ta-Shma, David Zuckerman: Extractor codes. IEEE Transactions on Information Theory 50(12): 3015-3025 (2004)
2003
47	EE	Jesse Kamp, David Zuckerman: Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. FOCS 2003: 92-101
2002
46	EE	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-
45		Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman: Combinatorial bounds for list decoding. IEEE Transactions on Information Theory 48(5): 1021-1034 (2002)
44	EE	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)
2001
43		Amnon Ta-Shma, David Zuckerman, Shmuel Safra: Extractors from Reed-Muller Codes. FOCS 2001: 638-647
42	EE	Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman: Interaction in quantum communication and the complexity of set disjointness. STOC 2001: 124-133
41	EE	Amnon Ta-Shma, Christopher Umans, David Zuckerman: Loss-less condensers, unbalanced expanders, and extractors. STOC 2001: 143-152
40	EE	Amnon Ta-Shma, David Zuckerman: Extractor codes. STOC 2001: 193-199
39	EE	Amnon Ta-Shma, David Zuckerman, Shmuel Safra: Extractors from Reed-Muller Codes Electronic Colloquium on Computational Complexity (ECCC) 8(36): (2001)
38	EE	Alexander Russell, David Zuckerman: Perfect Information Leader Election in log* n+O (1) Rounds. J. Comput. Syst. Sci. 63(4): 612-626 (2001)
2000
37	EE	Ashwin Nayak, Amnon Ta-Shma, David Zuckerman: Interaction in Quantum Communication Complexity CoRR quant-ph/0005106: (2000)
36	EE	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)
1999
35		Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman: Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families. RANDOM-APPROX 1999: 11-15
34	EE	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
33	EE	Avi Wigderson, David Zuckerman: Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. Combinatorica 19(1): 125-138 (1999)
32		Leonard J. Schulman, David Zuckerman: Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE Transactions on Information Theory 45(7): 2552-2557 (1999)
31		Aravind Srinivasan, David Zuckerman: Computing with Very Weak Random Sources. SIAM J. Comput. 28(4): 1433-1459 (1999)
30		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)
1998
29	EE	Alexander Russell, David Zuckerman: Perfect Information Leader Election in log*n + O(1) Rounds. FOCS 1998: 576-583
28	EE	David Zuckerman: Extractors for Weak Random Sources and Their Applications. SWAT 1998: 155-157
27	EE	Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman: Lower Bounds for Randomized Mutual Exclusion. SIAM J. Comput. 27(6): 1550-1563 (1998)
1997
26		Leonard J. Schulman, David Zuckerman: Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (Preliminary Version). SODA 1997: 669-674
25		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)
24	EE	Oded Goldreich, David Zuckerman: Another proof that BPP subseteq PH (and more). Electronic Colloquium on Computational Complexity (ECCC) 4(45): (1997)
23		David Zuckerman: Randomness-optimal oblivious sampling. Random Struct. Algorithms 11(4): 345-367 (1997)
1996
22	EE	David Zuckerman: Randomness-Optimal Sampling, Extractors, and Constructive Leader Election. STOC 1996: 286-295
21		David Zuckerman: Simulating BPP Using a General Weak Random Source. Algorithmica 16(4/5): 367-391 (1996)
20		Noam Nisan, David Zuckerman: Randomness is Linear in Space. J. Comput. Syst. Sci. 52(1): 43-52 (1996)
19		Peter Winkler, David Zuckerman: Multiple cover time. Random Struct. Algorithms 9(4): 403-411 (1996)
18		David Zuckerman: On Unapproximable Versions of NP-Complete Problems. SIAM J. Comput. 25(6): 1293-1304 (1996)
1995
17	EE	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
16		Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman: Derandomized Graph Products. Computational Complexity 5(1): 60-75 (1995)
1994
15		Aravind Srinivasan, David Zuckerman: Computing with Very Weak Random Sources FOCS 1994: 264-275
1993
14		Michael Luby, Alistair Sinclair, David Zuckerman: Optimal Speedup of Las Vegas Algorithms. ISTCS 1993: 128-133
13	EE	Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman: Lower bounds for randomized mutual exclusion. STOC 1993: 154-163
12	EE	Noam Nisan, David Zuckerman: More deterministic simulation in logspace. STOC 1993: 235-244
11	EE	Avi Wigderson, David Zuckerman: Expanders that beat the eigenvalue bound: explicit construction and applications. STOC 1993: 245-251
10	EE	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
9		David Zuckerman: NP-Complete Problems Have a Version That's Hard to Approximate. Structure in Complexity Theory Conference 1993: 305-312
8		Michael Luby, Alistair Sinclair, David Zuckerman: Optimal Speedup of Las Vegas Algorithms. Inf. Process. Lett. 47(4): 173-180 (1993)
1992
7		David Zuckerman: A Technique for Lower Bounding the Cover Time. SIAM J. Discrete Math. 5(1): 81-87 (1992)
1991
6		David Zuckerman: Simulating BPP Using a General Weak Random Source FOCS 1991: 79-89
5		David Zuckerman: On the Time to Traverse all Edges of a Graph. Inf. Process. Lett. 38(6): 335-337 (1991)
1990
4		Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman: Security Preserving Amplification of Hardness FOCS 1990: 318-326
3		David Zuckerman: General Weak Random Sources FOCS 1990: 534-543
2		David Zuckerman: A Technique for Lower Bounding the Cover Time STOC 1990: 254-259
1989
1		Russell Impagliazzo, David Zuckerman: How to Recycle Random Bits FOCS 1989: 248-253

Coauthor Index

1	Noga Alon	[16]
2	Uriel Feige	[16]
3	Bhaskar Ghosh	[17] [30]
4	Oded Goldreich	[4] [24]
5	Parikshit Gopalan	[63]
6	Ronen Gradwohl	[55] [58]
7	Venkatesan Guruswami	[45]
8	Johan Håstad	[45]
9	Russell Impagliazzo	[1] [4]
10	Charanjit S. Jutla	[50]
11	Yael Tauman Kalai (Yael Tauman)	[64]
12	Jesse Kamp	[47] [56] [60]
13	Hartmut Klauck	[42] [61]
14	Adam R. Klivans (Adam Klivans)	[63]
15	Eyal Kushilevitz	[13] [27]
16	Frank Thomson Leighton (Tom Leighton)	[17] [30]
17	Leonid A. Levin	[4]
18	Xin Li	[64]
19	Nathan Linial (Nati Linial)	[10] [25]
20	Michael Luby	[8] [10] [14] [25]
21	Bruce M. Maggs	[17] [30]
22	Yishay Mansour	[13] [27]
23	S. Muthukrishnan (S. Muthu Muthukrishnan)	[17] [30]
24	Ashwin Nayak	[37] [42] [61]
25	Noam Nisan	[12] [20]
26	Anindya C. Patthak	[50]
27	C. Greg Plaxton	[17] [30]
28	Michael O. Rabin	[13] [27]
29	Rajmohan Rajaraman	[17] [30]
30	Anup Rao	[56] [64] [65]
31	Andréa W. Richa	[17] [30]
32	Atri Rudra	[50]
33	Alexander Russell	[29] [34] [38] [44]
34	Shmuel Safra	[39] [43] [54]
35	Michael E. Saks	[10] [25] [34] [35] [36] [44]
36	Leonard J. Schulman	[26] [32]
37	Alistair Sinclair	[8] [14]
38	Dawn Xiaodong Song	[46]
39	Aravind Srinivasan	[15] [31] [35] [36]
40	Madhu Sudan	[45]
41	Amnon Ta-Shma	[37] [39] [40] [41] [42] [43] [48] [54] [61] [62]
42	Robert Endre Tarjan	[17] [30]
43	Luca Trevisan	[49] [52] [53]
44	J. Doug Tygar (J. D. Tygar)	[46]
45	Christopher Umans	[41] [62]
46	Salil P. Vadhan	[49] [52] [53] [55] [56] [58]
47	Ramarathnam Venkatesan	[4]
48	Avi Wigderson	[11] [16] [33]
49	Peter Winkler (Peter M. Winkler)	[19]
50	Shiyu Zhou	[35] [36]