אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

A k-spanner is a sparse subgraph that preserves distances up to a multiplicative factor of k. First introduced in the late 80's, spanners have been central for numerous applications, such as synchronization, compact routing tables, approximate shortest paths, and more.

This talk focuses on distributed construction of approximate minimum spanners, presenting both algorithmic and hardness results, in the classical LOCAL and CONGEST models of distributed computing. In both models vertices exchange messages in synchronous rounds, where in the LOCAL model the size of messages is not bounded, and in the CONGEST model they are bounded by O(log(n)) bits.

I will show a strict separation between the 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 the same 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 0<c<1.

Joint work with Keren Censor-Hillelץ