# Superpolynomial Lower Bounds for Decision Tree Learning and Testing

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 94 references that are in the map.
- First posted on arXiv 12 Oct 2022.

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

- [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)
- [Hyperparameter Optimization: A Spectral Approach](https://mlsanity.com/paper/1706.00764/) (2017)
- [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)
- [Top-down induction of decision trees: rigorous guarantees and inherent limitations](https://mlsanity.com/paper/1911.07375/) (2019)
- [Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications](https://mlsanity.com/paper/1803.06521/) (2018)
- [VC Dimension and Distribution-Free Sample-Based Testing](https://mlsanity.com/paper/2012.03923/) (2020)
- [Downsampling for Testing and Learning in Product Distributions](https://mlsanity.com/paper/2007.07449/) (2020)
- [Low Degree Testing over the Reals](https://mlsanity.com/paper/2204.08404/) (2022)
- [Testing Halfspaces over Rotation-Invariant Distributions](https://mlsanity.com/paper/1811.00139/) (2018)
- [Almost Optimal Distribution-free Junta Testing](https://mlsanity.com/paper/1901.00717/) (2019)
- [Distribution-Free Testing of Linear Functions on R^n](https://mlsanity.com/paper/1909.03391/) (2019)
- [Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions](https://mlsanity.com/paper/1511.03333/) (2015)
- [Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems](https://mlsanity.com/paper/2008.05374/) (2020)
- [On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes](https://mlsanity.com/paper/2009.02778/) (2020)
- [Reconstructing decision trees](https://mlsanity.com/paper/2012.08735/) (2020)

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

- [Towards a theory of model distillation](https://mlsanity.com/paper/2403.09053/) (2024)
- [Properly Learning Decision Trees with Queries Is NP-Hard](https://mlsanity.com/paper/2307.04093/) (2023)
- [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)
- [New Statistical and Computational Results for Learning Junta Distributions](https://mlsanity.com/paper/2505.05819/) (2025)
- [The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)](https://mlsanity.com/paper/2602.01054/) (2026)
- [Decision Tree Learning on Product Spaces](https://mlsanity.com/paper/2605.12983/) (2026)

## Abstract (arXiv)

We establish new hardness results for decision tree optimization problems, adding to a line of work that dates back to Hyafil and Rivest in 1976. We prove, under randomized ETH, superpolynomial lower bounds for two basic problems: given an explicit representation of a function f and a generator for a distribution D, construct a small decision tree approximator for f under D, and decide if there is a small decision tree approximator for f under D. Our results imply new lower bounds for distribution-free PAC learning and testing of decision trees, settings in which the algorithm only has restricted access to f and D. Specifically, we show: n-variable size-s decision trees cannot be properly PAC learned in time n^tildeO(loglog s), and depth-d decision trees cannot be tested in time exp(d,O(1)). For learning, the previous best lower bound only ruled out poly(n)-time algorithms (Alekhnovich, Braverman, Feldman, Klivans, and Pitassi, 2009). For testing, recent work gives similar though incomparable bounds in the setting where f is random and D is nonexplicit (Blais, Ferreira Pinto Jr., and Harms, 2021). Assuming a plausible conjecture on the hardness of Set-Cover, we show our lower bound for learning decision trees can be improved to nOmega(log s), matching the best known upper bound of nO(log s) due to Ehrenfeucht and Haussler (1989). We obtain our results within a unified framework that leverages recent progress in two lines of work: the inapproximability of Set-Cover and XOR lemmas for query complexity. Our framework is versatile and yields results for related concept classes such as juntas and DNF formulas.