Christian Coester
Christian Coester
Room
427,
Wolfson Building,
Parks Road, Oxford OX1 3QD
United Kingdom
Interests
I'm interested in the design and theoretical analysis of algorithms, especially online algorithms and learningaugmented algorithms (see details below). I’m especially drawn to problems that are simple to state and hard to solve.
NEWS: With Sébastien Bubeck and Yuval Rabani, we refuted the randomized kserver conjecture (video) and won the STOC best paper award for it.
My research is theoretical: I design algorithms, prove that they are good (in a sense that can be made mathematically precise) or that no good algorithm exists for a particular problem. While working on specific problems, this can often lead to the development of new techniques with an impact on a variety of problems and our understanding of decision making under uncertainty more generally. If you have strong mathematical skills and are interested in doing a PhD with me, you are welcome to email me.
More details about my research:
 Online Algorithms: An online algorithm is an algorithm that receives its input over time and has to make decisions before future parts of the input are revealed. For example, the kserver problem (often called the "holy grail" problem of the field) is defined as follows: There are k "servers" located at points of a metric space. At each time step, a point of the space is requested, and an algorithm has to choose a server to move to the requested point. The goal is to minimise the total distance travelled.
Crucially, the algorithm has to make its decisions without knowledge of future requests. Due to this lack of information, it is impossible to make only decisions that remain optimal in hindsight. Instead, one aims to find algorithms whose competitive ratio (= the worstcase multiplicative overhead over the bestinhindsight solution) is as small as possible. Despite signficant attention that the kserver problem has attracted for several decades, it is still unknown what the best algorithm and competitive ratio are! In my prior work, we showed that even infinitely many extra servers do not make up for the information disadvantage (video), made some progress towards the deterministic kserver conjecture (video), and refuted the randomised kserver conjecture (video). Related problems I worked on include metric allocation (a problem that connects multiple fundamental online problems) and the ktaxi problem (see also this (video) and this). For the ktaxi problem, it is still unknown whether the optimal competitive ratio is infinite or finite, even for simple special cases such as 3 taxis in the Euclidean plane! A key goal of my research is to advance our still poor understanding of handling uncertainty through study of the central problems in the field and development of new algorithmic techniques. Some problems with several decades of history that we essentially resolved are metrical task systems and the online version of the shortest paths problem (see algorithm for metrical task systems, algorithm for online shortest paths (video), matching hardness results for both).  LearningAugmented Algorithms aka Algorithms with Predictions: This is a new field of research that has been growing rapidly in the last few years. Motivated by advances in machine learning, it circumvents the sometimes too pessimistic assumption of having no information about the future by assuming access to a prediction oracle. However, predictions provided by the oracle have no guarantee of being correct. Can we design algorithms that take advantage of predictions when they are good, while simultaneously avoiding to be misled even if predictions are highly erroneous? In many cases, it turns out the answer is Yes. We designed such algorithms for many problems involving metric spaces (video), dynamic power management (which generalizes the classical ski rental problem) (video), weighted paging, and we also studied the question of how to combine multiple predictors whose advice may be contradictory. Predictions also make sense to improve running time in offline problems: In joint work with Oxford undergraduate Xingjian Bai, we explored the fundamental problem of sorting with predictions (upcoming; to appear at NeurIPS’23). The field of learningaugmented algorithms is still young, with lots of scope for new projects that I’m happy to propose and supervise.
Biography
I received my PhD from Oxford in 2020. After postdoctoral stints at CWI (Amsterdam) and Tel Aviv University and a brief lectureship in Sheffield, I returned to Oxford as Associate Professor in 2022.
Selected Publications

Shortest Paths without a Map‚ but with an Entropic Regularizer
Sébastien Bubeck‚ Christian Coester and Yuval Rabani
In 63nd IEEE Annual Symposium on Foundations of Computer Science (FOCS). 2022.
Details about Shortest Paths without a Map‚ but with an Entropic Regularizer  BibTeX data for Shortest Paths without a Map‚ but with an Entropic Regularizer  Download (pdf) of Shortest Paths without a Map‚ but with an Entropic Regularizer

Learning−Augmented Weighted Paging
Nikhil Bansal‚ Christian Coester‚ Ravi Kumar‚ Manish Purohit and Erik Vee
In Proceedings of the 2022 ACM−SIAM Symposium on Discrete Algorithms (SODA). 2022.
Details about Learning−Augmented Weighted Paging  BibTeX data for Learning−Augmented Weighted Paging  Download (pdf) of Learning−Augmented Weighted Paging

The Online k−Taxi Problem
Christian Coester and Elias Koutsoupias
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). 2019.
Details about The Online k−Taxi Problem  BibTeX data for The Online k−Taxi Problem  Download (pdf) of The Online k−Taxi Problem