Home

On Decision Trees, Influences, and Learning Monotone Decision Trees

Ryan O'Donnell; Rocco Anthony Servedio

Title:
On Decision Trees, Influences, and Learning Monotone Decision Trees
Author(s):
O'Donnell, Ryan
Servedio, Rocco Anthony
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-023-04
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:
159
Metadata:
text | xml
Suggested Citation:
Ryan O'Donnell, Rocco Anthony Servedio, 2004, On Decision Trees, Influences, and Learning Monotone Decision Trees, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:29225.

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use