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.

NEWS: With Sébastien Bubeck and Yuval Rabani, we refuted the randomized k-server 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 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 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 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.

Selected Publications

View AllManage publications

Activities

About Us

Back to Top