2-Coloring Cycles in One Round

arXiv:2603.04235v2 Announce Type: replace Abstract: 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 that a one-round algorithm cannot achieve a ...

🔗 Read more: https://arxiv.org/abs/2603.04235

#News #Policy #AI #Academic