On Decision Trees, Influences, and Learning Monotone Decision Trees
Ryan W. O’Donnell, Rocco A. Servedio · 2004
In this note we prove that a monotone boolean function computable by a decision tree of size s has average sensitivity at most √ log2 s. As a consequence we show that monotone functions are learnable to constant accuracy under the uniform distribution in time polynomial in their decision tree size.