Choreographies are coordination plans for concurrent and distributed systems. They define the roles of the involved participants and how they are supposed to work together. In the paradigm of choreographic programming, choreographies are programs that can be compiled into executable, correct-by-construction, decentralised implementations. This talk introduces the paradigm of choreographic programming, its key principles and benefits, and how it has recently matured from a theory based on process algebra to a full-fledged programming paradigm that has been applied to popular languages like Java, Haskell, and Rust to write distributed software more concisely and correctly.

In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of R^N such that for each v in V the ball B(v,1) intersects V on at least delta*|V| points, then for every epsilon>0, the points of V can be covered with f(delta,epsilon) balls B(v,1+epsilon) with v in V. DNL also applies to other metric spaces and to abstract set systems. In its strongest form, DNL provides an epsilon-clustering with size exponential in 1/epsilon, which amounts to a Regularity Lemma with 0/1 densities of some trigraph.

I will discuss the notion of VC-dimension, and explain how to generalize it to trigraphs to obtain statements such as DNL. I will then discuss some applications of DNL to the chromatic number of dense triangle-free graphs, and to domination in majority tournaments.

We study the minority-opinion dynamics over a fully-connected network of $n$ nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at random. Each activated node then adopts the opinion that is least common within the received sample. Unlike all other known consensus dynamics, we prove that this elementary protocol behaves in different ways, depending on whether activations occur sequentially or in parallel. Specifically, we show that its expected consensus time is exponential in n under asynchronous models, but, on the other hand, we show that it converges within $O(\log^2 n)$ rounds with high probability under synchronous models.

Our results shed light on the bit-dissemination problem, which was previously introduced to model the spread of information in biological scenarios. Specifically, our analysis implies that the minority-opinion dynamics is the first memoryless solution to this problem, in the parallel passive-communication setting, achieving convergence within a polylogarithmic number of rounds. This, together with a known lower bound for sequential stateless dynamics, implies a parallel-vs-sequential gap for this problem that is nearly quadratic in the number $n$ of nodes. This is in contrast to all known results for problems in this area, which exhibit a linear gap between the parallel and the sequential setting.

Quivers and their representations offer a natural language for formulating and solving various matrix problems. In this talk, we will start with an elementary approach to the subject and proceed through the lens of the representation theory of associative algebras. We then present Gabriel’s celebrated theorem, which classifies quivers with only finitely many indecomposable representations. Finally, we discuss how the theory developed by Auslander and Reiten provides a method for constructing (many of) the indecomposable representations. The talk will be accessible and requires only a background in linear algebra.

The parity index problem of tree automata asks, given a regular tree language L and a set of priorities J, is L J-feasible, that is, recognized by a nondeterministic parity automaton with priorities J. The minimal such J for a language is called its Mostowski index. This is a long-standing open problem, of which only a few sub-cases and variations are known to be decidable. Starting from the work from Colcombet and Löding on this same problem, we provide a new characterization of the J-feasibility, using tools from the parity game literature. We add some counters to Lehtinen’s register game, originally used to solve parity games in quasipolynomial time, and use this novel game to characterize J-feasibility. This provides a simple alternative proof to Colcombet and Löding’s reduction. Starting from this reduction, we exhibit two other characterizations, linking the index problem with universal trees and with a parameterized version of the Strahler number, a measure of the branching degree of a finite-depth tree. While we do not solve the decidability of the index problem, our work makes the state-of-the-art more accessible and brings to light the deep relationships between the J-feasability of a language and attractor decompositions, universal trees and Lehtinen’s register game.