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:
- Tensor decompositions: https://arxiv.org/abs/1311.3651
- Local Max-Cut: https://arxiv.org/abs/1610.04807
- Semi-random graph partitioning: https://arxiv.org/abs/1205.2234 or https://arxiv.org/abs/1406.5665
- Semi-random correlation clustering: https://arxiv.org/abs/1406.5667
- Semi-random independent set/ clique: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.6813
- Method-of-moments for Learning mixtures of Gaussians: https://arxiv.org/abs/1004.4223
- Isotropic PCA: https://arxiv.org/abs/0804.3575
Matrix Completion: https://arxiv.org/abs/1011.1518
Subspace clustering: https://statweb.stanford.edu/~candes/papers/RobustSubspaceClustering.pdf
High-dimensional Robust estimators: https://arxiv.org/abs/1604.06443 ,
Learning with untrusted data: https://arxiv.org/abs/1611.02315
You are also welcome to pick a different paper not in this list, after discussion with the instructor.
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.