aalto1 untyped-item.component.html
Locally checkable labelings with small messages
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
18
Series
35th International Symposium on Distributed Computing, DISC 2021, Leibniz International Proceedings in Informatics (LIPIcs) ; Volume 209
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.
Description
| openaire: EC/H2020/755839/EU//BANDWIDTH
Keywords
Other note
Citation
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