Properly learning decision trees in almost polynomial time

Guy Blanc, Jane Lange, Mingda Qiao +1

We give an $n^{O(\log \log n)}$-time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over $\{\pm 1{\}}^n$. Even in the…