Brief announcement: 2-coloring cycles in one round

Flin, Maxime; Raevskaya, Alesya; Stimpert, Ronja; Suomela, Jukka; Yang, Qingxin

doi:10.1145/3796701.3815937

Maxime Flin · Alesya Raevskaya · Ronja Stimpert · Jukka Suomela · Qingxin Yang

Brief announcement: 2-coloring cycles in one round

PODC 2026 · 45th ACM Symposium on Principles of Distributed Computing, Egham, United Kingdom, July 2026 · doi:10.1145/3796701.3815937

authors’ version publisher’s version arXiv.org

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 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.

Publication

Eric Ruppert and Dennis Olivetti (Eds.): PODC ’26, Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing, pages 44–47, 2026

ISBN 979-8-4007-2512-8

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.