Computer Science/Discrete Mathematics Seminar I

Since the late 19^th century, mathematicians have realized the importance and generality of selection problems: given a collection of sets, select an element in each set, possibly in a ``nice” way.  Of particular importance in computer science is the scenario where the ground set is a metric space, in which case it is natural to ask for *Lipschitz* selection (with Hausdorff distance between sets). In this talk, I will describe a far-reaching extension of this classical Lipschitz selection problem to an *online* setting, where sets are streaming to the selector.  I will show how Riemannian gradient descent (aka mirror descent) can be used to approach this type of problems.  I will illustrate the power of the framework by solving a long-standing problem in online shortest path known as layered graph traversal (introduced by Papadimitriou and Yannakakis in 1989).