[edit]

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

*Proceedings of Thirty Fifth Conference on Learning Theory*, PMLR 178:5619-5623, 2022.

#### Abstract

The authors recently gave an almost-polynomial time membership query algorithm for properly learning decision trees under the uniform distribution~\citep{BLQT21}. The previous fastest algorithm for this problem ran in quasipolynomial time, a consequence of \cite{EH89}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.