Algorithms with Predictions
April 27, 2022 (GHC 8102)

Abstract: 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.