# The Computational Complexity of Concise Hypersphere Classification

arXiv: https://arxiv.org/abs/2312.07103 · HTML: https://mlsanity.com/paper/2312.07103/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 12 Dec 2023.

## Builds on (most cited first, 17 of 17)

- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Scalable Rule-Based Representation Learning for Interpretable Classification](https://mlsanity.com/paper/2109.15103/) (2021)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Accuracy, Interpretability, and Differential Privacy via Explainable Boosting](https://mlsanity.com/paper/2106.09680/) (2021)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis](https://mlsanity.com/paper/2004.14724/) (2020)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Parameterized Complexity Results for Exact Bayesian Network Structure Learning](https://mlsanity.com/paper/1402.0558/) (2014)
- [GANMEX: One-vs-One Attributions Guided by GAN-based Counterfactual Explanation Baselines](https://mlsanity.com/paper/2011.06015/) (2020)
- [A Single-Exponential Time 2-Approximation Algorithm for Treewidth](https://mlsanity.com/paper/2104.07463/) (2021)
- [Provably Precise, Succinct and Efficient Explanations for Decision Trees](https://mlsanity.com/paper/2205.09569/) (2022)
- [Parameterized Algorithms for the Matrix Completion Problem](https://mlsanity.com/paper/1804.03423/) (2018)
- [Refined Complexity of PCA with Outliers](https://mlsanity.com/paper/1905.04124/) (2019)
- [Separating bichromatic point sets in the plane by restricted orientation convex hulls](https://mlsanity.com/paper/2209.04258/) (2022)

## Built on by (most cited first, 1 of 1)

- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)

## 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.