## Papers and Talks## Randomness Extractors and Applications- Extractors and Expanders, Four Part Tutorial
David Zuckerman Video: Simons Institute Pseudorandomness Boot Camp, 2017 - Randomness Extraction: A Survey
David Zuckerman Video: Presentation at Institute for Advanced Study, 2012 Slides: Given at the satellite pre-workshop of the ELC Tokoyo Complexity Workshop. This is an extended version of earleir talks given at Rutgers University, 2012; the Institute for Advacned Study, 2012; and the IPAM Workshop Mathematics of Information-Theoretic Cryptography, 2012.
*For a more detailed introduction to extractors and other aspects of pseudorandomness, see Salil Vadhan's book Pseudorandomness.* - Improved Extractors for Recognizable and Algebraic Sources Fu Li and David Zuckerman
- Explicit Two-Source Extractors and Resilient Functions Eshan Chattopadhyah and David Zuckerman
- New Extractors for Interleaved Sources Eshan Chattopadhyay and David Zuckerman
- Deterministic Extractors for Additive Sources Abhishek Bhowmick, Ariel Gabizon, Thai Hoang Le and David Zuckerman
- Non-Malleable Codes Against Constant Split-State Teampering Eshan Chattopadhyay and David Zuckerman
- Privacy Amplification and Non-Malleable Extractors Via Character Sums Yevgeniy Dodis, Xin Li, Trevor D. Wooley and David Zuckerman
- Network Extractor Protocols Yael Tauman Kalai, Xin Li, Anup Rao and David Zuckerman
- Extractors for Three Uneven-Length Sources Anup Rao and David Zuckerman
- Deterministic Extractors for Small Space Sources Jesse Kamp, Anup Rao, Salil Vadhan and David Zuckerman
- Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number David Zuckerman
- Deterministic Extractors for bit-Fixing Sources and Exposure-Resilient Cryptography Jesse Kamp and David Zuckerman
- Extractors from Reed-Muller Codes Amnon Ta-Shma, David Zuckerman and Shmuel Safra
- Extractor Codes Amnon Ta-Shma and David Zuckerman
- Lossless Condensers, Unbalanced Expanders, and Extractors Amnon Ta-Shma, Christopher Umans and David Zuckerman
- Some Successes and Failures of Algebra in Constructing Extractors David Zuckerman
- Computational Complexity and Entropy David Zuckerman
- Another proof that BPP\subseteq PH (and more) Oded Goldreich and David Zuckerman
- Randomness-Optimal Oblivious Sampling David Zuckerman
- Computing With Very Weak Random Sources Aravind Srinivasan and David Zuckerman
- Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications Avi Wigderson and David Zuckerman
- Randomness is Linear in Space Noam Nisan and David Zuckerman
- Simulating BPP Using a General Weak Random Source David Zuckerman
- Computing Efficiently Using General Weak Random Sources (Thesis) David Zuckerman
RANDOM 2019 Annals Mathematics 2019 STOC 2016, Won Best Paper Award (preliminary version) Video: TCS+ 2015 CCC 2016 ITCS 2015 Video: Simons Workshop on Coding: From Practice to Theory, 2015 Also under Coding Theory. Slides: Given at UT Austin, modified from earlier versions given at Rutgers University and Princeton University, 2011. SICOMP 2014 IEEE FOCS 2011, preliminary version FOCS 2008 RANDOM 2008 Slides: Given at the 2006 Banff Workshop on Recent Advances in Computational Complexity(modified from version given at SIAM Conference on Discrete Mathematics 2006). JCSS 2011 STOC 2006, preliminary version Slides: Modified from the version given at IBM/NYU/Columbia Theory Day, STOC 2006, and elsewhere. Theory of Computing 2007 STOC 2006, preliminary version SIAM Journal on Computing 2006 FOCS 2003, preliminary version JCSS 2006 FOCS 2001 IEEE Transactions on Information Theory 2004 STOC 2001 Combinatorica 2007 STOC 2001, preliminary version Slides: 2004, given at the IPAM Workshop on Automorphic Forms, Group Theory and Graph Expansion. Slides: 2001, given at the DIMACS Workshop on Computational Complexity, Entropy, and Statistical Physics ECCC 1997 Random Structures and Algorithms 1997 STOC 1996, prelimnary version: "Randomness-Optimal Sampling, Extractors, and Constructive Leader Election" SICOMP 1999 FOCS 1994, preliminary version Combinatorica 1999 STOC 1993, preliminary version JCSS 1996 STOC 1993, preliminary version: "More Deterministic Simulation in Logspace" Algorithmica 1996 FOCS 1991, preliminary version FOCS 1990, Improves main result of "General Weak Random Sources" D. Zuckerman. Ph.D. Dissertation 1991 Contains some other results from my FOCS 1990 and 1991 papers. ## Other Pseudorandomness and Explicit Constructions- Nearly Optimal Pseudorandomness From Hardness Dean Doron, Dana Moshkovitz, Justin Oh and David Zuckerman
- Simple Optimal Hitting Sets for Small-Success RL William Hoza and David Zuckerman
- On Low Discrepancy Samplings in Product Spaces of Motion Groups Chandrajit Bajaj, Abhishek Bhowmick, Eshan Chattopadhyay and David Zuckerman
- Robust Pseudorandom Generators Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai and David Zuckerman
- Pseudorandomness from Shrinkage Russell Impagliazzo, Raghu Meka and David Zuckerman
- Pseudorandom Generators for Combinatorial Shapes Parikshit Gopalan, Raghu Meka, Omer Reingold and David Zuckerman
- Certifiably Pseudorandom Financial Derivatives David Zuckerman
- Fooling Functions of Halfspaces Under Product Distributions Parikshit Gopalan, Ryan O'Donnell, Yi Wu and David Zuckerman
- Pseudorandom Generators for Polynomial Threshold Functions Raghu Meka and David Zuckerman
- Small-Bias Spaces for Group Products Raghu Meka and David Zuckerman
- Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families Michael Saks, Aravind Srinivasan, Shiyu Zhou and David Zuckerman
- Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension Nathan Linial, Michael Luby, Michael Saks and David Zuckerman
- How to Recycle Random Bits Russell Impagliazzo and David Zuckerman
FOCS 2020 Video: Presenting at Princeton TCS FOCS 2018 arXiv 2014 ICALP 2013 Video: BIRS Workshop on Computational Complexity, 2013 Slides: Talks given at MIT, The Weizmann Institute, ELC Tokyo Complexity Workshop, FOCS 2012, Dagstuhl Workshop on Algebraic and Combinatorial Methods in Computational Complexity and University of Washington. FOCS 2012, preliminary version To appear at JACM. SICOMP 2013 STOC 2011, preliminary version EC 2011, revised preliminary version CCC 2010 SICOMP 2013 STOC 2010, preliminary version RANDOM 2009 IPL 2000 RANDOM 1999, preliminary version Combinatorica 1997 STOC 1993, preliminary version FOCS 1989 - See also Derandomized Graph Products under Other Computational Complexity.
## Coding Theory and Curve Fitting- Codes and Pseudorandomness: A Survey
David Zuckerman Slides: Given at the Workshop on Complexity and Coding Theory, 2014. - Codes in Theoretical Computer Science David Zuckerman
- Robust Fourier and Polynomial Curve Fitting Venkatesan Guruswami and David Zuckerman
- Non-Malleable Codes Against Constant Split State Tampering Eshan Chattopadhyay and David Zuckerman
- Optimal Testing of Reed Muller Codes Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan and David Zuckerman
- List-Decoding Reed-Muller Codes over Small Fields Parikshit Gopalan, Adam R. Klivans and David Zuckerman
- Testing Low - Degree Polynomials Over Prime Fields Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra and David Zuckerman
- Combinatorial Bounds for List Decoding Venkatesan Guruswami, Johan Hastad, Madhu Sudan and David Zuckerman
- Asymptotically Good Codes Correcting Insertions, Deletions and Transpositions Leonard J. Schulman and David Zuckerman
- An XOR-Based Erasure-Resilient Coding Scheme Johannes Blomer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby and David Zuckerman
Slides: Given at the DIMACS Workshop on Codes and Complexity. FOCS 2016 FOCS 2014 FOCS 2010 Slides: Given at CMU, modified from version given at 2008 Banff Workshop on Analytic Tools in Computational Complexity, UC Berkeley, and IAS. STOC 2008 Random Structures and Algorithms 2009 FOCS 2004, preliminary version IEEE Transactions on Information Theory 2002 Allerton 2000, preliminary version IEEE Transactions on Information Theory 1999 SODA 1997, preliminary version ICSI Technical Report TR-95048, 1995 - See Extractor Codes and Extractors from Reed-Muller Codes under Randomness Extractors and Applications.
## Cryptography, Distributed Computing, and Security- Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions Yuval Filmus, Lianna Hamardzumyan, Hamed Hatami, Pooya Hatami and David Zuckerman
- Bitcoin Beacon Iddo Bentov, Ariel Gabizon and David Zuckerman
- Random Selection with an Adversarial Majority Ronen Gradwohl, Salil Vadhan and David Zuckerman
- Expander Graphs for Digital Stream Authentication and Robust Overlay Networks Dawn Song, David Zuckerman and J.D. Tugar
- Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model Alexander Russell, Michael Saks and David Zuckerman
- Perfect Information Leader Election in log*n+O(1) Rounds Alexander Russell and David Zuckerman
- Tight Analyses of Two Local Load Balancing Algorithms Bhaskar Ghosh, F.T. Leighton, Bruce M. Maggs, S. Muthurkrishnan, C. Greg Plaxton, R. Rajaraman, Andrea W. Richa, Robert E. Tarjan and David Zuckerman
- Lower Bounds for Randomized Mutual Exclusion Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin and David Zuckerman
- Security preserving amplification of hardness Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan and David Zuckerman
ICALP 2019 arXiv 2016 CRYPTO 2006, revised 06/19/2006 IEEE Security and Privacy 2002 SICOMP 2002 STOC 1999, preliminary version JCSS 2001 FOCS 1998, preliminary version SICOMP 1999 STOC 1995, preliminary version SICOMP 1998 STOC 1993, preliminary version FOCS 1990 - See Robust Pseudorandom Generators under Other Pseudorandomness and Explicit Constructions, and Privacy Amplification and Non-Malleable Extractors Via Character Sums, Network Extractor Protocols, and Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography under Randomness Extractors and Applications.
## Other Computational Complexity- XOR Lemmas for Resilient Functions Against Polynomials Eshan Chattopadhyah, Pooya Hatami, Kaave Hosseini, Shachar Lovett and David Zuckerman
- Rectangles are Nonnegative Juntas Mika Goos, Shachar Lovett, Raghu Meka, Thomas Watson and David Zuckerman
- Mining Circuit Lower Bounds for Meta-Algorithms Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel and David Zuckerman
- Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number David Zuckerman
- Compression of Samplable Sources Luca Trevisan, Salil Vadhan and David Zuckerman
- Interaction in Quantum Communication and the Complexity of Set Disjointness Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma and David Zuckerman
- Derandomized Graph Products Noga Alon, Uriel Feige, Avi Wigderson and David Zuckerman
- On Unapproximable Versions of NP-Complete Problems David Zuckerman
ACM STOC 2020 SICOMP 2016 STOC 2015, preliminary version Computational Complexity 2015 CCC 2014, preliminary version Slides: Modified from the version given at IBM/NYU/Columbia Theory Day, STOC 2006, and elsewhere. Theory of Computing 2007 STOC 2006, preliminary version Computational Complexity 2005 CCC 2004, preliminary version IEEE Transactions on Information Theory 2007 STOC 2001, preliminary version Computational Complexity 1995 SICOMP 1996 Structures 1993, preliminary version ## Random Walks on Graphs- Multiple Cover Time Peter Winkler and David Zuckerman
- On the Time to Traverse all Edges of a Graph David Zuckerman
- A Technique for Lower Bounding the Cover Time David Zuckerman
- Covering Times of Random Walks on Bounded Degree Trees and Other Graphs David Zuckerman
Random Structures and Algorithms 1996 IPS 1991 SIAM Journal on Discrete Mathematics 1992 STOC 1990, preliminary version Journal of Theoretical Probability 1998 - See Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography, How to Recycle Random Bits, Derandomized Graph Products, and Lower Bounds for Randomized Mutual Exclusion.
## Randomized Algorithms- Optimal Speedup of Las Vegas Algorithms Michael Luby, Alistair Sinclair and David Zuckerman
IPL 1993 ISTCS 1993, prelimnary version ## Finance- See Certifiably Pseudorandom Financial Derivatives under Other Pseudorandomness and Explicit Constructions.
## Expository- The Conversation: How random is your randomness, and why does it matter? David Zuckerman and Eshan Chattopadhyay
- Can Random Coin Flips Speed Up a Computer? David Zuckerman
arXiv 2010 |