Graph spanners (subgraphs which approximately preserve distances) originated in the distributed computing community and have had a huge impact in distributed algorithms and in algorithms more broadly. In this talk we will discuss recent progress on two relatively new variants of graph spanners: $\ell_p$-norm and fault-tolerant spanners. For $\ell_p$-norm spanners this includes tight existential bounds and good approximation algorithms (at least for some parameter settings), and for fault-tolerant spanners this includes tight existential bounds with surprisingly efficient algorithms.

Both of these variants are particularly well-motivated in distributed settings. Yet for both of them the recent progress in the centralized setting is based on some variant of the greedy algorithm, which is not easily implementable in distributed settings. We hope that this talk will help spur research on distributed algorithms for these important objects.

Broadcast is a fundamental network communication primitive, in which a source node has a message that has to be received by all other nodes. In synchronous radio networks, this problem is non-trivial, since if two or more neighbours of a node transmit at the same time, it hears nothing. In fact, if nodes do not store any information, broadcast is impossible deterministically, even in a four-cycle. If the nodes have distinct identifiers from a small name space, then a round-robin strategy suffices, but it takes a long time.

This talk will show that every radio network can be labelled using a small constant number of bits so that broadcast can be accomplished by a fixed deterministic algorithm that does not know the network topology nor any bound on its size. Specifically, there is a labelling scheme that stores 2 (carefully chosen) bits per nodes that allows broadcast to be performed in $O(n)$ rounds, where $n$ is the size of the network. There is a variant of this algorithm using 4 bits per node that completes broadcast in $O(\sqrt{Dn})$ rounds, where $D$ is the source eccentricity of the network. This number of rounds is shown to be optimal for a class of algorithms that includes both.

Then, using some ideas from some old algorithms, which assume nodes have distinct identifiers and a bound on the network size, a deterministic algorithm is constructed that uses 3 bits per node and completes in $O(D \log^2 n)$ rounds. A randomized construction of a labelling scheme with 3 bits per node for a broadcast algorithm that completes in $O(D \log n + \log^2 n)$ rounds is also presented.

This is joint work with Seth Gilbert and Barun Gorain, Avery Miller, and Andrzej Pelc.

The last years have seen several new distributed graph coloring algorithms in the LOCAL and the CONGEST model. In this talk we will survey modern techniques and relate (some of) them to classic ones. In particular, we see how Linial’s seminal $O(\Delta^2)$-coloring algorithm for graphs with maximum degree $\Delta$ extends to list coloring and how this implies one of the current state of the art distributed graph coloring algorithms.

Local computation algorithms (LCA) formalize concepts that arise in various algorithmic fields. The main task of LCA is to solve a problem on a part of an instance by accessing only "a small" part of it, e.g., deciding whether a given edge is in a maximal matching without looking at the entire graph. In this talk, in the context of matchings, we will discuss two recent LCA techniques. These techniques start with a generic transformation of a LOCAL algorithm to an LCA, and then provide a way to reduce the amount of an input needed to be inspected by the generic approach. One of these techniques has implications for MIS, set cover and coloring as well.

The problem of coloring the edges of an $n$-node graph of maximum degree $\Delta$ with $2\Delta-1$ colors is one of the key symmetry breaking problems in the area of distributed graph algorithms. While there has been a lot of progress towards the understanding of this problem, the dependency of the running time on $\Delta$ has been a long-standing open question. Very recently, Kuhn [SODA ’20] showed that the problem can be solved in time $2^{O(\sqrt{\log \Delta})}+O(\log^* n)$.

In this talk, we discuss the edge coloring problem in the distributed LOCAL model. We show that the (degree+1)-list edge coloring problem, and thus also the $(2\Delta-1)$-edge coloring problem, can be solved deterministically in time $2^{O(\log^2 \log \Delta)} + O(\log^* n)$.

One of the most interesting settings for massively parallel algorithms on graphs is when the local space of each machine is sublinear in the number of vertices. This allows for distributing computation, even for sparse graphs, across a large number of machines that do not have to be very powerful. In recent years, we have seen several developments in this area, including both algorithms and conditional lower bounds. In many cases these results leverage connections to other areas such as distributed algorithms and property testing. I will survey some of them and talk in more detail about generating random walks and estimating PageRank, for which we were able to obtain nearly-exponential improvements in round complexity over direct implementations of known algorithms. Finally, I will share some of my favorite open questions in the area.