STOC 2009, Day 0

The Saturday before STOC was devoted to a 60th birthday celebration for Les Valiant. The program is here. I'm afraid I missed most of the morning talks because I didn't fly in until the morning, but the afternoon talks were really very good. (I hope the speakers will all put their slides up on their web pages -- it's useful for everyone!) Some brief highlights, with apologies to those talks I don't describe:

Rocco Servedio started the afternoon with a short survey of learning theory, starting with the foundations laid by Valiant's PAC-learning paper and some of the early work in the area, and then connecting it to recent results and still-open problems in learning theory today.

Michael Kearns followed with a talk that highlighted the impact of this early work on the development of the machine learning community and how it is practiced today. One point he highlighted is that Les was not content to just publish his CACM article on the theory of the learnable, but was proactive in trying to ensure that the ideas reached other communities (in particular the machine learning community) so that they could really bloom. I think a hallmark of Les's work is his willingness to not only "focus the computational lens" on other areas but also to try to frame models in ideas in ways that those other areas can further build on them.

Vitaly Feldman provided a well-presented short survey of Les's more recent work on evolvability, and his own work in that area.

Avi Wigderson closed with a talk showing some of the threads and connections leading from Les's work, focused primarily on theoretical results related to the permanent. One of the really nice things about this talk was that Avi tried to close his quick discussions of each thread by listing some remaining open problems. I really enjoy surveys that are structured this way -- not just "here's what was done" but a clear sign of "and here's what's still left to do". I've encouraged Avi (and will do so again) to get the slides for this talk up on his web site as soon as possible; it should be a useful resource for people (especially graduate students) looking for problems to think about.

Perhaps the one disappointment for the day is Les himself didn't give a talk. But that's not surprising to me; Les avoids self-promotion, and lets his work speak for himself. I think the program itself pleasantly overwhelmed him, and provided a remarkable display of all that he has given the theory community (and the broader scientific community) through his work.