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