I was last week in Dagstuhl for a workshop on exact algorithms for NP-hard problems, where I talked about listing maximal cliques. Some of the other exciting recent work in the area, from the other workshop talks, included Ryan Williams' connections between exponential time algorithms and circuit lower bounds from his paper at STOC 2010 (closely related to his new announcement that NEXP is not a subset of ACC0), and the work of Lokshtanov, Marx, and Saurabh showing that a large set of treewidth-based dynamic programming algorithms for graph optimization problems cannot be improved without simultaneous improvements to more general-purpose satisfiability solvers, to appear at SODA 2011.

While there, I added to Wikipedia an article on the exponential time hypothesis, an important tool in this area for showing close relations between the complexities of different problems, used in both Williams' and Lokshtanov et al's papers. I had the chance to interact with a few people I already knew, and a much larger number that I'd had some online contact with but not met in person before. And I also found time to take a few photographs of the local scenery. My gallery is now online, here.

The ruins of Schloss Dagstuhl, Germany