Distributed computing and descriptive combinatorics

In distributed computing, the studied setup is a network of computers where each computer can only communicate with its neighbors. The question of interest in this area is to understand which local problems can be solved with only a few rounds of communication in the underlying network.

The goal of the area of descriptive combinatorics is to understand which constructions on infinite graphs can be performed without using the so-called axiom of choice. This leads to problems such as measurable circle squaring etc.

In this talk, I will discuss the recently discovered connections between these two fields (an approach initiated by Bernshteyn). In particular, I will focus on a lower bound technique in the LOCAL model of distributed computing that is derived from the celebrated determinacy method of Marks. This is joint work with Brandt, Chang, Grunau, Rozhoň and Vidnyánszky arXiv:2106.02066