arxiv: 2605.01497 · v1 · submitted 2026-05-02 · 💻 cs.DS

Recognition: unknown

Randomized k-server in polynomial time

Christian Coester, Romain Cosson

Pith reviewed 2026-05-09 17:50 UTC · model grok-4.3

classification 💻 cs.DS

keywords k-server problemderandomizationcompetitive analysishierarchically separated treesonline algorithmspolynomial timerandomized algorithms

0 comments

The pith

A derandomization framework converts randomized k-server algorithms on hierarchically separated trees into explicit polynomial-time versions using only O(log k) random bits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a black-box derandomization technique for the k-server problem restricted to hierarchically separated trees. It reduces the randomness requirement to O(log k) bits per arbitrary-length sequence while keeping the maintained distribution over only polynomially many server configurations. This technique is then composed with known metric-to-tree reductions to produce the first randomized k-server algorithm that runs in polynomial time on arbitrary n-point metrics and still achieves a polylogarithmic competitive ratio. A reader would care because prior best randomized algorithms required maintaining distributions over exponentially many configurations and could not be implemented efficiently despite their theoretical performance guarantees.

Core claim

We introduce a derandomization framework that transforms any randomized k-server algorithm on a hierarchically separated tree into one that uses only O(log k) random bits for request sequences of arbitrary length, hence maintaining a distribution over only polynomially many server configurations. Leveraging this black-box derandomization, we obtain the first polynomial-time randomized k-server algorithm on arbitrary n-point metrics with a polylogarithmic competitive ratio.

What carries the argument

The derandomization framework that reduces randomness to O(log k) bits while preserving competitive ratio for k-server algorithms on hierarchically separated trees.

If this is right

The first polynomial-time randomized k-server algorithm on arbitrary n-point metrics with a polylogarithmic competitive ratio.
New implications for the advice complexity of the k-server problem.
Any future randomized HST k-server algorithm can be turned into an explicit polynomial-time version via the same framework.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same derandomization technique could apply to other online problems whose analysis relies on embeddings into hierarchically separated trees.
Improvements to the underlying randomized HST algorithms would immediately translate into better polynomial-time algorithms for general metrics.
This explicitness may help close the gap between theoretical competitive ratios and implementable online decision procedures.

Load-bearing premise

The derandomization preserves the competitive ratio of any input randomized HST algorithm even for arbitrarily long sequences, and existing metric-to-HST reductions compose while retaining both polynomial runtime and the polylogarithmic guarantee.

What would settle it

A concrete long request sequence on an HST for which the derandomized algorithm incurs cost more than a constant factor above the original randomized algorithm's expected cost, or a general metric on which the composed algorithm exceeds polynomial time.

read the original abstract

We study the design of computationally efficient randomized algorithms for the $k$-server problem. Existing randomized algorithms with the best known competitive ratios are, on the one hand, inherently implicit and, on the other hand, employ a rounding scheme that maintains a distribution over exponentially many configurations. In this work, we introduce a derandomization framework that transforms any randomized $k$-server algorithm on a hierarchically separated tree into one that uses only $O(\log k)$ random bits for request sequences of arbitrary length; hence maintaining a distribution over only polynomially many server configurations. Leveraging this black-box derandomization, we obtain the first polynomial-time randomized $k$-server algorithm on arbitrary $n$-point metrics with a polylogarithmic competitive ratio. Our results also have implications for the advice complexity of the $k$-server problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They derandomize HST k-server to O(log k) bits total and compose it to get the first poly-time polylog-competitive randomized algorithm on general metrics, but the ratio preservation on long sequences needs close checking.

read the letter

