Speaker: Manuela Fisher, ETH Zurich Title: The Locality of Maximal Matching Abstract: 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. Bio: 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. When: 7th of March 2018, 12:00-13:00 Location: Manno, Galleria 1, 2nd floor, room G1-204 Registration: 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: https://doodle.com/poll/yuq8q4433p4df7bi