Reports

On Decision Trees, Influences, and Learning Monotone Decision Trees

O'Donnell, Ryan; Servedio, Rocco Anthony

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.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-023-04
Published Here
April 22, 2011