In the past few decades, pseudorandom objects, notably expander graphs, have been key ingredients of several results in various subareas of theoretical computer science. To name a few: Undirected Connectivity being in deterministic LOGSPACE, the existence of $O(\log n)$-depth sorting networks, and randomness-efficient error reduction.

In this talk, we will see a few important techniques from the area of pseudorandomness together with some applications in distributed computing. Our main application will be the compression of bandwidth-hungry primitives in models with congestion. Existential proofs often precede explicit constructions in the area of pseudorandomness, and we will discuss what it means for known algorithmic results using pseudorandom objects.

Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In the case of dynamic networks, this technique aims to explain the gaps between real-world networks that function well despite being dynamic and the strong theoretical lower bounds for arbitrary networks. In this talk, I will present our recent applications of smoothed analysis to dynamic networks. Our work studies different models of adversarial behavior and concerns problems such as information propagation and load balancing.

Based on joint works with Seth Gilbert, Uri Meir, and Gregory Schwartzman

Graph colouring is one of the most fundamental graph questions, and has received attention in pracically every computational model. In this talk, we will revisit graph colouring in the dynamic setting, where the graph is subject to arbitrary, adversarial insertions and deletions of edges. We will see how an interplay between dynamic and distributed algorithms can be used to give improved algorithmic solutions to the problem: distributed algorithms with dynamic advice was used in [STOC'23] to obtain new colouring algorithms for dynamic graphs. The notion of distributed algorithms with (dynamic) advice may be of independent interest, and the talk will mention open problems and open research directions.

Based on joint work with: Aleksander B. G. Christiansen, Jacob Holm, Ivor van der Hoog, Krzysztof Nowicki, Chris Schwiegelshohn, and Carsten Thomassen.

Many distributed coordination problems requiring perfect agreement, such as consensus, are typically hard to solve in a fault-tolerant manner. However, agreeing on values that are close to one another can be considerably easier. A classic example is the problem of approximate agreement over real values, which can be solved deterministically in many asynchronous models of computing — even if some processes arbitrarily fail. In this talk, I discuss generalisations of approximate agreement to arbitrary undirected graphs. It turns out that the structure of the graph significantly influences both solvability and complexity of such problems. The talk will overview some recent results and open problems in the area.

Symmetry breaking problems, such as vertex coloring and maximal independent set (MIS), have recently received a lot of attention in the study of (massively) parallel graph algorithms. By now, a standard technique to approach these problems is to sparsify the input graph and to efficiently simulate a distributed message passing algorithm in the sparse graph. Especially for MIS, the progress is stuck in the sparsification step, and the current techniques seem insufficient to push forward. We discuss algorithms for graphs that are already sparse where the sparsification step becomes irrelevant and nevertheless, the problem remains hard. In this setting, we require new methods to obtain efficient algorithms. In this talk, we discuss new techniques that do not rely on graph sparsification and the recent developments on massively parallel algorithms for symmetry breaking problems.