Theory Lunch Seminar
Speaker
MICHAEL MITZENMACHER
Professor of Computer Science
School of Engineering and Applied Sciences
Harvard University
When
-
Where
In Person and Virtual - ET
Description
In this talk, I will survey results in the emerging area of Algorithms with Predictions (aka learning augmented algorithms, or data driven algorithms), with a focus on my own work on filters and scheduling. These methods incorporate predictors -- which correspond naturally to machine learning “oracles” -- to adapt the algorithms' behavior to the properties of the input distribution. This can consequently improve their performance, such as the runtime, space, or quality of the solution. Ideally, the goal is to offer provable guarantees of improved performance when the predictions are good, while maintaining nearly identical worst-case or other performance guarantees when they are not. The field has recently boomed, with applications to classical streaming algorithms, online scheduling, clustering, and many other problems. The talk will discuss joint work with many, many others.
The Theory Lunch is sponsored in part by Smart Contract Research Forum.
In Person and Zoom Participation. See announcement.
CMU Theory Youtube channel.