Filed under: Uncategorized | Tags: algorithms, data structures, theory, workshops
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.
Congratulations to Dr. Maxwell Young who successfully defended his dissertation on Resource-Efficient Communication in the Presence of Adversaries at the University of Waterloo yesterday. Max got his Masters degree with me at UNM way back when I first started as a faculty member, and he was the very first student with whom I published a paper. He’s hard-working, talented, and also a lot of fun to work with. One of the great pleasures of academia is seeing student develop as researchers, and then have the possibility to continue to work with them as colleagues. Max and I have been actively working together for many years now, and I’m looking forward to visiting him in Singapore during his post doc with Seth Gilbert next year.
Some work of a recently graduated PhD student of mine, Amitabh Trehan, was mentioned in Muthu’s blog yesterday. The work is mentioned in a bullet about problems discussed at a Google research meeting at FCRC and is quoted below (btw was this meeting broadly advertised? I would have gone if I’d known about it):
- Big problems, eg., can we provide guidance on how science budget should be allocated among various disciplines, or NSF CS budget among different areas? Given a subset of researchers, say we can estimate their impact on the society when funded. Given this oracle, can we allocate funds to people to maximize social welfare? Can we model people switching teams in second round or open bid systems for reallocating funds? Q: Why doesn’t NSF give $’s to 2 teams for the same project and get them to compete? For some recent work, see the work of Shay Kutten, Ron Lavi and Amitabh Trehan.
It’s a proud and exciting moment to see a former student embark in a research area you know nothing about. But it’s also a bit disconcerting, like when my 3 year old son beats me at Concentration.