TCS+ talk: Wednesday, May 24 — Mohsen Ghaffari, ETH Zurich

by plustcs

The next TCS+ talk will take place next Wednesday, May 24th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Mohsen Ghaffari (ETH Zurich) will will speak about “On the Complexity of Local Distributed Graph Problems” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

We revisit the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS ’87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and $(\Delta+1)$-vertex coloring), the randomized complexity is at most polylogarithmic in the size $n$ of the network, while the best known deterministic complexity is typically $2^{O(\sqrt{\log n})}$. Understanding and potentially narrowing down this exponential gap is one of the central long-standing open questions in the area of distributed graph algorithms.

We investigate this question by introducing a complexity-theoretic framework, which allows us to shed some light on the role of randomness in the LOCAL model. In particular, we prove completeness results which, roughly speaking, show that some rather rudimentary-looking problems are “complete” for essentially all the classic local distributed problems. In other words, if any of these complete problems can be solved deterministically in $\poly\log n$ rounds in the LOCAL model, we can deterministically solve essentially all the classic LOCAL-problems (including MIS and $(\Delta+1)$-coloring) in $\poly\log n$ rounds.

Perhaps the most surprising complete problem is the following: Color the nodes of the graph red or blue such that each node of a sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized algorithm, simply color each node randomly. This completeness result can be viewed as showing that the only obstacle to getting efficient deterministic algorithms in the LOCAL model is an efficient algorithm to round fractional values into integer values, while approximately preserving some linear constraints.

This talk is based on a joint work with Fabian Kuhn and Yannic Maus.

A version of the paper can be found here: