Browse › Theoretical computer science › 110 Optimal-order randomized k-server on arbitrary metrics
Squared-logarithmic randomized k-server on arbitrary metrics
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove that randomized k-server has competitive ratio $O((\log(k+1))^2)$ on every metric space against oblivious request sequences, matching the known worst-case lower bound. For each metric and initial configuration, one policy works for all finite request sequences, including on infinite and unbounded spaces. When the initial server positions are distinct, no additive term is needed.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Lean scope notes for family 110: Optimal-order randomized k-server on arbitrary metrics (lean/docs/110.md, October 2026). The release's own scope description: it says the formalization proves the $O((\log(k+1))^2)$ bound for all $k\ge2$ and all metric spaces with at least $k+1$ points, with an additive constant that is zero for distinct starts, and it links the comparator statements for this and the companion uniform-computation result. [family-level]
- OpenAI, KServer/Main.lean (openai/math, commit adc7f12). Lean file containing
main_theorem : MainStatement, the formal counterpart of Theorem 1.1. The file shows nosorry, but it imports further modules that were not inspected here. - OpenAI, ComparatorChallenges/KServer.lean (openai/math, commit adc7f12). Standalone comparator statement of the main theorem (proof left as
sorryby design), for checking that the formal statement matches Theorem 1.1.
Possibly relevant literature (found by the agent, not checked)
- Indyk, Magen, Sidiropoulos, Zouzias, Online Embeddings (APPROX-RANDOM 2010, LNCS 6302, 246–259). Studies metric embeddings, including into distributions over ultrametrics, built as points arrive; possibly relevant to the paper's request-driven changing partitions (Sections 7–8) and its discussion of dynamic embeddings.
- Bubeck, Cohen, Lee, Lee, Metrical task systems on trees via mirror descent and unfair gluing (arXiv:1807.04404, 2018). Companion to the cited BCLLM18 mirror-descent framework, applied to HSTs; possibly relevant to the tree allocation theorem (Sections 3–5) and its treatment of per-level losses.
- Wenbin Chen, An O(log k log^2 n)-competitive Randomized Algorithm for the k-Sever Problem (arXiv:1510.07773, 2015). Claims a finite-metric bound with $n$-dependence that the introduction's survey of prior bounds (BBMN15, BCLLM18) does not mention; the arXiv page carries an admin note about text overlap with arXiv:1410.4955.
Digests and expositions
- Latent Seminar, Randomized k-server: competitive ratios and uniform computation (blog exposition, 2026-10-07). Exposition of both manuscripts' proof mechanisms, including partition and allocation costs, the bounded request filter, and delayed activation; it states that it did not independently verify the complete proofs. [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 110
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026,
author = {{OpenAI}},
title = {{Squared-logarithmic randomized $k$-server on arbitrary metrics}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf}{OAI:Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/110.md. The Lean statements have not been checked by people against the paper's claims.
Family 110: Optimal-order randomized k-server on arbitrary metrics
Establishes a randomized competitive ratio $O(\log^2(k+1))$ for k-server on every metric space, matching the worst-case lower-bound order. One policy serves every finite oblivious request sequence, including on infinite unbounded metrics. On finite rational metrics, a uniform implementation has polynomial preprocessing and per-request bit cost in the input length and $\log(t+1)$ at request t, with a finite instance-dependent additive movement constant.
Other papers in this family:
- Uniform computation of the squared-logarithmic k-server bound · September 24, 2026