David Zuckerman

1. Optimal Testing of Reed-Muller Codes
   2009/10/04 by Arnab Bhattacharyya, Swastik Kopparty, Bhattacharyya, Arnab +7 · 3 citations
   Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning and Algorithms #cs.CC #cs.IT #math.CO #math.IT #semigroups and automata theory
2. Linear degree extractors and the inapproximability of max clique and chromatic number
   2006/05/21 by David Zuckerman · 3 citations
   Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Computational Geometry and Mesh Generation #Randomness #Combinatorics #Mathematics #Clique #Constant (computer programming) #Entropy (arrow of time) #Binary logarithm #Time complexity #Discrete mathematics #Hypergraph #Degree (music) #Randomized algorithm #Chromatic scale #Computer science #Statistics #Physics
3. Pseudorandom Generators for Polynomial Threshold Functions
   2009/10/21 by Raghu Meka, Meka, Raghu, David Zuckerman +1 · 4 citations
   Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Numerical Methods and Algorithms #cs.CC
4. Privacy Amplification and Non-Malleable Extractors Via Character Sums
   2011/02/26 by Yevgeniy Dodis, Xin Li, Dodis, Yevgeniy +5 · 1 citation
   Computer Science · Mathematics · #94A62 (Primary) 11L40 (Secondary) #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #cs.CC #cs.CR #math.NT #msc:11L40 #msc:94A62
5. Optimal speedup of Las Vegas algorithms
   1993/09/01 by Michael Luby, Alistair Sinclair, David Zuckerman · 1 citation
6. On Unapproximable Versions of NP-Complete Problems
   1996/12/01 by David Zuckerman · 1 citation
   Computer Science · Mathematics · #Binary logarithm #Clique #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Counting problem #Discrete mathematics #Exponential time hypothesis #Iterated function #Law of the iterated logarithm #Logarithm #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Mathematics #Monotone polygon #Polynomial #Randomized algorithm #Simple (philosophy) #Time complexity