I will survey the topic of distributed subgraph finding, give a glimpse into some of the most recent results in this area, and highlight many open problems.

This talk surveys recent advances in Deterministic Distributed Symmetry-Breaking algorithms.

In this talk, I will present recent breakthrough results concerning quantum LOCAL and how these contribute to a sharper picture of the complexity landscape of extensions of the LOCAL model. In particular, we now have a full-fledged separation for locally checkable labeling (LCL) problems between quantum and classical randomized LOCAL, and the technique may have applications in other contexts of LCLs. That being said, yet another negative result for quantum advantage has cropped up, this time for fractional problems (with consequences for LCLs). I will present these two results and discuss what other developments to expect in the future.

In this talk, we will look at the notion of awake efficiency of distributed algorithms in a synchronous networked setting. In each round a computer can either be awake, as usual, or asleep, and be unable to send/receive messages or perform computations. The awake complexity of an algorithm is the maximum number of rounds any computer is awake throughout the algorithm. Why should one care about this complexity measure? When computers are asleep, the amount of energy they require is negligible compared to when they are awake. So if you want to know how much energy is being utilized by an algorithm the product of the awake complexity and number of nodes is a much better estimate compared to say the product of run time and number of nodes. A similar measure is already used in radio networks and is called the energy complexity of the algorithm. An additional motivation is that if one wants to schedule two or more algorithms across the same set of computers, one can easily avoid congestion and issues with computation if the algorithms are scheduled such that the awake rounds for each computer in one algorithm only overlap with the asleep rounds of the other algorithms.

The design of awake efficient algorithms for a given problem typically requires a mixture of both existing techniques to solve that problem coupled with schedules that dictate when computers are awake or asleep. The fun part of this is that developing these schedules requires one to be able to predict when computers will be awake in the network and this is heavily dependent on the techniques utilized. The ability to predict the flow of information, or in some cases actively control it, possibly at the expense of run time makes for interesting design decisions. This talk shows how to develop such schedules and more generally design awake efficient algorithms for some problems.

This presentation explores a range of models designed to capture how distributed systems can efficiently and reliably disseminate information. The focus is on systems composed of simple agents with severely limited computational resources, such as memory and communication, and operating in noisy or unpredictable environments. To better understand the fundamental capabilities and limitations of such systems, I will present a selection of elegant, minimalist strategies that enable effective information spread, alongside a few impossibility results.

Almost by definition, graphs are combinatorial in nature. This is reflected in the many combinatorial (distributed) algorithms for graph problems. In the last 20 years, algebraic techniques have become more prevalent in graph algorithms, also named the Laplacian paradigm. This has also had its impact on the distributed setting. In this talk, I'll take some time to go through the relevant definitions (what is a Laplacian matrix?) and then give an overview of the distributed applications (how do you use this to compute max flow?).