Departmental Colloquium
Sami Davies
Northwestern University
Beyond Worst-case Analysis in Combinatorial Optimization
Abstract: In theoretical computer science, algorithm design and analysis is centered around worst-case optimization, where results focus on provable guarantees for how well an algorithm performs on any input. While worst-case analysis has led to deep structural insights into the problems at hand, we lose much of the nuance behind algorithm performance. Instances forcing the worst-case performance of the algorithm may not appear in practice, do not occur under reasonable assumptions on the distribution of problem inputs, or are avoidable if the algorithm has additional information about the input. In this talk, I'll discuss how we can bridge the gap between theory and practice by using frameworks that go beyond worst-case analysis in order to (1) develop a more complete theoretical understanding of a problem's difficulty, and (2) provide performance guarantees that are representative of what happens in practice. I'll demonstrate this by discussing work on the 3-Coloring problem and the Max Flow problem.
Tea will be served in SEO 300 after the talk.
Friday December 9, 2022 at 3:00 PM in 636 SEO