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:

• Algorithms and Complexity Theory

Interests

I'm interested in the design and theoretical analysis of algorithms, especially online algorithms and learning-augmented algorithms.

Students interested in doing a PhD in this area are welcome to email me.

NEWS: In joint work with Sébastien Bubeck and Yuval Rabani, we refuted the randomized k-server conjecture!

List of publications

Selected Publications

View AllManage 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

Activities

• Online Algorithms
• Randomised Algorithms
• Foundational Issues in Computational Learning