Distributed computing and finitary factors of iid labelings
Locally checkable labeling (LCL) problems are graph problems where the validity of a solution can be checked locally. Examples include proper vertex or edge colorings, perfect matching etc.
Such problems have been studied from different points of view. Most important for our investigation is the perspective of distributed computing and random processes. The connection between the two fields has been suspected for some time [Holroyd, Schramm, Wilson. Annals of Prob. 2017, Brandt et al. 2017 ] but in our work we give probably the first precise translation between the two worlds. Among others, this almost automatically answers 3 out of 4 open questions from [Holroyd, Schramm, Wilson. Annals of Prob. 2017].
In the first part of the talk we introduce the basic notions from distributed computing. In the second part we use this theory to answer aforementioned questions from [Holroyd, Schramm, Wilson. Annals of Prob. 2017].