[{"article_processing_charge":"No","doi":"10.1145/3087801.3087833","date_updated":"2021-01-12T08:09:39Z","author":[{"full_name":"Brandt, Sebastian","first_name":"Sebastian","last_name":"Brandt"},{"full_name":"Hirvonen, Juho","last_name":"Hirvonen","first_name":"Juho"},{"last_name":"Korhonen","first_name":"Janne H.","full_name":"Korhonen, Janne H."},{"first_name":"Tuomo","last_name":"Lempiäinen","full_name":"Lempiäinen, Tuomo"},{"full_name":"Östergård, Patric R.J.","last_name":"Östergård","first_name":"Patric R.J."},{"first_name":"Christopher","last_name":"Purcell","full_name":"Purcell, Christopher"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","full_name":"Rybicki, Joel","last_name":"Rybicki","orcid":"0000-0002-6432-6646","first_name":"Joel"},{"full_name":"Suomela, Jukka","first_name":"Jukka","last_name":"Suomela"},{"full_name":"Uznański, Przemysław","first_name":"Przemysław","last_name":"Uznański"}],"date_published":"2017-07-01T00:00:00Z","quality_controlled":"1","extern":"1","abstract":[{"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.","lang":"eng"}],"publisher":"ACM Press","title":"LCL problems on grids","conference":{"name":"PODC: Principles of Distributed Computing","end_date":"2017-07-27","location":"Washington, DC, United States","start_date":"2017-07-25"},"date_created":"2019-10-08T12:47:46Z","oa_version":"None","day":"01","status":"public","month":"07","language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781450349925"]},"citation":{"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>","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.","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>.","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.","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.","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>.","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>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","page":"101-110","year":"2017","publication_status":"published","_id":"6932"}]