Course Syllabus

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 course, we will study systematically alternatives to worst-case analysis that nevertheless enable rigorous and robust guarantees on algorithm performance. The course will explore recent attempts using well-motivated non-worst-case approaches to bridge this disconnect between theory and practice, and also address some of the open research directions along these lines.  

Some of the topics that will be covered include:

1. Average-case analysis and planted models for NP-hard optimization problems
2. Semi-random models and robust probabilistic models.
3. Smoothed analysis
4. Implicit structural assumptions for clustering and partitioning
5. Sparse recovery problems, and incoherence assumptions
6. Success of iterative algorithms and heuristics.  


Suggestions for student paper presentations and projects: 

Smoothed Analysis:

  1. Tensor decompositions:
  2. Local Max-Cut:


Average-case analysis:

  1. Semi-random graph partitioning: or
  2. Semi-random correlation clustering:
  3. Semi-random independent set/ clique:


Average-case clustering:

  1. Method-of-moments for Learning mixtures of Gaussians:
  2. Isotropic PCA:



Matrix Completion:

Subspace clustering:

Dictionary Learning: and


High-dimensional Robust estimators: ,

Learning with untrusted data:

You are also welcome to pick a different paper not in this list, after discussion with the instructor. 


Course Summary:

Date Details Due