The main takeaway is that Coester and Cosson have a black-box way to take any randomized k-server algorithm on hierarchically separated trees and turn it into one that uses only O(log k) random bits for the entire request sequence, no matter how long. This keeps the distribution over polynomially many configurations and lets them plug in the standard metric-to-HST reductions to claim the first polynomial-time randomized polylog-competitive algorithm on arbitrary n-point metrics. They also note some advice-complexity consequences. That is the concrete new piece: the specific derandomization that works for arbitrary lengths and composes without blowing up the runtime or the ratio beyond polylog in k. Prior work had either exponential configurations or implicit algorithms that were not efficient to run. The black-box framing is useful because it lets them inherit competitive ratios from existing HST results without re-proving everything from scratch. The approach looks clean on the high level and avoids obvious circularity. The soft spot is exactly the one the stress-test flags. The derandomization has to preserve the expected cost relative to OPT for every finite but arbitrarily long sequence. If the original randomized analysis relies on full independence at each step or on martingale properties that do not survive limited-independence or conditional-probabilities methods, the ratio could pick up hidden dependence on sequence length or on the particular HST embedding. The paper claims the framework handles this, but without an explicit small example or a machine-checked core lemma it is hard to be fully confident the composition stays clean. The distortion from the metric reduction is already known to be logarithmic, so that part is standard, but any extra factor from the derandomization would be fatal to the polylog claim. This is the kind of paper that belongs in a reading group for people who work on online algorithms or derandomization. A reader who already knows the k-server literature will get the most out of it; others will mainly see the high-level claim. It is worth a serious referee because the result would be a genuine computational advance if the preservation argument holds. I would send it to review rather than desk-reject.

Referee Report

2 major / 2 minor

Summary. The paper introduces a derandomization framework that converts any randomized k-server algorithm on hierarchically separated trees into one using only O(log k) random bits for arbitrary-length request sequences, thereby maintaining a distribution over polynomially many server configurations. Leveraging this black-box derandomization, the authors obtain the first polynomial-time randomized k-server algorithm on arbitrary n-point metrics with a polylogarithmic competitive ratio, with additional implications for advice complexity.

Significance. If the black-box derandomization preserves the competitive ratio exactly for arbitrary-length sequences and composes cleanly with existing metric-to-HST reductions, this would constitute a significant advance in online algorithms by delivering the first computationally efficient randomized polylog-competitive algorithm for the k-server problem on general metrics. The limited-randomness approach and black-box reuse of prior HST results are explicit strengths.

major comments (2)

[§4] §4 (derandomization framework): the claim that the O(log k)-bit derandomization (via conditional probabilities or limited independence) preserves the original randomized competitive ratio for every finite but arbitrarily long sequence must be shown explicitly; the analysis needs to rule out hidden dependence on sequence length when the original HST algorithm's potential or martingale arguments are instantiated with the reduced randomness.
[§5] §5 (application to arbitrary metrics): the composition of the derandomized HST algorithm with standard metric-to-HST embeddings must be verified to incur no extra multiplicative factors beyond the known distortion; the high-level statement that the polylog guarantee is maintained does not yet address whether the embedding depth or the polynomial configuration count interacts with the limited randomness to affect the ratio for long sequences.

minor comments (2)

[Abstract] The abstract should state the concrete polylogarithmic competitive ratio (e.g., O(log^2 k) or similar) achieved by the final algorithm.
Notation for the support size of the maintained distribution should be introduced once and used consistently when discussing polynomial versus exponential configurations.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major comments point by point below. Both concerns can be resolved by adding explicit proofs and verifications to the manuscript.

read point-by-point responses

Referee: [§4] §4 (derandomization framework): the claim that the O(log k)-bit derandomization (via conditional probabilities or limited independence) preserves the original randomized competitive ratio for every finite but arbitrarily long sequence must be shown explicitly; the analysis needs to rule out hidden dependence on sequence length when the original HST algorithm's potential or martingale arguments are instantiated with the reduced randomness.

