Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, March 07, 2019, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Sebastian Brandt

A General Distributed Speedup Technique and Its Applications

At the heart of a recent lower bound for the distributed Lovász Local Lemma lies a speedup technique that transforms any distributed algorithm for one specific LLL problem into a one-round-faster algorithm for the same problem. In this talk, I will show that such a speedup exists for any locally checkable problem, with the difference that the problem the sped-up algorithm solves is not (necessarily) the same as the initial problem. This opens new and exciting possibilities for obtaining bounds for the complexity of locally checkable problems. We will see that our speedup technique has concrete applications: in particular, we will use it to obtain new deterministic and randomized lower bounds for Maximal Matching and Maximal Independent Set in the LOCAL model of distributed computing, improving on and complementing the two famous lower bounds by Linial [FOCS'87] and Kuhn, Moscibroda and Wattenhofer [PODC'04].

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login