Leveraging ML Predictions for Beyond-Worst-Case Algorithm Design
Traditionally, we measure the performance of algorithms in the worst-case model. That is, the algorithms are designed to perform well against an adversarial input sequence. While the worst-case paradigm provides extremely strong guarantees, it can often be too pessimistic compared to the empirical performance on typical datasets. This talk is about a growing line of work that incorporates machine learned predictions to break through worst-case running time barriers.
Shikha Singh is an assistant professor in our CS department, who typically teaches courses such as CS 134, CS 256 and C357. She has been on leave from teaching to focus on research, which in the area of algorithms and data structures and algorithmic game theory.