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.

Relevant literature

• 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