Beyond Worst Case Analysis in Algorithm Design: Aravindan Vijayaraghavan, CMU (CS Colloquium)

Starts:
11:00 am on Monday, February 24, 2014
Ends:
12:15 pm on Monday, February 24, 2014
Location:
Hariri Institute
Abstract: For many real world computational tasks there is a significant gap between our theoretical and practical understanding. While the theory of NP-completeness and worst case analysis tells us that many interesting computational problems are NP-hard in the worst case, practitioners in areas like machine learning and computer vision have made significant progress in solving such theoretically hard problems. Bridging this gap is a significant challenge for modern day theoretical computer science. In this talk, I will discuss three paradigms that go beyond traditional worst-case analysis in our search for algorithms with better provable guarantees: (realistic) average-case analysis, smoothed analysis and instance stability. I will use these paradigms to show significantly better guarantees for two classes of problems in very different domains: (a) graph partitioning, and (b) unsupervised learning of probabilistic models.