Authors: We agree that the preservation must be shown explicitly. The derandomization in Section 4 applies the method of conditional probabilities (or limited independence) to the per-step decisions of the original HST algorithm. The underlying potential function is a martingale whose bounded differences depend only on the current configuration and the next request, not on the total sequence length. Consequently, the conditional-expectation argument yields the same competitive ratio for any finite prefix. We will insert a new lemma in §4 with a self-contained proof that rules out length-dependent error accumulation, confirming exact preservation of the ratio. revision: yes
Referee: [§5] §5 (application to arbitrary metrics): the composition of the derandomized HST algorithm with standard metric-to-HST embeddings must be verified to incur no extra multiplicative factors beyond the known distortion; the high-level statement that the polylog guarantee is maintained does not yet address whether the embedding depth or the polynomial configuration count interacts with the limited randomness to affect the ratio for long sequences.

Authors: The composition is black-box: a fixed metric-to-HST embedding (with its standard distortion) is applied once to the input metric, after which the derandomized algorithm runs on the resulting HST. Because the derandomized algorithm achieves exactly the same competitive ratio as the original randomized algorithm on any HST (as established in the revised §4), and because the polynomial-size support is independent of sequence length, no additional multiplicative factors arise from embedding depth or configuration count. We will add a formal composition theorem in §5 that spells out these facts and confirms the overall polylogarithmic guarantee. revision: yes

Circularity Check

0 steps flagged

No significant circularity; black-box derandomization is independent of target result

full rationale

The paper presents a new derandomization framework that converts any randomized k-server algorithm on HSTs into one using O(log k) bits while maintaining a polynomial-sized distribution and the original competitive ratio on arbitrary-length sequences. This is then composed with standard metric-to-HST reductions to obtain the polynomial-time polylog-competitive algorithm on general metrics. No equations or claims reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the framework is explicitly black-box and the composition is argued to preserve runtime and ratio without introducing length-dependent factors. The derivation chain is self-contained against external benchmarks for randomized HST algorithms and metric embeddings.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the existence of good randomized algorithms for HSTs (domain assumption) and on standard reductions from general metrics to HSTs (domain assumption). No free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption There exist randomized k-server algorithms on hierarchically separated trees with known competitive ratios that can serve as black-box input.
The derandomization framework is explicitly black-box and applies to any such algorithm.
domain assumption Standard metric embeddings or reductions from arbitrary metrics to HSTs preserve the necessary properties for the composition to remain polynomial-time and polylog-competitive.
The final claim on arbitrary metrics relies on composing the new derandomization with these prior reductions.

pith-pipeline@v0.9.0 · 5431 in / 1346 out tokens · 56410 ms · 2026-05-09T17:50:13.322850+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

70 extracted references · 1 canonical work pages

[1]

Journal of the ACM (JACM) , volume=

On the k-server conjecture , author=. Journal of the ACM (JACM) , volume=. 1995 , publisher=

1995
[2]

Theory of Computing Systems , volume=

On online algorithms with advice for the k-server problem , author=. Theory of Computing Systems , volume=. 2015 , publisher=

2015
[3]

Adamaszek, Anna and Czumaj, Artur and Englert, Matthias and R. An. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , pages=
[4]

30th Annual European Symposium on Algorithms (ESA 2022) , pages=

Online metric allocation and time-varying regularization , author=. 30th Annual European Symposium on Algorithms (ESA 2022) , pages=. 2022 , organization=

2022
[5]

Computer Science Review , volume=

The k-server problem , author=. Computer Science Review , volume=. 2009 , publisher=

2009
[6]

1999 , institution=

Hoard: A fast, scalable, and memory-efficient allocator for shared-memory multiprocessors , author=. 1999 , institution=

1999
[7]

Ptlbmalloc2: Reducing tlb shootdowns with high memory efficiency , author=. 2020 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom) , pages=. 2020 , organization=

2020
[8]

Journal of the ACM , volume=

Iceberg hashing: Optimizing many hash-table criteria at once , author=. Journal of the ACM , volume=. 2023 , publisher=

2023
[9]

k-server via multiscale entropic regularization , year =

S. k-server via multiscale entropic regularization , year =
[10]

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) , pages=

A scalable work function algorithm for the k-server problem , author=. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) , pages=. 2022 , organization=

2022
[11]

