SWAT 2010 (part 2)
The SWAT conference dinner involved a boat trip to an island near Bergen, with a spectacular seafood dinner of Halibut and Wolffish. Also, initiated by Fedor Fomin, SWAT reverted back to its tradition of pressuring attendants to sing (partitioned into small groups by nationality or country of residence) after the main course. Again, the organisers managed to get the atmosphere exactly right.
- On Monday, Sanjeev Arora talked about semidefinite programming and approximation algorithms. A lot has happened in this field since what he called “first generation” SDP algorithms. Some of the most recent works concerns re-evaluatating the role played by the Unique Games Conjecture.
- On Tuesday, Prabhakar Raghavan, now at Yahoo! Research, talked about quantitative models for user behaviour. He spent some time on models for presenting search results (in particular, images) in two dimensions – which is much less obvious than the top-to-bottom ordering that web pages are presented in. (Left-to-right, row-by-row, is not the right answer for laying out pictures in a grid, because the eye doesn’t move like that.) He used this example to also communicate broader points about the interplay between quantitative sociology, cognitive psychology, and theoretical computer science. Great stuff, and highly interesting to me both because of the “algorithmic lens” propaganda, and because I sometimes give general audience talks about the computer science behind search engines, social networks, etc.
- On Wednesday, Dana Randall talked about phase transitions in sampling algorithms and underlying random structures. This was right in the middle of the interplay between statistical physics and theoretical computer science that I am currently fascinated by. The talk was an algorithms-friendly introduction filled with rapidly mixing Markov chains, crisp combinatorics, Ising and Potts models, and colloids (which I hadn’t seen before.)