The FOCS talks are now available online! I waited until now to report on FOCS for this very reason. I am not about to compete with Suresh or Lance for live blogging conferences. I’m not sure where they find the time amidst talks and meetings in hallways to do so. (I have to say, whenever I can’t make it to a conference, I very much appreciate such posts.) I did manage to find the time to circle a few listings in my wonderfully compact one-page program as a reminder that I liked these talks and to point my students to them. Of course, now I’ve forgotten why I liked them, but I can almost certainly guarantee that I was kept engaged throughout the talk and learnt something – a vote of confidence if I ever heard it!
In no particularly order (unfortunately it is not possible to link directly to the talk, so you’ll have to go and find them in the list):
- The geometry of scheduling presented by Nikhil Bansal.
Coauthored with Kirk Pruhs. I added the ever-so-wonderful note to my program: ‘neat not tight geometry problem’.
- Fast approximation algorithms for cut-based graph problems presented by Alexander Madry
I probably enjoyed the fact that Alex did not stand at the podium but walked around, indicating things on the slide (novel!). Unfortunately the camera does not move from the podium. Ghost speaker!
- Approximating maximum weight matching in near-linear time presented by Seth Pettie
Coauthored with his student, Ran Duan. I’ve always enjoyed and always learned something from Seth’s talks. I wonder if we could have a rating system for speakers with little stars in the program so that you can attend talks well outside your comfort zone if you know the speaker will be good?
- A separator theorem in minor-closed classes presented by Ken-ichi Kawarabayashi.
Coauthored with Bruce Reed. This talk had an amazingly thorough introduction that perhaps those new to H-minor-free graphs might appreciate
- Logspace versions of the theorems of Bodlaender and Courcells by Michael Eberfield.
Coauthored with Andreas Jakoby and Till Tantau. I love the example tree decomposition and his slides more generally. I keep meaning to ask him for his slides to get that tree decomposition figure …
- A nonlinear lower bound for planar epsilon-nets by Noga Alon.
Some of the best humour at the conference.
- And of course Dan Spielman’s Nevanlinna-Prize talk Laplacian Gems. I have heard that his prize talk at ICM was amazing too, but I haven’t watched it yet.
So there’s three hours of fun theory listening for you. I think they would pair well with a fine bottle of Oregon Gewurztraminer.