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: TBA