2004 Reports
On Decision Trees, Influences, and Learning Monotone Decision Trees
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
- cucs-023-04.pdf application/pdf 82.1 KB Download File
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