Blogging from Bertinoro

I'm here at Bertinoro (a beautiful, out-of-the-way, small town in Italy) for the 2010 version of Random GRAALS (= graphs and algorithms), a workshop that we've been having every few years, usually with around 30 or so people, which provides an opportunity to hear some nice talks, and gives a bunch of us an excuse to go to Bertinoro.  Sadly, I'll have to leave a bit early, so I can have some "home days" before STOC/EC/ISIT.  Busy start of summer.

Leslie Goldberg and Mark Jerrum started off with a joint talk on the complexity of certain graph counting problems, focusing on the connections between the hardness of approximate counting of independent sets on bipartite graphs and the hardness of computing the Tutte polynomial at various points.  They (along with others) have been looking at variations on this theme for quite some time;  there was a very nice bit about developing gadgets for randomized reductions by making using of random graphs with "bistable" characteristics, specifically 2nd order phase transitions, that seemed like fun.  Aris Anagnostopoulos talked about Approximation Algorithms for Dynamic Data -- for example, suppose you're trying to keep a set of item counts sorted, but the counts are changing over time, so as you do comparisons to sort, the underlying ground truth can be changing.  The data changes slowly enough that it doesn't change arbitrarily over time steps, but instead in a limited fashion;  however, it changes fast enough -- or comparisons are expensive enough -- you can't just resort everything each time step.  Uriel Feige talked about hat puzzles on graphs, with a nice collection of open problems on this generalization of the standard hat puzzle.  I talked about random stuff I've been doing, including the improved analysis of the lossy difference aggregator, and the Carousel paper on network logging that appeared at NSDI.  I then forced the audience to sit through a brief version of our talk on Swoopo -- which will be presented at EC next week.  Berthold Vocking talked about combinatorial auctions for secondary spectrum auctions, looking at models of conflict graphs and independent sets.

I enjoyed all the talks, but I have to say, as always I'm impressed with Uri's talk -- he somehow makes everything seem approachable and fun.  

Now we're going out for what, I assume, will be a wonderful Italian dinner.