The Computational Complexity of Concise Hypersphere Classification
Not on the map. Why?
Abstract (arXiv)
Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued and binary data. However, obtaining an (ideally concise) explanation via hypersphere classification is much more difficult when dealing with binary data than real-valued data. In this paper, we perform the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data as well as potential conciseness constraints. Our results include stronger lower bounds and new fixed-parameter algorithms for hypersphere classification of binary data, which can find an exact and concise explanation when one exists.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 17 of its 55 references that are in the map. First posted on arXiv 12 Dec 2023.
Builds on
17 of 55 references.
References · 17
- 2016The Mythos of Model Interpretabilitycited by 716
- 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 130
- 2020On The Reasons Behind Decisionscited by 99
- 2020Model Interpretability through the Lens of Computational Complexitycited by 75
- 2021Scalable Rule-Based Representation Learning for Interpretable Classificationcited by 40
- 2021Provably efficient, succinct, and precise explanationscited by 32
- 2021Accuracy, Interpretability, and Differential Privacy via Explainable Boostingcited by 24
- 2021On the price of explainability for some clustering problemscited by 21
- 2020Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysiscited by 13
- 2021Near-optimal Algorithms for Explainable k-Medians and k-Meanscited by 13
- 2014Parameterized Complexity Results for Exact Bayesian Network Structure Learningcited by 11
- 2020GANMEX: One-vs-One Attributions Guided by GAN-based Counterfactual Explanation Baselinescited by 8
5 more
- 2021A Single-Exponential Time 2-Approximation Algorithm for Treewidthcited by 8
- 2022Provably Precise, Succinct and Efficient Explanations for Decision Treescited by 8
- 2018Parameterized Algorithms for the Matrix Completion Problemcited by 7
- 2019Refined Complexity of PCA with Outlierscited by 7
- 2022Separating bichromatic point sets in the plane by restricted orientation convex hullscited by 1
Built on by
Citing papers per year: 2025: 1.
1 paper.