Machinations

Bertinoro is a small town near Bologna, with a castle on a hill, a monastery just below it and a beautiful view of farmland and the Mediterranean.  It’s now a popular site for workshops (kind of like Dagstuhl), which are held in the castle.

This summer was the second time that I attended the Algorithms and Data Structures (ADS) workshop at Bertinoro.  There were many interesting clusters of talks.  I’m just going to touch on a very biased sample of some of the talks I remember below:

• Andrew Goldberg talked about new algorithms for solving the single-source shortest path problem on graphs with low “highway” dimension.  Intuitively a graph has small highway dimension if for every positive r, there is a “sparse” set of vertices S_r such that every shortest path of length r passes through S_r, where sparse means that every ball of radius O(r) contains a small number of elements in S_r.  Renator Werneck and Daniel Delling talked about additional aspects of the SSSP problem, namely 1) handling arbitrary metrics quickly in order to handle, e.g.  real-time traffic updates (Weneck); and 2) showing a connection between highway dimension and VC-dimension, and showing that a labeling algorithm coming out of the distributed computing community improves theoretical and practical performance (Delling).  This research on fast single source shortest paths algorithms has been going on for years at MSR – it’s nice to see a practical problem so thoroughly investigated.
• For research in data structures, you can’t do much better than Sleator and Tarjan.  Bob Tarjan talked about a way to maintain search trees so that rebalancing occurs only on insertion, not deletion (thereby significantly simplifying the rebalancing process).  Daneil Sleator talked about, Skip-Splay, a BST data structure that nearly achieves the unified bound (intuitively a data structure that satisfies the unified bound has good performance for sequences of operations where most accesses are near a recently accessed element).  On a more practical note, Michael Bender talked about work done at his company on designing a data structure for membership queries that is optimized for 1) space, and 2) writes.  Like a Bloom Filter, the data structure trades off space for a false positive rate.  However, the new data structure scales beyond main memory, and is optimized for writes and for flash memory.  The talk was titled: “Don’t Thrash: How to Cache Your Hash on Flash”
• Distributed computing was represented by Faith Ellen, Sid Sen, Valerie King and me.  Faith talked about a communication model conjecture with applications to proving superpolylogarithmic lowerbounds for dynamic data structures. Sid talked about the cost of equivocation in Byzantine agreement – namely what happens if we have partial broadcast channels among sets of 3 processors.  Valerie talked about our work “Conflict on a Communication Channel” that I’ve blogged about here previously.  I talked about our recent work on scalable rational secret sharing (slides are here).

All in all this was a great workshop.  Lot’s of smart people, beautiful scenery, and 4-hour Italian-style dinners (3 courses of alcohol!) in which to think about the big problems in algorithms and data structures.