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
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:
154
Metadata:
text | xml

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