3 papers
cs.DC2026
2-Coloring Cycles in One Round
Maxime Flin, Alesya Raevskaya, Ronja Stimpert +2
We show that there is a one-round randomized distributed algorithm that can 2-color cycles such that the expected fraction of monochromatic edges is less than 0.24118. We also show…
cs.DC2026
Classification of Local Optimization Problems in Directed Cycles
Thomas Boudier, Fabian Kuhn, Augusto Modanese +2
We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles for both the deterministic and the randomized LOC…
cs.DC2025
Orientation does not help with 3-coloring a grid in online-LOCAL
Thomas Boudier, Filippo Casagrande, Avinandan Das +4
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 o…