mlsanityData to 14 Oct 2026

Open Problem: Properly learning decision trees in polynomial time?

arXiv 2206.14431 ↗First posted 29 Jun 2022cs.DS cs.LG stat.MLcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

2 of 12 references.

References · 2

  1. 2021Properly learning decision trees in almost polynomial timecited by 20
  2. 2019Top-down induction of decision trees: rigorous guarantees and inherent limitationscited by 17

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Decision Tree Learning on Product Spacescited by 0