Theory Seminar: Sergei Vassilvitskii

The speaker for the theory seminar on 4/28 is Sergei Vassilvitskii from Google. As usual, the talk will take place at 1pm in Levine 307.

Title: New advances in ‘Algorithms with Predictions’

Abstract: The theoretical study of algorithms and data structures has been bolstered by worst-case analysis, where we prove bounds on the running time, space, approximation ratio, competitive ratio, or other measure that holds even in the worst case. In practice, however, we often do not face worst-case scenarios, and the question arises of how we can tune our algorithms to work even better on the kinds of instances we are likely to see, while ideally keeping a rigorous formal framework similar to what we have developed through worst-case analysis.

We contribute to the burgeoning recent trend that develops algorithms parameterized by additional parameters which capture “the kinds of instances we are likely to see,” and obtains a finer grained analysis of algorithms’ performance. We will give new results for three different problems showcasing the breadth of this approach – single source shortest paths, secretary problems, and differentially private quantile estimation.

Based on work with Kareem Amin, Travis Dick, Paul Duetting, Misha Khodak, Silvio Lattanzi, Renato Paes Leme, and Ola Svensson.