讨论组:复杂性研究组
标题:Learning Monotone Decision Trees in Polynomial Time
演讲人: Elad Verbin 清华大学
时间: 2010-05-12 15:30-2010-05-12 17:00
地点: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: http://www.cs.columbia.edu/~rocco/papers/ccc06os.html




人物介绍: