Orientation does not help with 3-coloring a grid in online-LOCAL

Thomas Boudier; Filippo Casagrande; Avinandan Das; Massimo Equi; Henrik Lievonen; Augusto Modanese; Ronja Stimpert

doi:10.4230/LIPIcs.OPODIS.2025.19

Orientation does not help with 3-coloring a grid in online-LOCAL

Thomas Boudier
, Filippo Casagrande
, Avinandan Das
, Massimo Equi
, Henrik Lievonen
, Augusto Modanese
, Ronja Stimpert

Gran Sasso Science Institute

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

3 Downloads (Pure)

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.

Original language	English
Title of host publication	29th International Conference on Principles of Distributed Systems (OPODIS 2025)
Editors	Andrei Arusoaie, Emanuel Onica, Michael Spear, Sara Tucci-Piergiovanni
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-16
Number of pages	16
ISBN (Electronic)	978-3-95977-409-3
DOIs	https://doi.org/10.4230/LIPIcs.OPODIS.2025.19
Publication status	Published - 7 Jan 2026
MoE publication type	A4 Conference publication
Event	International Conference on Principles of Distributed Systems - Iaşi, Romania Duration: 3 Dec 2025 → 5 Dec 2025 Conference number: 29

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Volume	361
ISSN (Electronic)	1868-8969

Conference

Conference	International Conference on Principles of Distributed Systems
Abbreviated title	OPODIS
Country/Territory	Romania
City	Iaşi
Period	03/12/2025 → 05/12/2025

Funding

This work was supported in part by the Research Council of Finland, Grants 359104 and 363558, as well as the Quantum Doctoral Education Pilot, the Ministry of Education and Culture, decision VN/3137/2024-OKM-4.

Keywords

locally checkable labeling problems
coloring
online algorithms

Access to Document

10.4230/LIPIcs.OPODIS.2025.19Licence: CC BY

Orientation_Does_Not_Help_with_3-Coloring_a_Grid_in_Online-LOCALFinal published version, 845 KBLicence: CC BY

https://arxiv.org/abs/2509.22233

Cite this

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) (pp. 1-16). Article 19 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 361). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2025.19

Boudier, Thomas ; Casagrande, Filippo ; Das, Avinandan et al. / Orientation does not help with 3-coloring a grid in online-LOCAL. 29th International Conference on Principles of Distributed Systems (OPODIS 2025). editor / Andrei Arusoaie ; Emanuel Onica ; Michael Spear ; Sara Tucci-Piergiovanni. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. pp. 1-16 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{39959b722d9442bdbc66b4b02c71be70,

title = "Orientation does not help with 3-coloring a grid in online-LOCAL",

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.",

keywords = "locally checkable labeling problems, coloring, online algorithms",

author = "Thomas Boudier and Filippo Casagrande and Avinandan Das and Massimo Equi and Henrik Lievonen and Augusto Modanese and Ronja Stimpert",

year = "2026",

month = jan,

day = "7",

doi = "10.4230/LIPIcs.OPODIS.2025.19",

language = "English",

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

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

pages = "1--16",

editor = "Andrei Arusoaie and Emanuel Onica and Michael Spear and Sara Tucci-Piergiovanni",

booktitle = "29th International Conference on Principles of Distributed Systems (OPODIS 2025)",

address = "Germany",

note = "International Conference on Principles of Distributed Systems, OPODIS ; Conference date: 03-12-2025 Through 05-12-2025",

}

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

Orientation does not help with 3-coloring a grid in online-LOCAL. / Boudier, Thomas; Casagrande, Filippo; Das, Avinandan et al.
29th International Conference on Principles of Distributed Systems (OPODIS 2025). ed. / Andrei Arusoaie; Emanuel Onica; Michael Spear; Sara Tucci-Piergiovanni. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. p. 1-16 19 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 361).

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

TY - GEN

T1 - Orientation does not help with 3-coloring a grid in online-LOCAL

AU - Boudier, Thomas

AU - Casagrande, Filippo

AU - Das, Avinandan

AU - Equi, Massimo

AU - Lievonen, Henrik

AU - Modanese, Augusto

AU - Stimpert, Ronja

N1 - Conference code: 29

PY - 2026/1/7

Y1 - 2026/1/7

N2 - 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.

AB - 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.

KW - locally checkable labeling problems

KW - coloring

KW - online algorithms

UR - https://www.scopus.com/pages/publications/105031419191

U2 - 10.4230/LIPIcs.OPODIS.2025.19

DO - 10.4230/LIPIcs.OPODIS.2025.19

M3 - Conference article in proceedings

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 16

BT - 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

A2 - Arusoaie, Andrei

A2 - Onica, Emanuel

A2 - Spear, Michael

A2 - Tucci-Piergiovanni, Sara

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

T2 - International Conference on Principles of Distributed Systems

Y2 - 3 December 2025 through 5 December 2025

ER -

Boudier T, Casagrande F, Das A , Equi M , Lievonen H , Modanese A et al. Orientation does not help with 3-coloring a grid in online-LOCAL. In Arusoaie A, Onica E, Spear M, Tucci-Piergiovanni S, editors, 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2026. p. 1-16. 19. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.OPODIS.2025.19

Orientation does not help with 3-coloring a grid in online-LOCAL

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Robust/Suomela: Computation in Networks: Robust Foundations

Limits of Causal Comp/Suomela: Limits of Causal Computation

Cite this

Orientation does not help with 3-coloring a grid in online-LOCAL

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Robust/Suomela: Computation in Networks: Robust Foundations

Limits of Causal Comp/Suomela: Limits of Causal Computation

Cite this