Rocco A. Servedio
- Bounded Independence Fools Halfspaces
2009/02/21 by Ilias Diakonikolas, Diakonikolas, Ilias, Parikshit Gopalan +7 · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Machine Learning and Algorithms
- Learning mixtures of structured distributions over discrete domains
2012/10/02 by Siu-On Chan, Ilias Diakonikolas, Chan, Siu-on +5 · 6 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Mathematics #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning and Algorithms #Statistics Theory (math.ST)
- Average sensitivity and noise sensitivity of polynomial threshold functions
2009/09/28 by Ilias Diakonikolas, Prasad Raghavendra, Diakonikolas, Ilias +5 · 3 citations
Computer Science · #Machine Learning and Algorithms #Algorithms and Data Compression #Complexity and Algorithms in Graphs
- Learning Poisson Binomial Distributions
2011/07/13 by Constantinos Daskalakis, Ilias Diakonikolas, Daskalakis, Constantinos +3 · 2 citations
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning and Algorithms #Statistics Theory (math.ST)
- Addition is exponentially harder than counting for shallow monotone\n circuits
2015/08/12 by Xi Chen, Igor Carboni Oliveira, Chen, Xi +3 · 2 citations
Computer Science · Engineering · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Low-power high-performance VLSI design #Machine Learning and Algorithms
- Improved Approximation of Linear Threshold Functions
2009/10/19 by Ilias Diakonikolas, Rocco A. Servedio, Diakonikolas, Ilias +1 · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques
- New algorithms and lower bounds for monotonicity testing
2014/12/17 by Xi Chen, Chen, Xi, Rocco A. Servedio +3 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Machine Learning and Algorithms
- Distribution-free Junta Testing
2018/02/13 by Xi Chen, Zhengyang Liu, Chen, Xi +7 · 2 citations
Computer Science · #Machine Learning and Algorithms #Complexity and Algorithms in Graphs #Optimization and Search Problems
- Every decision tree has an influential variable
2005/08/16 by Ryan O'Donnell, Ryan O’Donnell, Michael Saks +6 · 1 citation
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
- Sharp bounds for population recovery
2017/03/04 by Anindya De, Ryan O’Donnell, De, Anindya +3 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Search Problems #Statistics Theory (math.ST)
- Private Data Release via Learning Thresholds
2011/07/13 by Moritz Hardt, Guy N. Rothblum, Hardt, Moritz +3 · 1 citation
Computer Science · #Privacy-Preserving Technologies in Data #Cryptography and Data Security #Complexity and Algorithms in Graphs
- Testing Convex Truncation
2023/05/04 by Anindya De, Shivam Nadimpalli, De, Anindya +3 · 2 citations
Computer Science · Mathematics · #Machine Learning and Algorithms #Statistical Methods and Inference #Bayesian Modeling and Causal Inference
- Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
2023/09/21 by Xi Chen, Anindya De, Chen, Xi +7 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning and Algorithms
- Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals
2022/02/10 by Daniel Hsu, Hsu, Daniel, Clayton Sanford +5 · 1 citation
Computer Science · #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification
- Trace reconstruction from local statistical queries
2024/07/15 by Xi Chen, Anindya De, Chen, Xi +5 · 1 citation
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Image Retrieval and Classification Techniques
- Lower Bounds for Convexity Testing
2024/10/23 by Xin Chen, Anindya De, Chen, Xi +7 · 2 citations
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
- A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
2025/04/22 by Xi Chen, Chen, Xi, Shyamal Patel +3 · 1 voice · 1 citation
#cs.DS
- Relative-error monotonicity testing
2024/10/11 by Xi Chen, Anindya De, Chen, Xi +11 · 2 citations
Decision Sciences · Mathematics · Engineering · #Advanced Statistical Process Monitoring #Advanced Statistical Methods and Models #Fault Detection and Control Systems
- The Probably Approximately Correct Learning Model in Computational Learning Theory
2025/11/11 by Rocco A. Servedio, Servedio, Rocco A. · 1 voice · 1 citation
#stat.ML #cs.LG