Top-down induction of decision trees: rigorous guarantees and inherent limitations

Guy Blanc, Jane Lange, Li-Yang Tan

Consider the following heuristic for building a decision tree for a function $f:\{0,1{\}}^n\to \{\pm 1\}$. Place the most influential variable $x_i$ of $f$ at the root, and recurs…