Helsinki Algorithms Seminar: "New Classes of Distributed Time Complexity" Janne H. Korhonen, Aalto

2017-11-30 16:15:00 2017-11-30 17:00:00 Europe/Helsinki Helsinki Algorithms Seminar: "New Classes of Distributed Time Complexity" Janne H. Korhonen, Aalto Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design http://cs.aalto.fi/en/midcom-permalink-1e7c2f8b03ea1fcc2f811e7bfa8b3043088f405f405 Otakaari 2, 02150, Helsinki

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design

30.11.2017 / 16:15 - 17:00
Exactum B222, Otakaari 2, 02150, Helsinki, FI

Janne H. Korhonen
Aalto University

New Classes of Distributed Time Complexity

Abstract:

Understanding the complexity landscape of LCL problems in the LOCAL model is one of the most fundamental research questions in the theory of distributed computing. Recent progress on the topic has given reasons to conjecture that the overall time hierarchy would be relatively simple, as is now known to be the case on restricted graph families such as cycles and grids. In this work, we give a surprising answer to many of the related open questions: we show that the picture is actually much more diverse than previously expected, by presenting a general technique for engineering LCL problems with numerous different deterministic time complexities. (https://arxiv.org/abs/1711.01871)

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

Welcome!