Post-Lunch Highlights, Day 1

More from Rahul at FOCS

I realize I could quite easily spend more time writing about the talks then going to them, so I'll keep it shorter

• Gil Kalai gave a vastly entertaining talk on "Elections can be Manipulated Often" (Kalai and Friedgut and Nisan). Clearly a topic of current relevance, but Gil bravely resisted making an Obama-McCain reference. The main result of the paper essentially says that the cumulative manipulation power (meaning their capacity to bring about their preferred global outcome by voting in a way that's different from their actual ranking of the candidates) in any "reasonable" election (where the voting scheme is far from yielding a dictatorship, and is insensitive to the names of the candidates) is invariably high, in a setting where voter preferences are modelled by random choices. The main open question from the talk was to prove that the current financial crisis was unavoidable.
• Mihai Patrascu gave a talk on his paper "Succincter", which won the Machtey best student paper award. His paper greatly advances the state of the art in the field of succinct data structures. For instance, the paper shows how to store N "trits" (numbers that are either 0,1 or 2) in N log(3) + O(1) bits of memory with only logarithmic query time. The proof uses a clever recursive encoding scheme.
• Dana Moshkovitz spoke about her Best Paper-winning work with Ran Raz on constructing sub-constant error 2-query PCPs of nearly linear size. This has been a major open problem for quite a while now, and the resolution of this open problem yields improvements to a large family of hardness of approximation results. The proof builds on earlier work by Moshkovitz and Raz constructing sub-constant error low degree tests of nearly linear size.

There's been precious little controversy at this conference, so I feel duty-bound to stir something up. There's an asymmetry between the two seminar rooms – one is considerably larger, wider and has better acoustics than the other. Is it a coincidence that the more complexity-oriented talks in Session B are in the smaller room, and the algorithms-oriented Session A talks in the larger not? I think not. This is merely the latest instance in the step-sisterly treatment accorded to complexity theory down the ages, right from when Euclid designed his algorithm but failed to analyze its complexity. I urge all right-minded readers to express their outrage at this state of affairs.

More seriously, can't think of a hitch; even lunch yesterday was good. Kudos to Sanjeev Khanna, Sudipto Guha, Sampath Kannan and the student volunteers.