Browse › Theoretical computer science › 110 Optimal-order randomized k-server on arbitrary metrics
Uniform computation of the squared-logarithmic k-server bound
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 construct a uniform randomized k-server algorithm on finite rational metrics with competitive ratio $O(\log^2(k+1))$ against oblivious request sequences. Preprocessing is polynomial in the input length, and per-request bit complexity is polynomial in that length and the binary request-counter length. The additive movement constant is finite and instance-dependent, but may be enormous. The construction uses the companion squared-logarithmic existence theorem.
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 a uniform randomized bit algorithm on finite rational metrics was formalized, with polynomial preprocessing and per-request time and an additive movement constant not claimed to be polynomially bounded, and it links the comparator statements. [family-level]
- OpenAI, UniformKServer/Main.lean (openai/math, commit adc7f12). Lean file containing
uniform_squared_logarithmic_main : UniformAlgorithmClaim, the formal counterpart of Theorem 1.1. The file shows nosorry, but it imports further modules that were not inspected here. - OpenAI, ComparatorChallenges/UniformKServer.lean (openai/math, commit adc7f12). Standalone comparator statement (proof left as
sorryby design) covering boot halting, legal server labels on reachable requests, and the expected-cost bound, phrased via a bit-machine model.
Possibly relevant literature (found by the agent, not checked)
- Ben-David, Borodin, Karp, Tardos, Wigderson, On the power of randomization in on-line algorithms (Algorithmica 11 (1994), 2–14, doi:10.1007/BF01294260). Classical game-theoretic treatment of online adversary models, including when an existentially proved online algorithm can actually be constructed; possibly relevant to the paper's goal of turning the companion paper's existence theorem into a computable algorithm.
- Bubeck, Cohen, Lee, Lee, Mądry, k-server via multiscale entropic regularization (arXiv:1711.01085, STOC 2018). Source of the $O(\log^2 k)$ HST algorithm and the $O(\log^3 k\log\Delta)$ dynamic-embedding bound, cited in the companion paper but not here; possibly relevant to this paper's comparison with the Coester–Cosson $O(\log n\log^2 k)$ bound (Section 1.1).
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 with an unrestricted additive constant; it states that it did not independently verify the complete proofs. [family-level]
Elsewhere
- Emergent Mind: family 110
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026,
author = {{OpenAI}},
title = {{Uniform computation of the squared-logarithmic $k$-server bound}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026.pdf}{OAI:Uniform-computation-of-the-squared-logarithmic-k-server-bound-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:
- Squared-logarithmic randomized k-server on arbitrary metrics · September 24, 2026