vix.ing · top · new · best · stats · spec

Li-Yang Tan

  1. Average sensitivity and noise sensitivity of polynomial threshold functions
    2009/09/28 by Ilias Diakonikolas, Diakonikolas, Ilias, Prasad Raghavendra +5 · 3 citations
    Computer Science · #Machine Learning and Algorithms #Algorithms and Data Compression #Complexity and Algorithms in Graphs
  2. New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
    2012/10/20 by Per Austrin, Austrin, Per, Ryan O’Donnell +5 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Optimization and Search Problems
  3. Almost 3-Approximate Correlation Clustering in Constant Rounds
    2022/05/07 by Soheil Behnezhad, Behnezhad, Soheil, Moses Charikar +5 · 3 citations
    Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Topological and Geometric Data Analysis #and Cluster Computing (cs.DC)
  4. New algorithms and lower bounds for monotonicity testing
    2014/12/17 by Xi Chen, Rocco A. Servedio, Chen, Xi +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
  5. On the power of adaptivity in statistical adversaries
    2021/11/19 by Guy Blanc, Jane Lange, Blanc, Guy +5 · 2 citations
    Computer Science · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference
  6. A composition theorem for parity kill number
    2013/12/07 by Ryan O’Donnell, Xiaorui Sun, O'Donnell, Ryan +7 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #semigroups and automata theory
  7. Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries
    2014/12/17 by Xi Chen, Chen, Xi, Anindya De +5 · 1 citation
    Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms
  8. Lifting uniform learners via distributional decomposition
    2023/03/27 by Guy Blanc, Jane Lange, Blanc, Guy +5 · 3 citations
    Computer Science · #Machine Learning and Algorithms #Machine Learning and Data Classification #Imbalanced Data Classification Techniques
  9. Top-down induction of decision trees: rigorous guarantees and inherent limitations
    2019/11/17 by Guy Blanc, Blanc, Guy, Jane Lange +3 · 1 citation
    Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification
  10. Query strategies for priced information, revisited
    2020/10/22 by Guy Blanc, Jane Lange, Blanc, Guy +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Machine Learning and Algorithms
  11. Superconstant Inapproximability of Decision Tree Learning
    2024/07/01 by Caleb Koch, Koch, Caleb, Carmen Strassle +3 · 2 citations
    Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Fuzzy Logic and Control Systems #Machine Learning (cs.LG) #Neural Networks and Applications #Rough Sets and Fuzzy Logic
  12. Properly Learning Decision Trees with Queries Is NP-Hard
    2023/07/09 by Caleb Koch, Carmen Strassle, Koch, Caleb +3 · 1 citation
    Computer Science · #Bayesian Modeling and Causal Inference #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 Data Classification
  13. The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
    2024/09/17 by Guy Blanc, Blanc, Guy, Alexandre Hayderi +5 · 1 citation
    Computer Science · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Rough Sets and Fuzzy Logic