@inproceedings{6932,
  abstract     = {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), Θ(log* n), or Θ(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), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids.
Nevertheless, if we correctly guess that the complexity of a problem is Θ(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' o Sk, where A' is a finite function, Sk is an algorithm for finding a maximal independent set in kth 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.},
  author       = {Brandt, Sebastian and Hirvonen, Juho and Korhonen, Janne H. and Lempiäinen, Tuomo and Östergård, Patric R.J. and Purcell, Christopher and Rybicki, Joel and Suomela, Jukka and Uznański, Przemysław},
  isbn         = {9781450349925},
  location     = {Washington, DC, United States},
  pages        = {101--110},
  publisher    = {ACM Press},
  title        = {{LCL problems on grids}},
  doi          = {10.1145/3087801.3087833},
  year         = {2017},
}