Modern communication networks support local fast-rerouting mechanisms that react to link failures without first communicating failure information through the network's control plane. This allows them to respond orders of magnitude faster than traditional approaches, reducing packet loss and improving throughput.

Such mechanisms are based on static failover rules that are predefined at each node. A forwarding decision may depend on locally available information, such as the incoming port, the destination of the packet, and the status of incident links, but not on failures elsewhere in the network. Ideally, these local rules provide perfect resilience: every packet reaches its destination as long as its source and destination remain connected after the link failures. Perfect resilience, however, cannot always be achieved. In fact, there are networks on only five vertices for which no perfectly resilient routing exists.

A natural weaker goal is ideal resilience. If the underlying network is $k$-link-connected, we ask only that every packet be delivered whenever at most $k-1$ links fail. Whether ideal resilience can always be achieved remains an open problem.

In this talk, I will give an overview of positive and negative results on local network resilience and highlight some of the ideas behind their proofs. We will also encounter a curious complexity phenomenon: finding a perfectly resilient routing is possible in polynomial time, while verifying that a given routing is perfectly resilient is coNP-hard.

What can a distributed system compute when messages convey no information beyond their arrival? This talk explores asynchronous networks in which an adversary may arbitrarily corrupt every message, while preserving its delivery. Communication then reduces to exchanging content-free pulses. I will survey the content-oblivious model, explain how reliable computation can nevertheless be achieved, and discuss the role of network connectivity and leader election. The talk will also highlight open questions in this interesting and extremely restricted model.

In this talk, I will present a constant-round quantum-LOCAL algorithm for 3-coloring directed cycles with high probability. This follows from the surprising fact that for every $\varepsilon > 0$, there exists a one-way one-round quantum-LOCAL algorithm coloring nodes with 20,000 colors such that, for each edge, its endpoints receive the same color with probability at most $\varepsilon$.

Local certification (also known as proof-labeling schemes) asks: can nodes of a distributed network verify a global graph property using only small-sized certificates and one (or constant) round of local communication? Over the past decade, compact certifications — using certificates of size $O(\log n)$, which is information-theoretically optimal for many properties — have been found for specific properties, including spanning trees, planarity, bounded-genus embeddability. A central open question in the area is whether every minor-closed property admits a compact proof-labeling scheme.

In this talk, I will survey the landscape of known local certification results for graph properties, with particular focus on minor-closed families and the structural tools underlying compactness results in this setting. We also review our recent tight meta-theorem (Cook, Kim, Masařík 2025): for every integer $k$ and every property expressible in Monadic Second-Order Logic ($\mathrm{MSO}_2$), there is a proof-labeling scheme of size $O(\log n)$ for graphs of treewidth at most $k$.

How efficiently can we determine how many vertex failures a network can withstand before becoming disconnected? This question is captured by vertex connectivity, a classical graph problem that has seen substantial progress in recent years.

In this talk, I will survey these developments, starting with the ideas behind fast sequential algorithms, new structural results and new direction for distributed computation. A central theme is the relationship between finding a minimum global vertex cut and finding minimum vertex cut that separating two vertices. While these problems have nearly equivalent complexity in the sequential setting, their relationship across other computational models reveals both efficient reductions and surprising separations.

Significant effort has been devoted over the past decade to understanding whether quantum resources can offer advantages in distributed computing, and in particular whether they can help overcome locality constraints in networks, typically in Linial's LOCAL model.

In this talk, I will consider the 3-coloring problem on rooted trees. For rooted trees, the deterministic Cole-Vishkin algorithm 3-colors $n$-node trees in $O(\log^{\star} n)$ rounds, matching Linial's classical $\Omega(\log^{\star} n)$ lower bound (FOCS 1987), which holds even for randomized algorithms.

I will show that any algorithm in quantum-LOCAL (without pre-shared entanglement) that properly 3-colors $n$-node rooted trees with probability at least $1-O(1/\log n)$ must perform $\Omega(\log^{\star} n)$ rounds. That is, quantum resources provide no advantage for 3-coloring rooted trees. To prove this, we show a lower bound of $\Omega(\log^{\star}\Delta)$ for 3-coloring any $\Delta$-ary tree with success probability at least $1-1/\Delta$. Our lower bound holds more generally in the non-signaling, bounded-dependence model, which formalizes the principle of physical causality in distributed computing. The proof uses a color lifting technique that departs from the indistinguishability-based arguments underlying most prior non-signaling lower bounds, and instead is similar to Linial's original argument.

This talk is based on joint work with Frédéric Magniez and Pierre Fraigniaud.