Home

On Decision Trees, Influences, and Learning Monotone Decision Trees

Ryan O'Donnell; Rocco Anthony Servedio; Columbia University. Computer Science

Title:
On Decision Trees, Influences, and Learning Monotone Decision Trees
Author(s):
O'Donnell, Ryan; Servedio, Rocco Anthony; Columbia University. Computer Science
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:
156
Metadata:
text | xml

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