Talks
Fall 2017
Chasing Convex Bodies, from 1817 to 2018
Tuesday, December 11th, 2018, 2:00 pm–2:45 pm
Speaker:
Sébastien Bubeck (Microsoft Research)
A selector maps a set (in some set system) to an element in that set. In a metric space, Lipschitz selection is the problem of finding a selector that is Lipschitz with respect to the Hausdorff distance. A classical result is the existence of a Lipschitz selector for convex sets in Euclidean space. In this talk we will prove an *online* version of this classical result. This resolves the 1991 Friedman-Linial conjecture on convex body chasing.
Joint work with Yin Tat Lee, Yuanzhi Li, and Mark Sellke.