Worst-case analysis of algorithms is one of the cornerstones of theoretical computer science. At the same time, there is a growing discrepancy between the theoretical worst-case guarantees we can prove and the practical performance of algorithms observed on real inputs. This is particularly true in fields such as machine learning, SAT solving, and numerical optimization, where problems known to be hard in the worst-case are routinely solved to great effect on large real-world inputs.

In this seminar, we look at different strategies for dealing with this situation, and more fine-grained and nuanced techniques for the analysis of algorithms. The discussions will be mostly based on chapters of the recent book: "Beyond the Worst-Case Analysis of Algorithms" by T. Roughgarden, Cambridge University Press, 2020.

Requirement: ALP3/HA or similar algorithmic background, mathematical maturity.