Saks, Michael
- A Polynomial Time Algorithm for Lossy Population Recovery
2013/02/06 by Ankur Moitra, Michael Saks, Moitra, Ankur +1 · 4 citations
Computer Science · #Machine Learning and Algorithms #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
- Every decision tree has an influential variable
2005/08/16 by Ryan O'Donnell, Ryan O’Donnell, O'Donnell, Ryan +6 · 3 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Probability (math.PR) #cs.CC #cs.DM #math.PR
- On the Discrepancy of Random Matrices with Many Columns
2018/07/11 by Franks, Cole, Saks, Michael · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
- A lower bound on the quantum query complexity of read-once functions
2002/01/03 by Howard Barnum, Michael Saks, Barnum, Howard +1 · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
- Noisy population recovery in polynomial time
2016/02/24 by Anindya De, Michael Saks, De, Anindya +3 · 2 citations
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and ELM #Optimization and Search Problems
- A Tail Bound for Read-k Families of Functions
2012/04/25 by Shachar Lovett, Gavinsky, Dmytro, Lovett, Shachar +4 · 1 citation
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Rough Sets and Fuzzy Logic
- Nearly Optimal List Labeling
2024/05/01 by Bender, Michael A., Conway, Alex, Farach-Colton, Martín +4 · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
- An Asymptotically Tight Bound on the Number of Relevant Variables in a\n Bounded Degree Boolean Function
2018/01/25 by John Chiarelli, Pooya Hatami, Chiarelli, John +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms
- Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
2024/06/18 by Aditi Dudeja, Rashmika Goswami, Dudeja, Aditi +3 · 2 citations
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs