**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.

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

- Vašek gave a nice introductory tutorial about the connections.
- Jukka's introduction to the LOCAL model.
- Hironen, Suomela Book about distributed algorithms.
- Oleg's introduction to Descriptive combinatorics
- Anton's Measurable LLL
- Anton's Continuous is log*
- Subexponential LLL
- LCLs on Tress
- LCLs on paths
- LCLs on grids
- Andrew's Determinacy method