Inapproximability of sufficient reasons for decision trees

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

cs.CC cs.AI Computer Science Mathematics

View graph Source

Paper

Similar papers

On the Explanatory Power of Decision TreesGilles Audemard, Steve Bellart, Louènas Bounia et al.2021 · arXiv (Cornell University) · 15 citations In Library

Superconstant Inapproximability of Decision Tree LearningCaleb Koch, Carmen Strassle, Li-Yang Tan2024 · arXiv (Cornell University) · 3 citations In Library

On Computing Probabilistic Explanations for Decision TreesMarcelo Arenas, Pablo Barceló, Miguel Romero et al.2022 · arXiv (Cornell University) · 54 citations In Library

On Computing Probabilistic Explanations for Decision TreesMarcelo Arenas, Pablo Barceló, Alexander Kozachinskiy et al.2025 · Journal of Artificial Intelligence Research · 0 citations In Library

Computing an Approximating Version of a Minimum-Size Explanation for Boolean Decision Tree ClassifiersLouenas Bounia2025 · HAL (Le Centre pour la Communication Scientifique Directe) In Library

On the explanatory power of Boolean decision treesGilles Audemard, Steve Bellart, Louènas Bounia et al.2022 · Data & Knowledge Engineering · 53 citations In Library

Provably Precise, Succinct and Efficient Explanations for Decision TreesYacine Izza, Alexey Ignatiev, Nina Narodytska et al.2022 · arXiv (Cornell University) · 10 citations In Library

Superpolynomial Lower Bounds for Decision Tree Learning and TestingCaleb Koch, Carmen Strassle, Li-Yang Tan2022 · arXiv (Cornell University) · 12 citations In Library

On the Computation of Necessary and Sufficient ExplanationsAdnan Darwiche, Chunxi Ji2022 · AAAI Conference on Artificial Intelligence · 36 citations In Library

Top-down induction of decision trees: rigorous guarantees and inherent limitationsGuy Blanc, Jane Lange, Li-Yang Tan2019 · Electron. Colloquium Comput. Complex. · 30 citations In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal