Distributed Computing, Random Processes, Descriptive Combinatorics

The aim of this mini-course is to discuss the emerginng connections between these fields. The common link is played by the so called locally checkable labeling problems, graph problems where the solution can be checked locally. We discuss and compare various techniques that allows to solve such problems ''effectively'' on bounded degree graphs.

We meet on Tuesdays 1pm UK time in the room B3.02, or on ZOOM.
Lecture 1: Local problems, pdf
Lecture 2: Local algorithms (uniform and non-uniform) pdf
Lecture 3: Complexity classes pdf
Lecture 4: Uniform algorithms pdf
Lecture 5: Random processes pdf
Lecture 6: 3-coloring of grids pdf
Lecture 7: Continuous colorings pdf
Lecture 8: Borel colorings pdf
Lecture 9: Lower bounds for vertex Δ-coloring in LOCAL model pdf

Relevant literature