# Christian Coester

Christian Coester

Associate Professor

Tutorial Fellow,

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

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 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.

• 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.
• 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. 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

• 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.

• 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.

• 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.