PODC 2017 · 36th ACM Symposium on Principles of Distributed Computing, Washington, D.C., USA, July 2017 · doi:10.1145/3087801.3087833

LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of $O(1)$, $\Theta(\log^* n)$, or $\Theta(n)$, and the design of optimal algorithms can be fully automated.

This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: $O(1)$, $\Theta(\log^* n)$, and $\Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $\Theta(\log^* n)$ or $\Theta(n)$ in 2-dimensional grids.

Nevertheless, if we correctly guess that the complexity of a problem is $\Theta(\log^* n)$, we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form $A' \circ S_k$, where $A'$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th power of the grid, and $k$ is a constant.

Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.

Elad Michael Schiller and Alexander A. Schwarzmann (Eds.): *PODC’17, Proceedings of the ACM Symposium on Principles of Distributed Computing, July 25–27, 2017, Washington, DC, USA*, pages 101–110, ACM Press, New York, 2017

ISBN 978-1-4503-4992-5

- presentation, 25 July 2017
- presentation at WOLA 2016, 15 October 2016
- presentation at the Helsinki Algorithms Seminar, 24 November 2016
- presentation at Finite Model Theory seminar, 27 January 2017
- presentation at ETH Zurich, 16 February 2017
- presentation at ETH Zurich, 21 February 2017
- demonstration