I recently gave a pair of talks in the Math Department’s Applied Math Seminar on basics of TCS. It was intended for a mathematically mature audience with no background in TCS. The slides for the talk are available here; they are far from perfect — but I will happily take suggestions on things that should be dropped or added. Interest in the talk was pleasantly high. High enough that I plan on doing this again and advertising more broadly — to graduate students in physics, engineering, etc. I also think it acts as a list of topics about which students should be able to answer questions during a comprehensive exam.
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.
ETP is an event for undergraduates with talent and interest in theoretical computer science, sponsored by the theory groups at the University of Washington and Microsoft Research. The purpose of the event is to exchange ideas about exciting results and research directions in theoretical computer science, and enjoy Seattle in all its summer glory.
Anna Karlin is organizing and asked me to join in. It’s a great group of students and a great excuse to spend some time at UW and MSR. There have been about 15 technical talks aimed at senior-year, bright undergrads.1 In an attempt to minimize the time I spend designing talks, I used a new presentation method – Prezi. I’ve used it before and was perhaps a little too excited about it. As critics would point out, I didn’t take full advantage of Prezi: I designed this poster2 in Illustrator with a tablet, exported to Prezi as swf and then added “frames” in order to navigate around the poster. Why? Prezi was frustrating to work with, figures would have to be uploaded one by one, jpegs cannot be uploaded in high enough resolution to zoom in on, uploading a pdf plain failed. I was worried about (lack of) reusability. At least now I have a reusable poster.
There were a few technical issues: I couldn’t use a remote to run the presentation; I forgot to manually set the “sleep” time on my laptop (accustomed to this being automatically set by Keynote); manual navigation sometimes did unexpected, non-deterministic things. Prezi was cute and flashy, but I wouldn’t use it for a longer talk or a more technical talk. Overall, I wouldn’t recommend it.
1 The level of the talks, at least on topics of which I am the least informed, was perfect for me – a gentle introduction. Disconcerting, maybe. Perhaps I am just too slow to follow the standard (short) technical talk in our field. 2 Which I hope to print out on a plotter and put up in my department. Look! Pretty pictures!
I recently found out that when I gave my job talk at Oregon State University last year, I was being recorded. I was hesitant to post it, but I hope that, despite this far-from-perfect performance, it might be useful to those on the job market this year. Note that Oregon State is not a theory school. I was talking to an audience of grad students and faculty, none of whom (except one) work in algorithms. If I was giving a talk at a theory powerhouse, I probably would have targeted differently.
I broke a lot of standard rules in giving this job talk. First and foremost, I did not practice it. *gasp* Practice would have removed a lot of my “um”s and “uh”s. In my defence, when I practice a talk too much, I find it gets stale. However, practicing it once from start-to-finish would have been a good idea. In watching this talk (as painful as it is), I think the best thing I could have done was to tape myself once.
Second, I climbed on a chair. I was offered a laser pointer, but I hate laser pointers. They are hard to keep steady and the point is very small and hard to see for the audience. I find it about as useful as the speaker pointing to their laptop screen while they give a presentation. So, at some point I wanted to point at something that too high for me, so I climbed on a chair.
Another minor thing that I wish I would get in the habit of doing is repeating an asked question. Taking two seconds to summarize the question both confirms that you are answering the intended question and allows the entire audience to hear both the question and the answer.
The slides for the talk are available for Keynote and Powerpoint here.