Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 10/10 - Mark Sellke

Neha Gupta nehgupta at
Wed Oct 9 10:21:05 PDT 2019

Hi everyone,

This Thursday at theory lunch, Mark will tell us about chasing convex bodies problem (title and abstract below). As usual, please join us from noon - 1pm in Gates 463A.


Chasing Convex Bodies

I will explain our recent understanding of the chasing convex bodies problem posed by Friedman and Linial in 1991. In this problem, an online player receives a request sequence K_1,...,K_T of convex sets in d dimensional space and moves his position online into each requested set. The player's movement cost is the total length of the resulting path. The question: is there an online algorithm with cost competitive against the offline optimal path? This is both an challenging metrical task system and (equivalent to) a competitive analysis view on online convex optimization.

This problem was open for d>2 until last year but has recently been solved twice. The first solution gives a 2^{O(d)} competitive algorithm while the second gives a nearly optimal min(d,sqrt(d*log(T))) competitive algorithm for T requests. The latter result is based on the Steiner point, which is the exact optimal solution to a related geometric problem called Lipschitz selection and dates from 1840. In the talk, I will briefly outline the first solution and fully explain the second.

Partially based on joint works with Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, and Yuanzhi Li.



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list