Speaker Name/Affiliation: Rocco Servedio/Columbia
University

Talk Title: Learning Monotone Decision Trees in Polynom

ial-Time

Date/Time: March 24 2005 at 11:30 a.m.

Coffee: 11:

15 a.m.

Location: ACES 3.408

Host: Adam Klivans

Talk
Abstract:
One of the most tantalizing open questions in computational <

br>learning theory is the following: can monotone DNF formulas be learned

in polynomial time using uniform random examples only?

In this w

ork we give an algorithm that learns monotone decision
trees (a weaker

representation scheme than DNF formulas) to any constant
accuracy in po

lynomial time. Equivalently our algorithm learns
any n-variable monot

one Boolean function f to any constant accuracy using only uniformly distr

ibuted random examples in time polynomial in n and in the decision tree si

ze of f. This is the first algorithm that can learn any monotone Boolean fu

nction to high accuracy using random examples only in time which is polyn

omial in a reasonable measure of the complexity of f.

A key ingredie

nt of the result is a new upper bound showing
that the average sensitiv

ity of any monotone function computed by
a decision tree of size s is a

t most %5Csqrt%7Blog s%7D.