mlsanityData to 7 Oct 2026

Inapproximability of sufficient reasons for decision trees

arXiv 2304.02781 ↗First posted 5 Apr 2023cs.CC cs.AIcited by 3

Not on the map. Why?

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.

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

Builds on

5 of 11 references.

References · 5

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,488
  2. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 130
  3. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
  4. 2021SAT-Based Rigorous Explanations for Decision Listscited by 40
  5. 2022On Computing Probabilistic Explanations for Decision Treescited by 35

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Additive Models Explained: A Computational Complexity Approachcited by 3
  2. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 1
  3. 2026Probabilistic Linear Explanationscited by 0