Manuela Fischer: The Locality of Maximal Matching
07 March 2018 - 07 March 2018
Galleria 1 - 2nd floor, room G1-204
Many systems in the world are vast networks consisting of autonomous
nodes that communicate with each other in order to jointly solve a
task. One common feature of these complex networks is that due to
their size it is impossible for an individual node to have a global
view. Instead, nodes have to base their decisions on local information
about nearby nodes only. Despite this intrinsic locality, the network
as a whole is supposed to arrive at a global solution. Understanding
capabilities and limitations of such local algorithms is the key
challenge of distributed graph algorithms. The LOCAL model---the
standard synchronous message-passing model of distributed computing
introduced by Linial in 1987---is designed to abstract the pure
concept of locality.

In this talk, we discuss the maximal matching problem in the LOCAL
model. In particular, we introduce a new rounding technique that leads
to a deterministic O(log^2 Delta log n)-round algorithm on any n-node
graph with maximum degree Delta. This is the first improvement in
almost 20 years over the celebrated O(log^4 n)-round algorithm by
Hanckowiak, Karonski, and Panconesi.

The speaker

Manuela Fischer is a PhD student at ETH Zurich under the supervision of Mohsen Ghaffari. Her research interests include distributed graph algorithms, combinatorics, and stochastic processes.

Registration is highly recommended

 Pizza (or alternative food) and drinks will be offered
at the end of the talk. If you plan to attend, please register in a
timely fashion at the following link so that we will have no shortage of food.