Theory Lunch Seminar

Wednesday, November 13, 2019 - 12:00pm to 1:00pm


3305 Newell-Simon Hall


C.J. ARGUE, Ph.D. Student (Algorithms, Combinatorics and Optimization)

O(d)-competitive Convex Body Chasing

We study the problem of chasing convex bodies online: given a sequence of convex bodies K_t ⊆ R^d the algorithm must respond with points x_t ∈ K_t in an online fashion (i.e., x_t is chosen before K_{t+1} is revealed). The objective is to minimize the total distance between successive points in this sequence. Recently, Bubeck et al. (STOC 2019) gave a 2^{O(d)} -competitive algorithm for this problem. We give an algorithm that is O(min(d, √ d log T))-competitive for any sequence of length T.

Theory YouTube Channel

Event Website:

For More Information, Contact:


Seminar Series