2-Coloring Cycles in One Round
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911488169476096 |
|---|---|
| author | Flin, Maxime Raevskaya, Alesya Stimpert, Ronja Suomela, Jukka Yang, Qingxin |
| author_facet | Flin, Maxime Raevskaya, Alesya Stimpert, Ronja Suomela, Jukka Yang, Qingxin |
| contents | 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 fraction less than 0.23879. Before this work, the best upper and lower bounds were 0.25 and 0.2. Our proof was largely discovered and developed by large language models, and both the upper and lower bounds have been formalized in Lean 4. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04235 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | 2-Coloring Cycles in One Round Flin, Maxime Raevskaya, Alesya Stimpert, Ronja Suomela, Jukka Yang, Qingxin Distributed, Parallel, and Cluster Computing Formal Languages and Automata Theory 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 fraction less than 0.23879. Before this work, the best upper and lower bounds were 0.25 and 0.2. Our proof was largely discovered and developed by large language models, and both the upper and lower bounds have been formalized in Lean 4. |
| title | 2-Coloring Cycles in One Round |
| topic | Distributed, Parallel, and Cluster Computing Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2603.04235 |