Previous month Previous day Next day Next month
See by year See by month See by week See Today Search Jump to month


Wednesday, March 12, 2014, 11:00am


A Vijayaraghavan flyerDr. Aravindan Vijayaraghavan

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




Location Tech Room L324
Wednesday, March 12, 2014 at 11:00am
Contact For more information contact Amanda Zarate at or 847-491-3451

  Download as iCal file