# Superconstant Inapproximability of Decision Tree Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 47 references that are in the map.
- First posted on arXiv 1 Jul 2024.

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Hyperparameter Optimization: A Spectral Approach](https://mlsanity.com/paper/1706.00764/) (2017)
- [Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications](https://mlsanity.com/paper/1803.06521/) (2018)
- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Properly Learning Decision Trees with Queries Is NP-Hard](https://mlsanity.com/paper/2307.04093/) (2023)

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

- [Conformal Information Pursuit for Interactively Guiding Large Language Models](https://mlsanity.com/paper/2507.03279/) (2025)
- [A Goemans-Williamson type algorithm for identifying subcohorts in clinical trials](https://mlsanity.com/paper/2506.10879/) (2025)

## Abstract (arXiv)

We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothesis tree T is required to be optimally small, is NP-hard. Their work leaves open the question of whether the task remains intractable if T is only required to be close to optimal, say within a factor of 2, rather than exactly optimal. We answer this affirmatively and show that the task indeed remains NP-hard even if T is allowed to be within any constant factor of optimal. More generally, our result allows for a smooth tradeoff between the hardness assumption and the inapproximability factor. As Koch et al.'s techniques do not appear to be amenable to such a strengthening, we first recover their result with a new and simpler proof, which we couple with a new XOR lemma for decision trees. While there is a large body of work on XOR lemmas for decision trees, our setting necessitates parameters that are extremely sharp, and are not known to be attainable by existing XOR lemmas. Our work also carries new implications for the related problem of Decision Tree Minimization.