Skip to main content

Christian Coester and co-authors win Best Paper at STOC

Posted:

Congratulations to Christian Coester, whose co-authored paper The Randomized k-Server Conjecture is False! has won a Best Paper award at STOC 2023: 55th Annual ACM Symposium on Theory of Computing.

The paper (co-written with Sebastien Bubeck of Microsoft Research and Yuval Rabani of the Hebrew University) refutes the ‘randomized k-server conjecture’, which had been a central open question in the field of online algorithms for several decades. In the k-server problem, there are k mobile servers located in some space. One by one, points of the space are requested, and each time an algorithm has to select a server to move to that point – without knowledge of future requests. It was conjectured that a randomized algorithm exists that is efficient, in the sense that the distance travelled by its servers is at most a log(k) factor larger than the optimum in hindsight (when all requests are revealed). The paper shows that no such algorithm can exist. At a high level, this means that the lack of information is costlier than previously believed.

Christian gave a talk about this paper for the online seminar series TCS+, which you can watch here: https://www.youtube.com/watch?v=BYnRaIym3LI