Locally checkable labelings with small messages

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)
1 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 languageEnglish
Title of host publication35th International Symposium on Distributed Computing, DISC 2021
EditorsSeth Gilbert
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages18
ISBN (Electronic)9783959772105
DOIs
Publication statusPublished - 2021
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Distributed Computing - Virtual, Online, Freiburg, Germany
Duration: 4 Oct 20218 Oct 2021
Conference number: 35

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume209
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
Country/TerritoryGermany
CityFreiburg
Period04/10/202108/10/2021

Fingerprint

Dive into the research topics of 'Locally checkable labelings with small messages'. Together they form a unique fingerprint.

Cite this