# Open Problem: Properly learning decision trees in polynomial time?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 12 references that are in the map.
- First posted on arXiv 29 Jun 2022.

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

- [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)

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

- [Decision Tree Learning on Product Spaces](https://mlsanity.com/paper/2605.12983/) (2026)

## Abstract (arXiv)

The authors recently gave an nO(loglog n) time membership query algorithm for properly learning decision trees under the uniform distribution (Blanc et al., 2021). The previous fastest algorithm for this problem ran in nO(log n) time, a consequence of Ehrenfeucht and Haussler (1989)'s classic algorithm for the distribution-free setting. In this article we highlight the natural open problem of obtaining a polynomial-time algorithm, discuss possible avenues towards obtaining it, and state intermediate milestones that we believe are of independent interest.