Vanity of Vanities, all is Vanity

New comment on your post #377 “What am I reading?”
Author : Sariel Har-Peled
Comment:

What do you mean – you dont read papers normally ?

Not as regularly and as much as I believe I should.

What do you mean – you dont read papers normally ?

Not as regularly and as much as I believe I should.

New comment on your post #377 “What am I reading?”
Author : anonymous
Comment:
What do you mean – you dont read papers normally ?

What do you mean – you dont read papers normally ?

I am trying to get back to the habit of reading papers. Disgusting, I know. Anyway, here is a beautiful paper I read recently (together with a group of students).

Improved Embedding of Graph Metrics into Random Trees. Anupam Gupta, Kedar Dhamdhere and Harald Räcke.

This paper has little new ideas over the breakthrough result:

Lower-Stretch Spanning Trees by Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng.

But the Gupta etal paper (partially maybe with the benefit of hindsight) is much cleaner and more elegant (and even slightly improves the result).

The Gupta etal paper shows that any finite graph of n vertices can be embedded into a probabilistic tree with expected distortion X=O(log^2 n) on the distances. Namely, given a graph the algorithm generates a spanning tree, so that for any pair **u,v in V(G)** the distance along the tree between u and v in expectation is X times bigger than the true distance in G.

This direction of research started long long time ago in a land far far away, where Alon, Karp, Peleg and West (A Graph-Theoretic Game and its Application to the $k$-Server Problem in SICOMP Vol 24 (1): 78-100, 1995) showed how such an embedding can help with the k sever problem. Furthermore, they showed such a probabilistic embedding with distortion of \exp(O(\sqrt{\log n \log\log n})) (somewhere in the no-man land between sub-polynomial and polyloarithmic). They also show a lower bound of Omega(log n) even for the grid in two dimensions (!).

Then Yair Bartal showed up on the scene (FOCS 96, STOC 98). In a sequence of papers, he showed that if one embeds into a probabilistic trees that are not necessarily part of the graph (i.e., the graph nodes are now the leaves of the tree) then one can achieve a O( log n * log log n) distortion. Slightly short of the promised land of O( log n ) distortion. The search was on for trying to remove the pesky log log factor.

Underlining all these results is a way of breaking (the finite metric) space into clusters. Intuitively, we would like to guarantee that if we break space into clusters of radius r, the probability of an edge of length l to be cut by the clustering is O(l/r) (i.e., short edges are “relatively” safe when we care about large distances). This of course easily holds when we speak about the plane, and we do the partition by randomly shifting a grid of sidelength, say, r/2 (this is one of the key observations used in Arora’s Euclidean TSP paper). Unfortunately, this is too good to be true to hold in general. It turns out that to improve the Bartal result, what was needed was a partition scheme with probability guarantee that depended on the local density of the metric. This was achieved by Fakcharoenphol, Rao and Talwar in a nice paper (STOC 03: 448-455). This lead to finally improving Bartal result achieving the promised O(log n) distortion. (I have some class notes on this topic!
, see here.)

The surprising thing about Elkin etal. result is that they showed that a polylogarithmic bound was possible even when the tree is a spanning tree of the original graph. Gupta etal further improved things by coming up with a cleverer partitioning schemes (essentially taking the Elkin etal scheme and carefully tuning the distributions used for the cut-radiuses of the partitions).

>From low dimensional computational geometry the results are not too interesting. Such an embedding can be achieved by just using randomly shifted quadtrees (and that might have been Bartal intuition behind his work).

For me research in finite metric spaces is a spectator sport. But the players are smart, the math is beautiful, and in a good day of reading you can have a lot of fun…

New comment on your post #359 “Happiness and university life?”
Author : WTF
Comment:
Is there anything to do with China? You uncivilized king kong..

Is there anything to do with China? You uncivilized king kong..

New comment on your post #376 “Discrete integration?”
Author :
Comment:
Something is weird.

I keep typing an inequality. But perhaps I just mean a (1+- epsilon) approximation to K.

Something is weird.

I keep typing an inequality. But perhaps I just mean a (1+- epsilon) approximation to K.

New comment on your post #376 “Discrete integration?”
Author :
Comment:
Hmm. Some how the tail of my post was cut off. I meant the inequality:

1-epsilon