HomeHome

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:
Reports
Department(s):
Computer Science
Persistent 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 √ 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.
Subject(s):
Computer science
Item views
198
Metadata:
text | xml
Suggested Citation:
Ryan O'Donnell, Rocco Anthony Servedio, , On Decision Trees, Influences, and Learning Monotone Decision Trees, Columbia University Academic Commons, .

Columbia University Libraries | Policies | FAQ