**Date: **
13:00,
Tuesday, February 16, 2016

**Speaker: **
Keren Censor-Hillel

**Venue: **TU Wien

**Notes: **

**Time: 13:00**

For many distributed computing problems there exists a characterizing

combinatorial structure. In other words, the existence of an algorithm

for solving the problem on any graph G in time T(G) implies the

existence of the structure in G with some parameter related to T(G),

and vice versa. Such relations go back to classic examples, such as

synchronizers and sparse spanners, and continue to emerge in recent

studies of gossip algorithms and multicast algorithms in different

communication settings. In this talk I will give an overview of both

old and recent results that illustrate these connections. I will show

how finding distributed algorithms as well as proving lower bounds can

be reduced to studying combinatorial graph structures.

No previous knowledge in distributed computing will be assumed.