RAIRO-Theoretical Informatics and Applications , volume=

Advice complexity and barely random algorithms , author=. RAIRO-Theoretical Informatics and Applications , volume=. 2011 , publisher=

2011
[12]

Theoretical Computer Science , volume=

Shortest paths without a map , author=. Theoretical Computer Science , volume=
[13]

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , year=

Graph Searching with Predictions , author=. 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , year=

2023
[14]

Journal of the ACM (JACM) , volume=

An optimal on-line algorithm for metrical task system , author=. Journal of the ACM (JACM) , volume=
[15]

1993 , publisher=

Metrical Service System: Deterministic Strategies , author=. 1993 , publisher=

1993
[16]

SIAM Journal on Computing , volume=

Competitive algorithms for layered graph traversal , author=. SIAM Journal on Computing , volume=
[17]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing,

The Randomized k-Server Conjecture Is False! , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing,
[18]

63rd Annual Symposium on Foundations of Computer Science,

Shortest paths without a map, but with an entropic regularizer , author=. 63rd Annual Symposium on Foundations of Computer Science,
[19]

Online Metric Algorithms with Untrusted Predictions , journal =

Antonios Antoniadis and Christian Coester and Marek Eli. Online Metric Algorithms with Untrusted Predictions , journal =
[20]

Mixing Predictions for Online Metric Algorithms , booktitle =

Antonios Antoniadis and Christian Coester and Marek Eli. Mixing Predictions for Online Metric Algorithms , booktitle =
[21]

Lee , title =

Christian Coester and James R. Lee , title =. Theory Comput. , volume =
[22]

30th Annual European Symposium on Algorithms,

Nikhil Bansal and Christian Coester , title =. 30th Annual European Symposium on Algorithms,
[23]

Proceedings of the Thirtieth Annual

Niv Buchbinder and Anupam Gupta and Marco Molinaro and Joseph (Seffi) Naor , title =. Proceedings of the Thirtieth Annual
[24]

2018 , howpublished =

Niv Buchbinder and Anupam Gupta and Marco Molinaro and Joseph Naor , title =. 2018 , howpublished =

2018
[25]

Proceedings of the Twenty-Fifth Annual

Niv Buchbinder and Shahar Chen and Joseph Naor , title =. Proceedings of the Twenty-Fifth Annual
[26]

k-server via multiscale entropic regularization , booktitle =

S. k-server via multiscale entropic regularization , booktitle =
[27]

Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing , journal =

S. Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing , journal =
[28]

Discrete & Computational Geometry , volume=

On convex body chasing , author=. Discrete & Computational Geometry , volume=
[29]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,

Competitively chasing convex bodies , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,
[30]

Proceedings of the 2020

Mark Sellke , title =. Proceedings of the 2020

2020
[31]

Journal of the ACM (JACM) , volume=

Chasing convex bodies with linear competitive ratio , author=. Journal of the ACM (JACM) , volume=
[32]

Kowalski and Andrzej Pelc , title =

Pierre Fraigniaud and Leszek Gasieniec and Dariusz R. Kowalski and Andrzej Pelc , title =. Networks , volume =
[33]

Journal of Algorithms , volume=

Traversing layered graphs using the work function algorithm , author=. Journal of Algorithms , volume=
[34]

On traversing layered graphs on-line , author=. J. Algorithms , volume=
[35]

Automata, Languages, and Programming - 40th International Colloquium,

Dariusz Dereniowski and Yann Disser and Adrian Kosowski and Dominik Pajak and Przemyslaw Uznanski , title =. Automata, Languages, and Programming - 40th International Colloquium,
[36]

Siam Review , volume=

An optimal search , author=. Siam Review , volume=
[37]

SODA , year=

On traversing layered graphs on-line , author=. SODA , year=
[38]

15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , year=

Collective Tree Exploration via Potential Function Method , author=. 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , year=

2024
[39]

Lucas,. R. 1882 , publisher=
[40]

Nouvelles annales de math

