aalto1 untyped-item.component.html
Orientation does not help with 3-coloring a grid in online-LOCAL
Loading...
Access rights
openAccess
CC BY
CC BY
Creative Commons license
Except where otherwised noted, this item's license is described as 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)
Other link related to publication (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)
Other link related to publication (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
16
Series
29th International Conference on Principles of Distributed Systems (OPODIS 2025), pp. 1-16, Leibniz International Proceedings in Informatics (LIPIcs) ; Volume 361
Abstract
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know of where the global memory of the online-LOCAL model has an advantage over SLOCAL is 3-coloring bipartite graphs. Recently, Chang et al. [PODC 2024] showed that even in grids, 3-coloring requires Ω(log n) locality in deterministic online-LOCAL. This result was subsequently extended by Akbari et al. [STOC 2025] to also hold in randomized online-LOCAL. However, both proofs heavily rely on the assumption that the algorithm does not have access to the orientation of the underlying grid. In this paper, we show how to lift this requirement and obtain the same lower bound (against either model) even when the algorithm is explicitly given a globally consistent orientation of the grid.
Description
Other note
Citation
Boudier, T, Casagrande, F, Das, A, Equi, M, Lievonen, H, Modanese, A & Stimpert, R 2026, Orientation does not help with 3-coloring a grid in online-LOCAL. in A Arusoaie, E Onica, M Spear & S Tucci-Piergiovanni (eds), 29th International Conference on Principles of Distributed Systems (OPODIS 2025)., 19, Leibniz International Proceedings in Informatics (LIPIcs), vol. 361, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-16, International Conference on Principles of Distributed Systems, Iaşi, Romania, 03/12/2025. https://doi.org/10.4230/LIPIcs.OPODIS.2025.19