Optimal-order randomized k-server on arbitrary metrics

What OpenAI claims

Establishes a randomized competitive ratio O(log²(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. (Lean)

Papers (2)

1. Squared-logarithmic randomized k-server on arbitrary metrics

   24 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract We prove that randomized k-server has competitive ratio O((log(k+1))²) 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.

2. Uniform computation of the squared-logarithmic k-server bound

   24 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract We construct a uniform randomized k-server algorithm on finite rational metrics with competitive ratio O(log²(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.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.