April 28, 2023

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.