Search papers, labs, and topics across Lattice.
This paper presents a one-round randomized distributed algorithm for 2-coloring cycles, improving the upper bound on the expected fraction of monochromatic edges to less than 0.24118. It also establishes a lower bound of 0.23879 for any one-round algorithm. Notably, the proof was largely developed by large language models and formalized in Lean 4, demonstrating the potential of AI-assisted mathematical discovery.
LLMs helped discover a new algorithm for 2-coloring cycles, achieving a tighter bound on monochromatic edges than previously known.
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.
