Group:Complexity Group
Title: Learning Monotone Decision Trees in Polynomial Time
Speaker: Elad Verbin Tsinghua university
Time: 2010-05-12 15:30-2010-05-12 17:00
Venue: FIT 1-222


I will present a paper by O'Donnell and Servedio, where they show how to learn monotone decision trees in polynomial time, over the uniform distribution and *without* membership queries. This is, in my eyes, one of the most interesting papers in learning Boolean functions, and is a state-of-the-art result, which we have a lot to learn from. I will ask many open questions, some of which might even be solvable!

No prior knowledge is assumed. In particular, I will introduce all the required knowledge from analysis of Boolean functions, so there's no excuse not to come.

The paper is available here:

Short Bio: