---
_id: '6932'
abstract:
- lang: eng
  text: "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.\r\nNevertheless,
    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.\r\nFinally,
    partially with the help of automated design tools, we classify the complexity
    of several concrete LCL problems related to colourings and orientations."
article_processing_charge: No
author:
- first_name: Sebastian
  full_name: Brandt, Sebastian
  last_name: Brandt
- first_name: Juho
  full_name: Hirvonen, Juho
  last_name: Hirvonen
- first_name: Janne H.
  full_name: Korhonen, Janne H.
  last_name: Korhonen
- first_name: Tuomo
  full_name: Lempiäinen, Tuomo
  last_name: Lempiäinen
- first_name: Patric R.J.
  full_name: Östergård, Patric R.J.
  last_name: Östergård
- first_name: Christopher
  full_name: Purcell, Christopher
  last_name: Purcell
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
- first_name: Jukka
  full_name: Suomela, Jukka
  last_name: Suomela
- first_name: Przemysław
  full_name: Uznański, Przemysław
  last_name: Uznański
citation:
  ama: 'Brandt S, Hirvonen J, Korhonen JH, et al. LCL problems on grids. In: ACM Press;
    2017:101-110. doi:<a href="https://doi.org/10.1145/3087801.3087833">10.1145/3087801.3087833</a>'
  apa: 'Brandt, S., Hirvonen, J., Korhonen, J. H., Lempiäinen, T., Östergård, P. R.
    J., Purcell, C., … Uznański, P. (2017). LCL problems on grids (pp. 101–110). Presented
    at the PODC: Principles of Distributed Computing, Washington, DC, United States:
    ACM Press. <a href="https://doi.org/10.1145/3087801.3087833">https://doi.org/10.1145/3087801.3087833</a>'
  chicago: Brandt, Sebastian, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen,
    Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław
    Uznański. “LCL Problems on Grids,” 101–10. ACM Press, 2017. <a href="https://doi.org/10.1145/3087801.3087833">https://doi.org/10.1145/3087801.3087833</a>.
  ieee: 'S. Brandt <i>et al.</i>, “LCL problems on grids,” presented at the PODC:
    Principles of Distributed Computing, Washington, DC, United States, 2017, pp.
    101–110.'
  ista: 'Brandt S, Hirvonen J, Korhonen JH, Lempiäinen T, Östergård PRJ, Purcell C,
    Rybicki J, Suomela J, Uznański P. 2017. LCL problems on grids. PODC: Principles
    of Distributed Computing, 101–110.'
  mla: Brandt, Sebastian, et al. <i>LCL Problems on Grids</i>. ACM Press, 2017, pp.
    101–10, doi:<a href="https://doi.org/10.1145/3087801.3087833">10.1145/3087801.3087833</a>.
  short: S. Brandt, J. Hirvonen, J.H. Korhonen, T. Lempiäinen, P.R.J. Östergård, C.
    Purcell, J. Rybicki, J. Suomela, P. Uznański, in:, ACM Press, 2017, pp. 101–110.
conference:
  end_date: 2017-07-27
  location: Washington, DC, United States
  name: 'PODC: Principles of Distributed Computing'
  start_date: 2017-07-25
date_created: 2019-10-08T12:47:46Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2021-01-12T08:09:39Z
day: '01'
doi: 10.1145/3087801.3087833
extern: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 101-110
publication_identifier:
  isbn:
  - '9781450349925'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
status: public
title: LCL problems on grids
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...