# Properly Learning Decision Trees with Queries Is NP-Hard

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

## Key facts

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

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Distilling a Neural Network Into a Soft Decision Tree](https://mlsanity.com/paper/1711.09784/) (2017)
- [Interpretability via Model Extraction](https://mlsanity.com/paper/1706.09773/) (2017)
- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Interpreting Models via Single Tree Approximation](https://mlsanity.com/paper/1610.09036/) (2016)
- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Decision tree heuristics can fail, even in the smoothed setting](https://mlsanity.com/paper/2107.00819/) (2021)
- [Superpolynomial Lower Bounds for Learning Monotone Classes](https://mlsanity.com/paper/2301.08486/) (2023)

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

- [Towards a theory of model distillation](https://mlsanity.com/paper/2403.09053/) (2024)
- [The Probably Approximately Correct Learning Model in Computational Learning Theory](https://mlsanity.com/paper/2511.08791/) (2025)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [Superconstant Inapproximability of Decision Tree Learning](https://mlsanity.com/paper/2407.01402/) (2024)
- [Fast decision tree learning solves hard coding-theoretic problems](https://mlsanity.com/paper/2409.13096/) (2024)

## Abstract (arXiv)

We prove that it is NP-hard to properly PAC learn decision trees with queries, resolving a longstanding open problem in learning theory (Bshouty 1993; Guijarro-Lavin-Raghavan 1999; Mehta-Raghavan 2002; Feldman 2016). While there has been a long line of work, dating back to (Pitt-Valiant 1988), establishing the hardness of properly learning decision trees from random examples, the more challenging setting of query learners necessitates different techniques and there were no previous lower bounds. En route to our main result, we simplify and strengthen the best known lower bounds for a different problem of Decision Tree Minimization (Zantema-Bodlaender 2000; Sieling 2003). On a technical level, we introduce the notion of hardness distillation, which we study for decision tree complexity but can be considered for any complexity measure: for a function that requires large decision trees, we give a general method for identifying a small set of inputs that is responsible for its complexity. Our technique even rules out query learners that are allowed constant error. This contrasts with existing lower bounds for the setting of random examples which only hold for inverse-polynomial error. Our result, taken together with a recent almost-polynomial time query algorithm for properly learning decision trees under the uniform distribution (Blanc-Lange-Qiao-Tan 2022), demonstrates the dramatic impact of distributional assumptions on the problem.