Michal Dory
Distributed Spanner Approximation

Abstract: I will show a strict separation between the classical
distributed LOCAL and CONGEST models for approximating k-spanners in
directed graphs. While in the LOCAL model, it is possible to obtain
(1+epsilon)-approximation to this problem in a polylogarithmic number
of rounds, obtaining any polylogarithmic approximation in the CONGEST
model requires nearly-linear number of rounds using deterministic
algorithms or nearly sqrt{n} rounds using randomized algorithms. Even
obtaining an approximation ratio of only n^c is hard in the CONGEST
model for any c smaller than 1. Joint work with Keren Censor-Hillel.