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…