notes from FOCS

There’s a table with free copies of the proceedings of FOCS 2010 and FOCS 2001, but there are not so many takers, seemingly. FOCS 2010 is a muddy green colour, and are the last paper proceedings — the proceedings of FOCS this year come on USB sticks, not paper, saving me the weight on the return trip, and also cutting down the cost of producing the proceedings to about $1,000, as mentioned during the business meeting. I believe that it’s the privilege of the local organizers to choose the colour of the proceedings, but I don’t know if the lime-green colour of the USB follows that tradition.

The conference had 236 registrations of which 82 were students. The number is similar to recent years. 85 papers were accepted out of 283 submissions. The Machtey award was awarded jointly, likewise the best paper award. (Really, we should maintain some central web page with a list of who won them; for the former there’s the wikipedia page, but at the time of writing it has not been updated for 2011. For the latter, when I googled for “FOCS best paper 2011” I got pointed to this blog post of Claire Mathieu of 1st April 2011, which featured prominently in Rafi Ostrovsky’s overview talk at the business meeting, but does not identify the relevant papers.) The business meeting featured an extensive discussion of how the conference should adapt to better serve the community: the format hasn’t changed much over the years, meanwhile things like arxiv have taken over some of the functions of conferences. The desired state of affairs is that lots of people would attend even if they don’t have papers there. Maybe next time we should have poster sessions, open problem sessions, that sort of thing. (Maybe the proceedings will be supplied in a shared Dropbox folder, USB sticks are getting a bit passé...)

I attended the tutorial talks on Saturday: I liked Kirk Pruhs on “Green Computing Algorithmics”: you want to save energy expended during computation; unfortunately there’s unlikely to be a very distinctive theory in which energy joins time and space as a resource you try to minimize; since computation can be made reversible there is no thermodynamic reason to lower-bound energy requirements; a “big-O” theory of energy would treat it like computation time. On the other hand, there’s still a “mother lode” of algorithmic problems relating to architecture-dependent scenarios.