Re: [theory students] [theory faculty] Theory lunch and TCS+ talk noon TODAY: k-server via multiscale entropic regularization

[Benjamin Miller <bmiller@xxxxxxxxxxx>]

Hi all,

Just a reminder this is happening today! CS 3310 at noon. Bring your lunch!

Benjamin

On Tue, Dec 12, 2017 at 10:33 AM, Shuchi Chawla <shuchi@xxxxxxxxxxx> wrote:

To follow up on Ben's message, this year seems to have been the year of big algorithmic breakthroughs. A few weeks back we heard about the new constant factor approximation for ATSP. Tomorrow's talk will likewise talk about the (almost) resolution of a major conjecture.Â

The k-server conjecture states that there exists an O(log k) competitive online algorithm for the k-server problem. This has been the most important open problem in online algorithms for 25 years. James Lee recently announced a polylog(k) competitive algorithm for general metrics. SeeÂhttps://homes.cs.washington.edu/~jrl/papers/fusion.pdf. Competitive ratios of all previously known algorithms had either a polynomial dependence on k, or a dependence on the size of the instance, n. The topic of tomorrow's talk is a key step in James' eventual proof.

Shuchi

On Tue, Dec 12, 2017 at 11:59 AM Benjamin Miller <bmiller@xxxxxxxxxxx> wrote:

Hi all,

We'll have theory lunch during the TCS+ talk tomorrow, starting at noon in CS 3310. Sebastien Bubeck from MSR will be presenting his breakthrough (along withÂMichael Cohen, James Lee, Yin Tat Lee, and Aleksander Madry) on the k-server problem. It should be a good talk!

As usual, bring your own lunch. I'll see you there.

Benjamin

-------------------------------------------------------------------------------
This message was sent to the mailing list for the theory faculty at the
Computer Sciences Department of the University of Wisconsin in Madison.