# Inapproximability of sufficient reasons for decision trees

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 11 references that are in the map.
- First posted on arXiv 5 Apr 2023.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022)

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

- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Probabilistic Linear Explanations](https://mlsanity.com/paper/2609.19077/) (2026)

## Abstract (arXiv)

In this note, we establish the hardness of approximation of the problem of computing the minimal size of a δ-sufficient reason for decision trees.