Locally checkable labelings with small messages

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

12 Sitaatiot (Scopus)
69 Lataukset (Pure)

Abstrakti

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.
AlkuperäiskieliEnglanti
Otsikko35th International Symposium on Distributed Computing, DISC 2021
ToimittajatSeth Gilbert
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivumäärä18
ISBN (elektroninen)978-3-95977-210-5
DOI - pysyväislinkit
TilaJulkaistu - 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Symposium on Distributed Computing - Virtual, Online, Freiburg, Saksa
Kesto: 4 lokak. 20218 lokak. 2021
Konferenssinumero: 35

Julkaisusarja

NimiLeibniz International Proceedings in Informatics (LIPIcs)
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Vuosikerta209
ISSN (elektroninen)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
LyhennettäDISC
Maa/AlueSaksa
KaupunkiFreiburg
Ajanjakso04/10/202108/10/2021

Sormenjälki

Sukella tutkimusaiheisiin 'Locally checkable labelings with small messages'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä