# Fast decision tree learning solves hard coding-theoretic problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 69 references that are in the map.
- First posted on arXiv 19 Sep 2024.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Tabular Data: Deep Learning is Not All You Need](https://mlsanity.com/paper/2106.03253/) (2021)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Top-down induction of decision trees: rigorous guarantees and inherent limitations](https://mlsanity.com/paper/1911.07375/) (2019)
- [Towards a theory of model distillation](https://mlsanity.com/paper/2403.09053/) (2024)
- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)](https://mlsanity.com/paper/1910.11850/) (2019)
- [A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms](https://mlsanity.com/paper/2006.04411/) (2020)
- [Properly Learning Decision Trees with Queries Is NP-Hard](https://mlsanity.com/paper/2307.04093/) (2023)

## Abstract (arXiv)

We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem (k-NCP). Despite significant effort by the respective communities, algorithmic progress on both problems has been stuck: the fastest known algorithm for the former runs in quasipolynomial time (Ehrenfeucht and Haussler 1989) and the best known approximation ratio for the latter is O(n/log n) (Berman and Karpinsky 2002; Alon, Panigrahy, and Yekhanin 2009). Research on both problems has thus far proceeded independently with no known connections. We show that textitany improvement of Ehrenfeucht and Haussler's algorithm will yield O(log n)-approximation algorithms for k-NCP, an exponential improvement of the current state of the art. This can be interpreted either as a new avenue for designing algorithms for k-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler's algorithm. Furthermore, our reduction along with existing inapproximability results for k-NCP already rule out polynomial-time algorithms for properly learning decision trees. A notable aspect of our hardness results is that they hold even in the setting of textitweak learning whereas prior ones were limited to the setting of strong learning.