


default search action
David Zuckerman
Person information
- affiliation: University of Texas at Austin, USA
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j39]Dean Doron
, Jack Murtagh
, Salil P. Vadhan
, David Zuckerman:
Small-Space Spectral Sparsification via Bounded-Independence Sampling. ACM Trans. Comput. Theory 16(2): 7:1-7:32 (2024) - [c61]Jesse Goodman, Xin Li, David Zuckerman:
Improved Condensers for Chor-Goldreich Sources. FOCS 2024: 1513-1549 - [i46]Jesse Goodman, Xin Li, David Zuckerman:
Improved Condensers for Chor-Goldreich Sources. CoRR abs/2410.08142 (2024) - [i45]Zhiyang Xun, David Zuckerman:
Near-Optimal Averaging Samplers and Matrix Samplers. CoRR abs/2411.10870 (2024) - [i44]Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Online Condensing of Unpredictable Sources via Random Walks. Electron. Colloquium Comput. Complex. TR24 (2024) - [i43]Jesse Goodman, Xin Li, David Zuckerman:
Improved Condensers for Chor-Goldreich Sources. Electron. Colloquium Comput. Complex. TR24 (2024) - [i42]Zhiyang Xun, David Zuckerman:
Near-Optimal Averaging Samplers. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c60]Dean Doron
, Dana Moshkovitz, Justin Oh, David Zuckerman:
Almost Chor-Goldreich Sources and Adversarial Random Walks. STOC 2023: 1-9 - [c59]Zeyu Guo
, Ben Lee Volk, Akhil Jalan, David Zuckerman:
Extractors for Images of Varieties. STOC 2023: 46-59 - 2022
- [j38]Dean Doron
, Dana Moshkovitz
, Justin Oh
, David Zuckerman
:
Nearly Optimal Pseudorandomness from Hardness. J. ACM 69(6): 43:1-43:55 (2022) - [c58]Eshan Chattopadhyay, Jesse Goodman, David Zuckerman:
The Space Complexity of Sampling. ITCS 2022: 40:1-40:23 - [i41]Zeyu Guo
, Ben Lee Volk, Akhil Jalan, David Zuckerman:
Extractors for Images of Varieties. CoRR abs/2211.14497 (2022) - [i40]Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Almost Chor-Goldreich Sources and Adversarial Random Walks. Electron. Colloquium Comput. Complex. TR22 (2022) - [i39]Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman:
Extractors for Images of Varieties. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [i38]Eshan Chattopadhyay, Jesse Goodman, David Zuckerman:
The Space Complexity of Sampling. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j37]William M. Hoza
, David Zuckerman:
Simple Optimal Hitting Sets for Small-Success RL. SIAM J. Comput. 49(4): 811-820 (2020) - [c57]Dean Doron
, Dana Moshkovitz, Justin Oh, David Zuckerman:
Nearly Optimal Pseudorandomness From Hardness. FOCS 2020: 1057-1068 - [c56]Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman:
Extractors and Secret Sharing Against Bounded Collusion Protocols. FOCS 2020: 1226-1242 - [c55]Dana Moshkovitz, Justin Oh, David Zuckerman:
Randomness Efficient Noise Stability and Generalized Small Bias Sets. FSTTCS 2020: 31:1-31:16 - [c54]Dean Doron
, Jack Murtagh, Salil P. Vadhan, David Zuckerman:
Spectral Sparsification via Bounded-Independence Sampling. ICALP 2020: 39:1-39:21 - [c53]Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini
, Shachar Lovett, David Zuckerman:
XOR lemmas for resilient functions against polynomials. STOC 2020: 234-246 - [i37]Dean Doron, Jack Murtagh, Salil P. Vadhan, David Zuckerman:
Spectral Sparsification via Bounded-Independence Sampling. CoRR abs/2002.11237 (2020) - [i36]Dean Doron, Jack Murtagh, Salil P. Vadhan, David Zuckerman:
Spectral Sparsification via Bounded-Independence Sampling. Electron. Colloquium Comput. Complex. TR20 (2020) - [i35]Ashutosh Kumar, Raghu Meka, David Zuckerman:
Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing. Electron. Colloquium Comput. Complex. TR20 (2020) - [i34]Ashutosh Kumar, Raghu Meka, David Zuckerman:
Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing. IACR Cryptol. ePrint Arch. 2020: 473 (2020)
2010 – 2019
- 2019
- [j36]Russell Impagliazzo
, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. J. ACM 66(2): 11:1-11:16 (2019) - [j35]David Zuckerman:
Certifiably Pseudorandom Financial Derivatives. SIAM J. Comput. 48(6): 1711-1726 (2019) - [c52]Fu Li, David Zuckerman:
Improved Extractors for Recognizable and Algebraic Sources. APPROX-RANDOM 2019: 72:1-72:22 - [c51]Yuval Filmus
, Lianna Hambardzumyan, Hamed Hatami
, Pooya Hatami
, David Zuckerman:
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. ICALP 2019: 58:1-58:13 - [e2]David Zuckerman:
60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019. IEEE Computer Society 2019, ISBN 978-1-7281-4952-3 [contents] - [i33]Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman:
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. CoRR abs/1902.07426 (2019) - [i32]Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman:
XOR Lemmas for Resilient Functions Against Polynomials. Electron. Colloquium Comput. Complex. TR19 (2019) - [i31]Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Nearly Optimal Pseudorandomness From Hardness. Electron. Colloquium Comput. Complex. TR19 (2019) - [i30]Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman:
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c50]William Hoza, David Zuckerman:
Simple Optimal Hitting Sets for Small-Success RL. FOCS 2018: 59-64 - [i29]Xue Chen, David Zuckerman:
Existence of Simple Extractors. Electron. Colloquium Comput. Complex. TR18 (2018) - [i28]William Hoza, David Zuckerman:
Simple Optimal Hitting Sets for Small-Success RL. Electron. Colloquium Comput. Complex. TR18 (2018) - [i27]Fu Li, David Zuckerman:
Improved Extractors for Recognizable and Algebraic Sources. Electron. Colloquium Comput. Complex. TR18 (2018) - 2016
- [j34]Zeev Dvir, David Zuckerman:
Special issue "Computational Complexity Conference 2015" Guest Editors' Foreword. Comput. Complex. 25(2): 305-307 (2016) - [j33]Mika Göös, Shachar Lovett
, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. SIAM J. Comput. 45(5): 1835-1869 (2016) - [c49]Eshan Chattopadhyay, David Zuckerman:
New Extractors for Interleaved Sources. CCC 2016: 7:1-7:28 - [c48]Venkatesan Guruswami, David Zuckerman:
Robust Fourier and Polynomial Curve Fitting. FOCS 2016: 751-759 - [c47]Eshan Chattopadhyay, David Zuckerman:
Explicit two-source extractors and resilient functions. STOC 2016: 670-683 - [i26]Iddo Bentov, Ariel Gabizon, David Zuckerman:
Bitcoin Beacon. CoRR abs/1605.04559 (2016) - 2015
- [j32]Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman:
Mining Circuit Lower Bound Proofs for Meta-Algorithms. Comput. Complex. 24(2): 333-392 (2015) - [c46]Abhishek Bhowmick, Ariel Gabizon, Thái Hoàng Lê, David Zuckerman:
Deterministic Extractors for Additive Sources: Extended Abstract. ITCS 2015: 277-286 - [c45]Mika Göös, Shachar Lovett
, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. STOC 2015: 257-266 - [e1]David Zuckerman:
30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA. LIPIcs 33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2015, ISBN 978-3-939897-81-1 [contents] - [i25]Eshan Chattopadhyay, David Zuckerman:
Explicit Two-Source Extractors and Resilient Functions. Electron. Colloquium Comput. Complex. TR15 (2015) - [i24]Eshan Chattopadhyay, David Zuckerman:
New Extractors for Interleaved Sources. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j31]Yevgeniy Dodis, Xin Li, Trevor D. Wooley
, David Zuckerman:
Privacy Amplification and Nonmalleable Extractors Via Character Sums. SIAM J. Comput. 43(2): 800-830 (2014) - [c44]Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman:
Mining Circuit Lower Bound Proofs for Meta-algorithms. CCC 2014: 262-273 - [c43]Eshan Chattopadhyay, David Zuckerman:
Non-malleable Codes against Constant Split-State Tampering. FOCS 2014: 306-315 - [i23]Abhishek Bhowmick, Ariel Gabizon, Thái Hoàng Lê, David Zuckerman:
Deterministic Extractors for Additive Sources. CoRR abs/1410.7253 (2014) - [i22]Chandrajit L. Bajaj, Abhishek Bhowmick, Eshan Chattopadhyay, David Zuckerman:
On Low Discrepancy Samplings in Product Spaces of Motion Groups. CoRR abs/1411.7753 (2014) - [i21]Eshan Chattopadhyay, David Zuckerman:
Non-Malleable Codes Against Constant Split-State Tampering. Electron. Colloquium Comput. Complex. TR14 (2014) - [i20]Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j30]Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman:
Pseudorandom Generators for Combinatorial Shapes. SIAM J. Comput. 42(3): 1051-1076 (2013) - [j29]Raghu Meka, David Zuckerman:
Pseudorandom Generators for Polynomial Threshold Functions. SIAM J. Comput. 42(3): 1275-1301 (2013) - [c42]Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman:
Robust Pseudorandom Generators. ICALP (1) 2013: 576-588 - [i19]Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman:
Mining Circuit Lower Bound Proofs for Meta-Algorithms. Electron. Colloquium Comput. Complex. TR13 (2013) - [i18]Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman:
Robust Pseudorandom Generators. Electron. Colloquium Comput. Complex. TR13 (2013) - [i17]Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman:
Robust Pseudorandom Generators. IACR Cryptol. ePrint Arch. 2013: 671 (2013) - 2012
- [c41]Russell Impagliazzo
, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. FOCS 2012: 111-119 - [i16]Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j28]Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman:
Deterministic extractors for small-space sources. J. Comput. Syst. Sci. 77(1): 191-220 (2011) - [c40]Yevgeniy Dodis, Xin Li, Trevor D. Wooley
, David Zuckerman:
Privacy Amplification and Non-malleable Extractors via Character Sums. FOCS 2011: 668-677 - [c39]David Zuckerman:
Pseudorandom financial derivatives. EC 2011: 315-320 - [c38]Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman:
Pseudorandom generators for combinatorial shapes. STOC 2011: 253-262 - [p2]Oded Goldreich
, David Zuckerman:
Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More). Studies in Complexity and Cryptography 2011: 40-53 - [i15]Trevor D. Wooley, David Zuckerman:
Non-malleable extractors via character sums. CoRR abs/1102.5415 (2011) - 2010
- [c37]Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman:
Fooling Functions of Halfspaces under Product Distributions. CCC 2010: 223-234 - [c36]Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck
, Madhu Sudan, David Zuckerman:
Optimal Testing of Reed-Muller Codes. FOCS 2010: 488-497 - [c35]Raghu Meka, David Zuckerman:
Pseudorandom generators for polynomial threshold functions. STOC 2010: 427-436 - [p1]Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck
, Madhu Sudan, David Zuckerman:
Optimal Testing of Reed-Muller Codes. Property Testing 2010: 269-275 - [i14]Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman:
Fooling functions of halfspaces under product distributions. CoRR abs/1001.1593 (2010) - [i13]David Zuckerman:
Pseudorandom Financial Derivatives. CoRR abs/1006.0469 (2010) - [i12]David Zuckerman:
Can Random Coin Flips Speed Up a Computer? CoRR abs/1007.1678 (2010) - [i11]Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman:
Pseudorandom Generators for Combinatorial Shapes. Electron. Colloquium Comput. Complex. TR10 (2010) - [i10]Yi Wu, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan:
Fooling functions of halfspaces under product distributions. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j27]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) - [c34]Raghu Meka, David Zuckerman:
Small-Bias Spaces for Group Products. APPROX-RANDOM 2009: 658-672 - [i9]Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
Optimal Testing of Reed-Muller Codes. CoRR abs/0910.0641 (2009) - [i8]Raghu Meka, David Zuckerman:
Pseudorandom Generators for Polynomial Threshold Functions. CoRR abs/0910.4122 (2009) - [i7]Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
Optimal testing of Reed-Muller codes. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c33]Anup Rao, David Zuckerman:
Extractors for Three Uneven-Length Sources. APPROX-RANDOM 2008: 557-570 - [c32]Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman:
Network Extractor Protocols. FOCS 2008: 654-663 - [c31]Parikshit Gopalan, Adam R. Klivans, David Zuckerman:
List-decoding reed-muller codes over small fields. STOC 2008: 265-274 - 2007
- [j26]Amnon Ta-Shma
, Christopher Umans, David Zuckerman:
Lossless Condensers, Unbalanced Expanders, And Extractors. Comb. 27(2): 213-240 (2007) - [j25]Jesse Kamp, David Zuckerman:
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. SIAM J. Comput. 36(5): 1231-1247 (2007) - [j24]Hartmut Klauck
, Ashwin Nayak, Amnon Ta-Shma
, David Zuckerman:
Interaction in Quantum Communication. IEEE Trans. Inf. Theory 53(6): 1970-1982 (2007) - [j23]David Zuckerman:
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory Comput. 3(1): 103-128 (2007) - 2006
- [j22]Amnon Ta-Shma
, David Zuckerman, Shmuel Safra
:
Extractors from Reed-Muller codes. J. Comput. Syst. Sci. 72(5): 786-812 (2006) - [c30]Ronen Gradwohl, Salil P. Vadhan, David Zuckerman:
Random Selection with an Adversarial Majority. CRYPTO 2006: 409-426 - [c29]David Zuckerman:
Linear degree extractors and the inapproximability of max clique and chromatic number. STOC 2006: 681-690 - [c28]Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman:
Deterministic extractors for small-space sources. STOC 2006: 691-700 - [i6]Ronen Gradwohl, Salil P. Vadhan, David Zuckerman:
Random Selection with an Adversarial Majority. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j21]Luca Trevisan
, Salil P. Vadhan, David Zuckerman:
Compression of Samplable Sources. Comput. Complex. 14(3): 186-227 (2005) - [i5]Luca Trevisan, Salil P. Vadhan, David Zuckerman:
Compression of Samplable Sources. Electron. Colloquium Comput. Complex. TR05 (2005) - [i4]David Zuckerman:
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j20]Amnon Ta-Shma
, David Zuckerman:
Extractor codes. IEEE Trans. Inf. Theory 50(12): 3015-3025 (2004) - [c27]Luca Trevisan, Salil P. Vadhan, David Zuckerman:
Compression of Samplable Sources. CCC 2004: 1-14 - [c26]Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman:
Testing Low-Degree Polynomials over Prime Fields. FOCS 2004: 423-432 - 2003
- [c25]Jesse Kamp, David Zuckerman:
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. FOCS 2003: 92-101 - 2002
- [j19]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) - [j18]Venkatesan Guruswami, Johan Håstad
, Madhu Sudan, David Zuckerman:
Combinatorial bounds for list decoding. IEEE Trans. Inf. Theory 48(5): 1021-1034 (2002) - [c24]Dawn Xiaodong Song, J. D. Tygar, David Zuckerman:
Expander Graphs for Digital Stream Authentication and Robust Overlay Networks. S&P 2002: 258-270 - 2001
- [j17]Alexander Russell
, David Zuckerman:
Perfect Information Leader Election in log* n+O (1) Rounds. J. Comput. Syst. Sci. 63(4): 612-626 (2001) - [c23]Amnon Ta-Shma
, David Zuckerman, Shmuel Safra
:
Extractors from Reed-Muller Codes. FOCS 2001: 638-647 - [c22]Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma
, David Zuckerman:
Interaction in quantum communication and the complexity of set disjointness. STOC 2001: 124-133 - [c21]Amnon Ta-Shma
, Christopher Umans, David Zuckerman:
Loss-less condensers, unbalanced expanders, and extractors. STOC 2001: 143-152 - [c20]Amnon Ta-Shma
, David Zuckerman:
Extractor codes. STOC 2001: 193-199 - [i3]Amnon Ta-Shma, David Zuckerman, Shmuel Safra
:
Extractors from Reed-Muller Codes. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j16]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) - [i2]Ashwin Nayak, Amnon Ta-Shma, David Zuckerman:
Interaction in Quantum Communication Complexity. CoRR quant-ph/0005106 (2000)
1990 – 1999
- 1999
- [j15]Avi Wigderson, David Zuckerman:
Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. Comb. 19(1): 125-138 (1999) - [j14]Aravind Srinivasan, David Zuckerman:
Computing with Very Weak Random Sources. SIAM J. Comput. 28(4): 1433-1459 (1999) - [j13]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) - [j12]Leonard J. Schulman
, David Zuckerman:
Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE Trans. Inf. Theory 45(7): 2552-2557 (1999) - [c19]Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman:
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families. RANDOM-APPROX 1999: 11-15 - [c18]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 - 1998
- [j11]Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman:
Lower Bounds for Randomized Mutual Exclusion. SIAM J. Comput. 27(6): 1550-1563 (1998) - [c17]Alexander Russell, David Zuckerman:
Perfect Information Leader Election in log*n + O(1) Rounds. FOCS 1998: 576-583 - [c16]David Zuckerman:
Extractors for Weak Random Sources and Their Applications. SWAT 1998: 155-157 - 1997
- [j10]Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman:
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension. Comb. 17(2): 215-234 (1997) - [j9]David Zuckerman:
Randomness-optimal oblivious sampling. Random Struct. Algorithms 11(4): 345-367 (1997) - [c15]Leonard J. Schulman, David Zuckerman:
Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (Preliminary Version). SODA 1997: 669-674 - [i1]Oded Goldreich, David Zuckerman:
Another proof that BPP subseteq PH (and more). Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j8]David Zuckerman:
Simulating BPP Using a General Weak Random Source. Algorithmica 16(4/5): 367-391 (1996) - [j7]Noam Nisan, David Zuckerman:
Randomness is Linear in Space. J. Comput. Syst. Sci. 52(1): 43-52 (1996) - [j6]Peter Winkler, David Zuckerman:
Multiple cover time. Random Struct. Algorithms 9(4): 403-411 (1996) - [j5]David Zuckerman:
On Unapproximable Versions of NP-Complete Problems. SIAM J. Comput. 25(6): 1293-1304 (1996) - [c14]David Zuckerman:
Randomness-Optimal Sampling, Extractors, and Constructive Leader Election. STOC 1996: 286-295 - 1995
- [j4]Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman:
Derandomized Graph Products. Comput. Complex. 5(1): 60-75 (1995) - [c13]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 - 1994
- [c12]Aravind Srinivasan, David Zuckerman:
Computing with Very Weak Random Sources. FOCS 1994: 264-275 - 1993
- [j3]Michael Luby, Alistair Sinclair, David Zuckerman:
Optimal Speedup of Las Vegas Algorithms. Inf. Process. Lett. 47(4): 173-180 (1993) - [c11]David Zuckerman:
NP-Complete Problems Have a Version That's Hard to Approximate. SCT 1993: 305-312 - [c10]Michael Luby, Alistair Sinclair, David Zuckerman:
Optimal Speedup of Las Vegas Algorithms. ISTCS 1993: 128-133 - [c9]Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman:
Lower bounds for randomized mutual exclusion. STOC 1993: 154-163 - [c8]Noam Nisan
, David Zuckerman:
More deterministic simulation in logspace. STOC 1993: 235-244 - [c7]Avi Wigderson, David Zuckerman:
Expanders that beat the eigenvalue bound: explicit construction and applications. STOC 1993: 245-251 - [c6]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 - 1992
- [j2]David Zuckerman:
A Technique for Lower Bounding the Cover Time. SIAM J. Discret. Math. 5(1): 81-87 (1992) - 1991
- [j1]David Zuckerman:
On the Time to Traverse all Edges of a Graph. Inf. Process. Lett. 38(6): 335-337 (1991) - [c5]David Zuckerman:
Simulating BPP Using a General Weak Random Source. FOCS 1991: 79-89 - 1990
- [c4]Oded Goldreich, Russell Impagliazzo
, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman:
Security Preserving Amplification of Hardness. FOCS 1990: 318-326 - [c3]David Zuckerman:
General Weak Random Sources. FOCS 1990: 534-543 - [c2]David Zuckerman:
A Technique for Lower Bounding the Cover Time. STOC 1990: 254-259
1980 – 1989
- 1989
- [c1]Russell Impagliazzo
, David Zuckerman:
How to Recycle Random Bits. FOCS 1989: 248-253
Coauthor Index

manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-02-26 21:49 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint