Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

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)
What and Who
Title:Lower bounds for maximal matchings and maximal independent sets
Speaker:Jukka Suomela
coming from:Aalto University
Speakers Bio: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.
Event Type:AG1 Mittagsseminar (others' work)
Visibility:D1, D3, D4, RG1, MMCI, D2, D5, SWS
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 14 February 2019
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.)

Contact
Name(s):Christoph Lenzen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:
Christoph Lenzen, 02/04/2019 05:25 PM
Last modified:
Uwe Brahm/MPII/DE, 02/14/2019 07:01 AM
  • Christoph Lenzen, 02/04/2019 05:25 PM -- Created document.