Hi, Dear all
We will watch TCS+ talk tomorrow noon in 4310. Feel free to bring your lunch and join us. I created a spreadsheet for this semester.
https://docs.google.com/spreadsheets/d/12LdZiO-QU7kW7s1bS4zSzeVw_1N-2Fkuh260gdcwM-U/edit?usp=sharing
Students are encouraged to sign up to give an (informal) talk. Also, professors are certainly welcome to add a note if free food will be provided. Thanks.
Below is the information for tomorrow TCS+ talk.
Title: Chasing Convex Bodies
Speaker: Mark Sellke(Stanford)
Abstract: 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 length of the resulting path. Chasing convex bodies asks if 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.
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}