k-server-bench: Automating Potential Discovery for the k-Server Conjecture
Published in 3rd AI for Math Workshop at ICML, 2026
We introduce a code-based benchmark for discovering potential functions for the k-server conjecture. Candidates are evaluated against a graph-structured system of linear inequalities: violations refute a candidate, while passing all constraints provides evidence toward a proof rather than a proof itself. Experiments show that discovery agents can solve nontrivial instances for k = 3 and reduce violations in the open k = 4 circle case without fully resolving it.
Recommended citation: Kirill Brilliantov, Etienne Bamas, and Emmanuel Abbé. "k-server-bench: Automating Potential Discovery for the k-Server Conjecture." 3rd AI for Math Workshop at ICML, 2026.
Download Paper