TCS+ talk: Wednesday, March 22 — Christian Coester, University of Oxford

by plustcs

The next TCS+ talk will take place this coming March 22nd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC: check your timezone!). Christian Coester from University of Oxford will speak about “The Randomized k-Server Conjecture is False!” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: The randomized k-server conjecture, which had been open for over three decades, states that there exists an O(\log k)-competitive randomized algorithm for the k-server problem. In this talk, I will present our recent joint work with Sébastien Bubeck and Yuval Rabani, where we refute this conjecture by giving a lower bound of \Omega((\log k)^2). Our work also settles the competitive ratio of metrical task systems to be \Theta((\log n)^2) on the hardest metric spaces and \Theta(\log n) on the easiest metric spaces of n points. In particular, this yields the first improvement over the previous “coupon collector” lower bound since the introduction of the model in 1987.