Lower Bounds on Learning Decision Lists and Trees

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Learning Optimal Decision Trees with SAT (2018, background): “On the negative side, the construction of optimal decision trees is well-known to be NP-hard, for different notions of optimality [Hyaﬁl and Rivest, 1976; Hancock et al. , 1996].”
Budding Trees (2014, background): “That is why, decision tree induction algorithms are greedy—they do not guarantee finding the smallest decision tree but they learn in reasonable time.”
Efficient Inference of Optimal Decision Trees (2020, background): “…an optimal decision tree is known to be NP-complete for these two basic criteria but also for several other deﬁnitions of optimality (Hyaﬁl and Rivest 1976; Hancock et al. 1996) and it is also hard to approximate up to any constant factor under the assumption P (cid:54) = NP (Sieling 2008;…”
Top-down induction of decision trees classifiers - a survey (2005, background): “Induction of an optimal decision tree from a given data is considered to be hard task.”
SAT-Based Encodings for Optimal Decision Trees with Explicit Paths (2020, background): “However, despite this simplicity, minimization of decision trees is well-known to be an NP-hard problem [10,16].”
Learning optimal decision trees using constraint programming (2020, background): “The problem of finding a decision tree minimizing the number of leaves is also proven NP-complete in [13].”