In the recent four years, there has been a fast progress in showing impossibility results for several fundamental problems in the LOCAL model of distributed computing. Our advances in understanding the automatic round elimination technique have played a big role in these achievements.

In this talk I will give an overview of the current state of the art of the automatic round elimination technique. We will see what are the tricks and methods that have worked so far, and what are some of the important open questions that we would like to comprehend. We will see that the study of the $\Delta$-vertex coloring problem under the round elimination framework had a direct effect in our understanding of several symmetry breaking problems.

In this talk I will outline a recently discovered connection between distributed computing and an apparently very different subject, namely descriptive combinatorics. Descriptive combinatorics studies classical combinatorial problems—such as coloring, matching, etc.—on infinite structures (for example, infinite graphs) under additional topological or measure-theoretic regularity constraints. It turns out that distributed algorithms can provide powerful tools for working with such infinite structures; moreover, it is sometimes possible to establish exact translations of distributed results in the descriptive setting and vice versa. For example, efficient deterministic algorithms for locally checkable problems in the LOCAL model precisely correspond to continuous colorings. I will discuss this and several other instances of the interplay between distributed algorithms and descriptive combinatorics and mention a number of open problems.

In recent years, the fields of distributed and parallel graph algorithms, while always linked, have grown increasingly close. In particular, the emergent Massively Parallel Computation (MPC) model has been shown to have a strong connection to the classic LOCAL model of distributed computing. Under some restrictions, LOCAL algorithms can be run at an exponential speedup in MPC, via a process known as graph exponentiation. Furthermore, recent work has suggested that for many problems, this might be the best that one can hope to do in low-space MPC.

This talk will begin with an overview of what is known about this connection, both from an upper- and lower-bounds perspective. We will then discuss some recent results (joint work with Artur Czumaj and Merav Parter) showing that the power of low-space MPC is not limited to graph exponentiation, and demonstrate examples of algorithms which are super-exponentially faster than their LOCAL counterparts.

Many distributed graph algorithms have been designed for specific graph classes, such as regular or planar graphs. In some cases, e.g. regular graphs, the nodes of the network can check locally that the network indeed has the right structure, before running the algorithm. Unfortunately, in some cases, e.g. planar graphs, it is not possible to locally check the structure, and this can be problematic.

In this talk, I will review the recent results on the local certification of graph classes, which consists in certifying that the network belongs to a given class, using short labels on the nodes and a local verification algorithm.

[The talk will have a non-empty but small intersection with the gem talk I gave at PODC.]

In the Congested Clique model, there are n players that perform computation in synchronous rounds. Each round consists of a phase of local computation and a phase of communication, in which each pair of players is allowed to exchange $O(\log n)$ bit messages. The main complexity measure is the number of rounds needed by the algorithm. The Congested Clique model may be considered as a special case of the Congest model in which the communication network is a clique, or as a special case of the Massively Parallel Computation model.

In this talk I will present a deterministic algorithm computing a maximal (in the sense of inclusion) spanning forest of a graph in a constant number of rounds, and briefly discuss its applications to the Minimum Spanning Tree problem, and the Edge Connectivity problem.

Many distributed algorithms for optimization problems like the shortest path or the minimum spanning tree achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two long-standing fundamental questions in distributed computing:

(i) What network topology parameters determine the complexity of distributed optimization?

(ii) Are there universally-optimal algorithms that are as fast as possible on every topology?

A recent line of work on the so-called low-congestion shortcut framework answered both of these questions: (i) the network topology parameter is (up to polylogs) the low-congestion shortcut quality, and (ii) there indeed exist universally-optimal algorithms. In this talk, I will give an overview of the various pieces of the framework, explain how they interact to culminate in universally-optimal algorithms, as well as several other results of independent interest.