| On decision trees, influences, and learning monotone decision trees (2004) | |||||
Abstract | |||||
| In this note we prove that a monotone boolean function computable by a decision tree of size $s$ has average sensitivity at most $\sqrt{\log_2 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. | |||||
Publication details | |||||
| |||||