עופר נימן

We prove that any graph G with n points has a distribution T over spanning trees such that for any edge (u, v) the expected stretch E_T-T[d _T(u, v)/d_G(u, v)] is bounded by Õ(log n). Our result is obtained via a new approach of building "highways" between portals and a new strong diameter probabilistic decomposition theorem.