Locally checkable labelings with small messages

Alkida Balliu; Keren Censor-Hillel; Yannic Maus; Dennis Olivetti; Jukka Suomela

doi:10.4230/LIPIcs.DISC.2021.8

Locally checkable labelings with small messages

Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

13 Citations (Scopus)

41 Downloads (Pure)

Abstract

A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires Ω̃(n^{1/2}) rounds in the CONGEST model.

Original language	English
Title of host publication	35th International Symposium on Distributed Computing, DISC 2021
Editors	Seth Gilbert
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	18
ISBN (Electronic)	978-3-95977-210-5
DOIs	https://doi.org/10.4230/LIPIcs.DISC.2021.8
Publication status	Published - 2021
MoE publication type	A4 Conference publication
Event	International Symposium on Distributed Computing - Virtual, Online, Freiburg, Germany Duration: 4 Oct 2021 → 8 Oct 2021 Conference number: 35

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume	209
ISSN (Electronic)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Abbreviated title	DISC
Country/Territory	Germany
City	Freiburg
Period	04/10/2021 → 08/10/2021

Access to Document

10.4230/LIPIcs.DISC.2021.8

Locally checkable labelings with small messagesFinal published version, 709 KBLicence: CC BY

Cite this

Balliu, A., Censor-Hillel, K., Maus, Y., Olivetti, D., & Suomela, J. (2021). Locally checkable labelings with small messages. In S. Gilbert (Ed.), 35th International Symposium on Distributed Computing, DISC 2021 Article 8 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 209). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.8

@inproceedings{acb9c5fb2a884c62889fccd485555b37,

title = "Locally checkable labelings with small messages",

abstract = "A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires {\~Ω}(n^{1/2}) rounds in the CONGEST model. ",

author = "Alkida Balliu and Keren Censor-Hillel and Yannic Maus and Dennis Olivetti and Jukka Suomela",

note = "| openaire: EC/H2020/755839/EU//BANDWIDTH ; International Symposium on Distributed Computing, DISC ; Conference date: 04-10-2021 Through 08-10-2021",

year = "2021",

doi = "10.4230/LIPIcs.DISC.2021.8",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Seth Gilbert",

booktitle = "35th International Symposium on Distributed Computing, DISC 2021",

address = "Germany",

}

Balliu, A, Censor-Hillel, K, Maus, Y, Olivetti, D & Suomela, J 2021, Locally checkable labelings with small messages. in S Gilbert (ed.), 35th International Symposium on Distributed Computing, DISC 2021., 8, Leibniz International Proceedings in Informatics (LIPIcs), vol. 209, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Freiburg, Germany, 04/10/2021. https://doi.org/10.4230/LIPIcs.DISC.2021.8

Locally checkable labelings with small messages. / Balliu, Alkida; Censor-Hillel, Keren; Maus, Yannic et al.
35th International Symposium on Distributed Computing, DISC 2021. ed. / Seth Gilbert. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. 8 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 209).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Locally checkable labelings with small messages

AU - Balliu, Alkida

AU - Censor-Hillel, Keren

AU - Maus, Yannic

AU - Olivetti, Dennis

AU - Suomela, Jukka

N1 - Conference code: 35

PY - 2021

Y1 - 2021

N2 - A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires Ω̃(n^{1/2}) rounds in the CONGEST model.

AB - A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires Ω̃(n^{1/2}) rounds in the CONGEST model.

UR - http://www.scopus.com/inward/record.url?scp=85113581492&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.DISC.2021.8

DO - 10.4230/LIPIcs.DISC.2021.8

M3 - Conference article in proceedings

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 35th International Symposium on Distributed Computing, DISC 2021

A2 - Gilbert, Seth

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Symposium on Distributed Computing

Y2 - 4 October 2021 through 8 October 2021

ER -

Locally checkable labelings with small messages

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this