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.

Project Waterloo

I tried playing Microsoft Research’s Project Waterloo on Facebook; details are here, see also here. It’s a Colonel Blotto game: each player (there are 2) has 100 soldiers that he uses to attack 5 hills¹, and you capture any hill if you attack it with more troops than your opponent. In each round you divide your soldiers between the hills, doing your best to guess how the opponent is dividing his, and you win the round if you capture 3 or more hills. Quoting the MSRC site:

The game is complex from a game-theoretic perspective, involves randomized strategies, and can be approached by reasoning about the opponent's reasoning. We have also found it to be fun, engaging, and slightly addictive. It is thus a great test case for studying actual strategic behaviour of people on Facebook.

I’m wondering whether it’s meant to be straightforward to devise an optimal strategy... it’s a zero-sum game, the catch is, there’s a large number of pure strategies — but do you have to mix over a large number of pure strategies (to guarantee to break even over time)? Maybe there’s a set of 5 good numbers (e.g. 34,26,21,15,4) that work if you allocate them at random to the hills; those suggested numbers look like a good bet against opponents who split their troops about equally amongst 3,4 or 5 hills.

Next I start thinking up ideas for improvement, usually after losing a round... how about a multi-round variant, in which the surviving troops get to defend the hills they captured? In a subsequent round, a defender would cancel out (say) three attackers, and you are allowed to send additional troops to a hill you already captured, in which case, you have to cancel them out with opponent’s attackers, and if any survive, they add to the defenders of that hill. It looks like eventually, all hills will end up with so many defenders that further attacks should be futile, but there is no guarantee of how long it will take to reach that state.

¹“Hill” comes from the Gross and Wagner paper linked-to in the Wikipedia page. More abstractly they are sometimes called battlefields or sites.