max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Lower bounds for maximal matchings and maximal independent sets Jukka Suomela Aalto University Jukka Suomela (https://users.ics.aalto.fi/suomela/) is an Assistant Professor in the Department of Computer Science at Aalto University. His work focuses on the theoretical foundations of distributed computing, with particular emphasis on the concept of locality. He is a member of the EATCS council, he was recently a local co-chair of ALGO 2018, and he is the PC chair of DISC 2019. AG1 Mittagsseminar (others' work) D1, D3, D4, RG1, MMCI, D2, D5, SWSWe use this to send out email in the morning. AG Audience English
Date: Thursday, 14 February 2019 13:00 30 Minutes Saarbrücken E1 4 024
 How fast can one find a maximal matching or a maximal independent set in a distributed system? Here each node of the input graph is a computer, and each node needs to output its own part of the solution. How many communication rounds are needed in a graph with n nodes and maximum degree Δ? These are classical questions with a long history of upper and lower bounds, the first of which date back to the 1980s. For example, for maximal matchings the current upper bounds are: (1) O(Δ + log* n), by Panconesi & Rizzi (2001) (2) O(log Δ + log^3 log n), by Fischer (2017) and Barenboim et al. (2012, 2016). The running time of algorithm (1) is optimal as a function of n; there is a matching lower bound by Linial (1987, 1992). The running time of algorithm (2) is near-optimal as a function of Δ; there is an almost-matching lower bound by Kuhn et al. (2004, 2016). However, it has been a long-standing open question whether we can achieve the best of both worlds, and find maximal matchings and maximal independents sets e.g. in time O(log Δ + log* n). We show that the answer is no. There is no distributed algorithm that finds a maximal matching or maximal independent set in time o(Δ + log log n/log log log n). Algorithm (1) is optimal for Δ << n, and algorithm (2) is near-optimal for larger values of Δ. (This is joint work with Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, and Mikaël Rabie. Please see https://arxiv.org/abs/1901.02441 for more details.)
Name(s): Christoph Lenzen