Nearly Tight Low Stretch Spanning Trees

We prove that any graph G on n vertices has a distribution over its 
spanning trees such that for any edge (u,v) the expected stretch 
E_T[d_T(u,v)] is bounded by \tilde{O}(\log n). Our result is obtained 
via a new approach of building ``highways'' between portals and a new 
strong diameter probabilistic decomposition theorem.

Joint work with Ittai Abraham and Yair Bartal.