Helsinki Algorithms Seminar: "On the Role of Randomization in Local Distributed Graph Algorithms" Fabian Kuhn

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

Speaker:
Fabian Kuhn

Title:
On the Role of Randomization in Local Distributed Graph Algorithms

Abstract:
Many modern computing systems are distributed and built in a decentralized way on top of large networks. As one of the key challenges when running a distributed algorithm in a large network, typically no node can know the state of the whole network and thus each node has to base its decisions on only partial, mostly local information about the network. The major goal of the research on local distributed algorithms is to understand to what extent nodes in a network can achieve a global goal such as solving some graph problem, based on only local information.

In my talk, I will focus on the role of using randomization in local distributed graph algorithms. In many cases, there currently is a large gap between the best randomized and deterministic algorithms and understanding whether this gap is inherent, is considered to be one of the central open questions of the area. I will discuss recent results that shed some light on what randomness is really needed for and that allow to identify simple and basic problems that are complete for the class of problems that have efficient randomized distributed algorithms and for which we do not know efficient deterministic algorithms.

**

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.

For the season programme, please see the seminar webpage.