Wednesday, March 12, 2014, 11:00am
Simons Postdoctoral Fellow, CS Dept, Carnegie Mellon University
"Beyond Worst Case Analysis in Algorithm Design"
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.
Bio: Dr. Aravindan Vijayaraghavan is a Simons Postdoctoral Fellow in the Department of Computer Science at Carnegie Mellon University. He received his PhD (in 2012) from Princeton University under the supervision of Prof.Moses Charikar. His research interests are in designing algorithms with provable guarantees for problems in combinatorial optimization and machine learning.
Hosted by: EECS Prof. Ming-Yang Kao