10 citations · 17 across the 14 of their papers we have counts for
22 papers
The -server conjecture is true
Christian Coester, Elias Koutsoupias, Marek Zbysiński
The -server conjecture states that a deterministic online algorithm can achieve competitive ratio on every metric space. We prove the conjecture. Specifically, we show that…
Early science acceleration experiments with GPT-5
Sébastien Bubeck, Christian Coester, Ronen Eldan +11
AI models like GPT-5 are an increasingly valuable tool for scientists, but many remain unaware of the capabilities of frontier AI. We present a collection of short case studies in…
Online 3-Taxi on General Metrics
Christian Coester, Tze-Yang Poon
The online -taxi problem, introduced in 1990 by Fiat, Rabani and Ravid, is a generalization of the -server problem where taxis must serve a sequence of requests in a metr…
Smoothed Analysis of Online Metric Problems
Christian Coester, Jack Umenberger
We study three classical online problems -- -server, -taxi, and chasing size sets -- through a lens of smoothed analysis. Our setting allows request locations to be adver…
Learning-Augmented Priority Queues
Ziyad Benomar, Christian Coester
Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements…
Mixing predictions for online metric algorithms
Antonios Antoniadis, Christian Coester, Marek Eliáš +2
A major technique in learning-augmented online algorithms is combining multiple algorithms or predictors. Since the performance of each predictor may vary over time, it is desirabl…
The Randomized -Server Conjecture is False!
Sébastien Bubeck, Christian Coester, Yuval Rabani
We prove a few new lower bounds on the randomized competitive ratio for the -server problem and other related problems, resolving some long-standing conjectures. In particular,…
Competitive Algorithms for Block-Aware Caching
Christian Coester, Roie Levin, Joseph +2
We study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evictin…
Shortest Paths without a Map, but with an Entropic Regularizer
Sébastien Bubeck, Christian Coester, Yuval Rabani
In a 1989 paper titled "shortest paths without a map", Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while att…
Online metric allocation
Nikhil Bansal, Christian Coester
We introduce a natural online allocation problem that connects several of the most fundamental problems in online optimization. Let be an -point metric space. Consider a res…
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
Antonios Antoniadis, Christian Coester, Marek Eliáš +2
We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between…
Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle
Christian Coester, Elias Koutsoupias
The -server conjecture, first posed by Manasse, McGeoch and Sleator in 1988, states that a -competitive deterministic algorithm for the -server problem exists. It is conje…
Online -Taxi via Double Coverage and Time-Reverse Primal-Dual
Niv Buchbinder, Christian Coester, Joseph +1
We consider the online -taxi problem, a generalization of the -server problem, in which servers are located in a metric space. A sequence of requests is revealed one by o…
Learning-Augmented Weighted Paging
Nikhil Bansal, Christian Coester, Ravi Kumar +2
We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The mo…
Metrical Service Systems with Transformations
Sébastien Bubeck, Niv Buchbinder, Christian Coester +1
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which…
Online metric algorithms with untrusted predictions
Antonios Antoniadis, Christian Coester, Marek Elias +2
Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision…
Unbounded lower bound for k-server against weak adversaries
Marcin Bienkowski, Jarosław Byrka, Christian Coester +1
We study the resource augmented version of the -server problem, also known as the -server problem against weak adversaries or the -server problem. In this setting, an…
Pure entropic regularization for metrical task systems
Christian Coester, James R. Lee
We show that on every -point HST metric, there is a randomized online algorithm for metrical task systems (MTS) that is -competitive for service costs and -competi…
Better Bounds for Online Line Chasing
Marcin Bienkowski, Jarosław Byrka, Marek Chrobak +3
We study online competitive algorithms for the \emph{line chasing problem} in Euclidean spaces , where the input consists of an initial point and a sequence of line…
The Online -Taxi Problem
Christian Coester, Elias Koutsoupias
We consider the online -taxi problem, a generalization of the -server problem, in which taxis serve a sequence of requests in a metric space. A request consists of two po…
Streaming Rewriting Games: Winning Strategies and Complexity
Christian Coester, Thomas Schwentick, Martin Schuster
Context-free games on strings are two-player rewriting games based on a set of production rules and a regular target language. In each round, the first player selects a position of…
The Infinite Server Problem
Christian Coester, Elias Koutsoupias, Philip Lazos
We study a variant of the -server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a s…