Confirmed Speakers

Abstract: The maximum matching problem has attracted significant attention in both dynamic and sub-linear models of computation in recent years. Interestingly, some long-standing barriers for this problem have been overcome by combining algorithmic techniques from both models. In this talk, we will survey recent developments in algorithms for matching within these models and discuss their implications for related graph and geometric problems.

Abstract: In a distributed model of computation that puts no restriction on message size like LOCAL, it makes little difference whether an algorithm is performing computation about the communication network G or a different graph whose information can be locally inferred by the nodes -- as is the case, e.g., for a power graph $G^k$ or the line graph $L(G)$. The situation is quite different with messages of bounded size, i.e., "congestion" constraints. It is natural to ask what is the exact cost of congestion, and in particular, what can be achieved in roughly the same runtime as without congestion?

In this talk, we will see some recent results addressing these questions, achieving in particular an $O(\log^* n)$ randomized algorithm for distance-2 $(\Delta^2+1)$-coloring in communication graphs $G$ of a large enough maximum degree Delta. We will see the main algorithmic insights underlying this kind of results, and in particular the critical role played by randomness as our algorithms make use of probabilistic counting, sampling, and hashing. Primarily based on joint work with Maxime Flin and Magnús Halldórsson.

Abstract: This talk explores recent advances in streaming algorithms for graph matching in massive graphs. I will first present a new deterministic semi-streaming algorithm that achieves a $(1+ε)$-approximation using significantly fewer passes, advancing our understanding of space-pass trade-offs beyond the breakthrough result of Fischer, Mitrović, and Uitto (STOC 2022). In the remaining time, I will turn to a streaming-in-MPC setting, where the input arrives as a stream while computation is distributed across machines with highly restrictive local memory. I will discuss how matchings can be maintained efficiently in this model, with minimal communication rounds and near-optimal total memory.