Le probleme des labyrinthes , author=. Nouvelles annales de math
[41]

Theoretical Computer Science , volume=

Online graph exploration: New results on old and new algorithms , author=. Theoretical Computer Science , volume=
[42]

20th Annual Symposium on Foundations of Computer Science (sfcs 1979) , year=

Random walks, universal traversal sequences, and the complexity of maze problems , author=. 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) , year=

1979
[43]

Algorithmica , volume=

A distributed ant algorithm for efficiently patrolling a network , author=. Algorithmica , volume=
[44]

Information and computation , volume=

Searching in the plane , author=. Information and computation , volume=
[45]

Theoretical Computer Science , volume=

Constructing competitive tours from local information , author=. Theoretical Computer Science , volume=
[46]

31st Annual European Symposium on Algorithms (ESA) , year=

Exploration of Graphs with Excluded Minors , author=. 31st Annual European Symposium on Algorithms (ESA) , year=
[47]

arXiv preprint arXiv:2403.07748 , year=

Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph , author=. arXiv preprint arXiv:2403.07748 , year=

work page arXiv
[48]

Proceedings of the 51st Annual

Christian Coester and Elias Koutsoupias , title =. Proceedings of the 51st Annual
[49]

Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Breaking the k/log k Barrier in Collective Tree Exploration via Tree-Mining , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

2024
[50]

37th International Symposium on Distributed Computing (DISC 2023) , year=

Efficient Collaborative Tree Exploration with Breadth-First Depth-Next , author=. 37th International Symposium on Distributed Computing (DISC 2023) , year=

2023
[51]

Journal of the ACM (JACM) , volume=

A polylogarithmic-competitive algorithm for the k-server problem , author=. Journal of the ACM (JACM) , volume=. 2015 , publisher=

2015
[52]

International Colloquium on Automata, Languages, and Programming , pages=

On the advice complexity of the k-server problem , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2011 , organization=

2011
[53]

Journal of the ACM (JACM) , volume=

A primal-dual randomized algorithm for weighted paging , author=. Journal of the ACM (JACM) , volume=. 2012 , publisher=

2012
[54]

40th Annual Symposium on Foundations of Computer Science (Cat

Finely-competitive paging , author=. 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) , pages=. 1999 , organization=

1999
[55]

Journal of Algorithms , volume=

Competitive paging algorithms , author=. Journal of Algorithms , volume=. 1991 , publisher=

1991
[56]

Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=

Competitive algorithms for on-line problems , author=. Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=
[57]

Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

Randomized k-server on hierarchical binary trees , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=
[58]

Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures , pages=

Efficient online weighted multi-level paging , author=. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures , pages=
[59]

Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility) , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

2023
[60]

Theoretical Computer Science , volume=

Online computation with advice , author=. Theoretical Computer Science , volume=. 2011 , publisher=

2011
[61]

Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009

On the advice complexity of online problems , author=. Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings 20 , pages=. 2009 , organization=

2009
[62]

2016 , publisher=

Introduction to Online Computation , author=. 2016 , publisher=

2016
[63]

Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages=

A tight bound on approximating arbitrary metrics by tree metrics , author=. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages=
[64]

Algorithmica , volume=

Randomized competitive algorithms for the list update problem , author=. Algorithmica , volume=. 1994 , publisher=

1994
[65]

2005 , publisher=

Online computation and competitive analysis , author=. 2005 , publisher=

2005
[66]

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages=

Stochastic k-Server: How Should Uber Work? , author=. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages=. 2017 , organization=

2017
[67]

2012 , publisher=

Geometric algorithms and combinatorial optimization , author=. 2012 , publisher=

2012
[68]

Advances in Neural Information Processing Systems , volume=

Barely random algorithms and collective metrical task systems , author=. Advances in Neural Information Processing Systems , volume=
[69]

Grove , title =

Edward F. Grove , title =. Proceedings of the 23rd Annual
[70]

Yair Bartal and Eddie Grove , title =. J