Technical reports:
On Decision Trees, Influences, and Learning Monotone Decision Trees
Ryan O'Donnell; Rocco Anthony Servedio
Downloads:
- Title:
- On Decision Trees, Influences, and Learning Monotone Decision Trees
- Author(s):
-
O'Donnell, Ryan
Servedio, Rocco Anthony - Date:
- 2004
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:29225
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-023-04
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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.
- Subject(s):
- Computer science
- Item views:
- 102