论文标题
开放问题：在多项式时间内正确学习决策树？
Open Problem: Properly learning decision trees in polynomial time?
论文作者
论文摘要
作者最近给出了$ n^{o（\ log \ log n）} $时间成员资格查询算法，用于在统一分布下正确学习决策树（Blanc等，2021）。以前的此问题的最快算法以$ n^{o（\ log n）} $时间运行，这是Ehrenfeucht和Haussler（1989）的经典算法，这是用于无分配设置的经典算法。在本文中，我们强调了获得多项式时间算法的自然开放问题，讨论获得它的可能途径以及我们认为具有独立利益的状态中级里程碑。
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.
