Open Problem: Properly learning decision trees in polynomial time?
The authors recently gave an $n^{O(\log\log 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
$n^{O(\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.