Christian Coester

Christian Coester is an Associate Professor of Computer Science at the University of Oxford and a Tutorial Fellow at St Anne's College. His research focuses on theoretical computer science, particularly in the design and analysis of algorithms for problems involving uncertainty and incomplete information.

His primary research areas include:

• Online algorithms, with groundbreaking work on the k-server problem (including refuting the randomized k-server conjecture, which earned the STOC 2023 Best Paper Award)
• Learning-augmented algorithms (algorithms with predictions) that leverage machine learning predictions while maintaining robustness guarantees
• Fundamental problems such as the k-taxi problem, metrical task systems, and online shortest paths

Coester's theoretical work aims to develop algorithms with provable performance guarantees, particularly focusing on competitive ratios that measure worst-case performance against optimal offline solutions. His research often addresses problems that are 'simple to state and hard to solve,' leading to techniques with broad applicability across theoretical computer science.

His publications span top venues including STOC, FOCS, SODA, and ICML, showing consistent contributions to both classical online algorithms and the emerging field of learning-augmented algorithms. The publications reveal a strong focus on metric spaces, competitive analysis, and the integration of prediction models into traditional algorithmic frameworks.

Coester has received significant recognition including the STOC 2023 Best Paper Award and a substantial ERC Starting Grant (EUR 1.5M) for 'Challenges in Competitive Online Optimisation' (2025-2029). He actively supervises PhD students and welcomes inquiries from mathematically skilled candidates interested in theoretical computer science.