When: Friday Oct 5, 2:00PM
Where: LOM 215.
Computer Scientists often find it useful to approximate arbitrary graphs by trees. Classic approximations include Maximum Spanning trees and Shortest Path trees. However, for many purposes the right measure of the quality of an approximation is the stretch of a spanning tree. This is essentially the average over edges not in the tree of the distance in the tree between their endpoints.
Many recently developed algorithms depend upon constructions of spanning trees of low stretch, and could be improved by better constructions. Many practitioners are anxiously awaiting practical constructions. I will describe constructions of stretch $O(log^2 n log log n)$ that I developed with Elkin, Emek and Teng. I will say a little about improvements upon our constructions by Abraham, Bartal and Neiman, and make wild conjectures about what I believe should be possible. I will also present a spectral characterization of stretch.
For more information: