# Machinations

PODC DAY 2
June 9, 2011, 12:02 am
Filed under: Uncategorized | Tags: , ,

Several interesting talks today including the following

“Compact Policy Routing” by Revtvari et al. considered the problems of designing small routing tables for routing when the optimization criteria is not necessarily path length. In particular, they note that Internet routing doesn’t use shortest paths, but instead is policy routing: making use of economic and political concerns. Their paper defines routing algebras and explores compressibility of routing tables for different types of optimization functions. A main result of the paper shows that BGP policy routing essentially must give rise to very large routing tables.

“Locally Checkable Proofs” by Goos and Suomela classifies various graph problems according to their local proof complexity. For example, locally checking whether a graph is bipartite requires each node to hold a proof of just 1 bit (the node’s color in a 2-coloring of a graph). In contrast, locally showing that a graph is *not* bipartite requires each node to hold a proof of size Theta(log n) (shown in the paper). The paper categorizes a dozen or so graph problems in terms of locally checkable proof sizes. Possibly interesting connections exist between this paper and the “Toward More Localized Local Algorithms” by Korman, Sereni and Viennot on Day 1. The proofs from this paper could possibly be plugged in as the “pruning algorithms” required by Korman et al.

“Fault-tolerant spanners” by Dinitz and Krauthgamer ” builds spanners that are robust to deletion of r nodes. Specifically, any algorithm that can create a k spanner (k>= 3) with f(n) edges can be converted to a k spanner with O(r^3 log n)*f(2n/r) edges that is “robust” to deletion of r nodes. “Robust” here means that for any set of F nodes, |F| <= r, the original spanner with F deleted is still a k-spanner of the original graph with F deleted. The algorithm is technically quite interesting, making use of a clever LP relaxation and the Lovasz Local Lemma.

“The Round Complexity of Distributed Sorting” by Patt-Shamir and Teplitsky considers a fully connected network where in each round, each node can send a O(log n) bit message to every other node (This is the CONGEST model with diameter 1). They first show that sorting in this model, when each node has at most n items can be done in O(log log n) rounds and selection can be done in O(1) rounds. Then, using a concurrent result by Lenzen and Wattenhofer on routing in the same model (in STOC), they further reduce sorting to O(1) rounds. The interaction between this paper and the result by Lenzen and Wattenhofer is neat, an the model itself is interesting (sort of diametrically opposed to LOCAL), and seems very powerful.

A quick final mention of two papers presented today that I was a co-author on. Varsha Dani gave a nice talk on our “Scalable Rational Secret Sharing” paper, and Maxwell Young gave a nice talk on our “Conflict on a Communication Channel paper.