Skip to main content
University of Oxford Department of Computer Science
  Contact Us     Search  
  1. Home
  2. About Us
  3. People
  4. Faculty
  5. Christian Coester

Christian Coester

Personal photo - Christian Coester

Christian Coester

Associate Professor

Tutorial Fellow, St Anne's College

E: christian.coester(a)cs.ox.ac.uk

Room 427, Wolfson Building, Parks Road, Oxford OX1 3QD
United Kingdom

Themes:

Interests

I'm interested in the design and theoretical analysis of algorithms, especially online algorithms and learning-augmented algorithms (see details below). I’m especially drawn to problems that are simple to state and hard to solve.

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 (such as in our refutation of the randomized k-server conjecture (video), which won the STOC 2023 Best Paper Award). 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. I am also currently looking for a postdoc.

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 k-server 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 worst-case multiplicative overhead over the best-in-hindsight solution) is as small as possible. Despite signficant attention that the k-server 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 k-server conjecture (video), and refuted the randomised k-server conjecture (video). Related problems I worked on include metric allocation (a problem that connects multiple fundamental online problems) and the k-taxi problem (see also this (video) and this). For the k-taxi 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).
  • Learning-Augmented 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 can also help to improve running time and comparison complexity, as we showed for sorting and priority queues. The field of learning-augmented algorithms is still young, with lots of scope for new projects that I’m happy to propose and supervise.

List of publications

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.

My research is funded by an ERC Starting Grant: Challenges in Competitive Online Optimisation, 2025-2029, EUR 1.5M.

Selected Publications

View AllManage publications

Activities

Projects

About Us

Back to Top