• Calendar

November 15, Tuesday
12:00 – 14:00

Elkin, Emek, Spielman and Teng showed recently that every graph can be probabilistically embedded into a distribution over its spanning trees with polylogarithmic expected distortion, narrowing the gap left by Alon, Karp, Peleg and West that established a logarithmic lower bound in 1995. This lower bound holds even for the class of series-parallel graphs as Gupta, Newman, Rabinovich and Sinclair proved in 1999.

In this work we close this gap for series-parallel graphs, namely, we prove that every $n$-vertex series-parallel graph can be probabilistically embedded into a distribution over its spanning trees with expected stretch $O(\log{n})$ for every two vertices. We gain our upper bound by presenting a polynomial time probabilistic algorithm that constructs spanning trees with low expected stretch. This probabilistic algorithm can be derandomized to yield a deterministic polynomial time algorithm for constructing a spanning tree of a given series-parallel graph $G$, whose communication cost is at most $O(\log{n})$ times larger than that of $G$ .

Bio:
Yuval is a Ph.D. student at the Department of Computer Science and Applied Mathematics in the Weizmann Institute of Science. His fields of interest include combinatorial optimization, graph theory and coping with NP-hardness. He is conducting his research under the advice of Prof. David Peleg. Yuval has a B.A. in computer science from the Technion (summa cum laude) and an M.Sc. from the Weizmann Institute of Science. He is on the Feinberg Graduate School Dean's list of honor for 2005.