Descriptive set theory and distributed computing
Abstract: The fact that a given graph has chromatic number $k\in \mathbb{N}$ does not necessarily mean that there is an efficient way to produce a $k$-coloring. This phenomenon has been studied from different perspectives in various areas of mathematics and computer science.
I will discuss recent results that formally connect a part of descriptive set theory that studies the existence of measurable solutions to local coloring problems on Borel graphs, so-called Descriptive graph combinatorics, and the LOCAL model of distributed computing that studies the existence of efficient distributed algorithms that produce solutions to local coloring problems on finite graphs.