Orientation does not help with 3-coloring a grid in online-LOCAL
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915516523741184 |
|---|---|
| author | Boudier, Thomas Casagrande, Filippo Das, Avinandan Equi, Massimo Lievonen, Henrik Modanese, Augusto Stimpert, Ronja |
| author_facet | Boudier, Thomas Casagrande, Filippo Das, Avinandan Equi, Massimo Lievonen, Henrik Modanese, Augusto Stimpert, Ronja |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22233 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Orientation does not help with 3-coloring a grid in online-LOCAL Boudier, Thomas Casagrande, Filippo Das, Avinandan Equi, Massimo Lievonen, Henrik Modanese, Augusto Stimpert, Ronja Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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. |
| title | Orientation does not help with 3-coloring a grid in online-LOCAL |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.22233 |