Proofs, beliefs and algorithms through the lens of Sum of Squares

All lecture notes

Important announcements:

See also similar courses/seminars I (Boaz) taught in previous years

About the course

In this graduate seminar we will cover recent research on the use of mathematical programming for problems arising from optimization, machine learning, computational complexity and more, with a particular focus on the Parrilo-Lasserre “Sum of Squares” semidefinite programming hierarchy. We will discuss both lower and upper bounds, as well as how such mathematical programs give rise to a general theory of computational difficulty, computation vs. sample size tradeoffs, and computational analogs of Bayesian probabilities.

More concretely, we will touch some of the following topics:

However, this is a fast moving research area and our plans may change as new results, as well as new understandings of old results, come to light. The course will not require much mathematical background beyond so called “mathematical maturity”. However, some familiarity with notions such as convexity, linear programming duality, separation oracles, eigenvalues/eigenvectors and positive semidefiniteness, could be helpful.

See this blog post for a longer introduction to this course.

Catalog listings: MIT Harvard

Harvard/MIT class calendar:

Plan for lectures

See all lecture notes

Lecture no. Date/Place Lecture notes / pre-reading Notes / Homeworks Videos
1 9.9 at MIT pre-reading and exercises, introduction , Lecture 1: definitions Lecture 1 slides lecture 1 video
2 9.17 at Harvard Pre-reading: max-cut (html ) , Cheeger ( html ) , Grothendieck ( html ) lecture 2 video
3 Monday 5pm 9.26 at Harvard 60 Oxford St Room 330 Lower bounds for max cut ( html ), Lower bounds for CSPs ( html ), Raghavendra’s theorem ( html ) Lecture 3 video
4 9.30 at MIT ARV algorithm ( html ) Video
5 10.14 at Harvard (MD G125) Bayesian view (html ) General sos ( html ) Planted clique ( html ) video
6 10.21 at Harvard (MD G125) Symmetric SOS and flag algebras Lecture 6 video
7 10.28 at MIT Optimizing vectors over the sphere ( html ) Planted sparse vector problem ( html ) Tensor decomposition (html ) Dictionary learning ( html ) lecture 7 video
8 11.4 at MIT Quantum entanglement, log rank conjecture, and sos Lecture 8 video
9 Monday 5pm 11.14 at Harvard 60 Oxford St Room 330 sos and the unique games conjecture: a love-hate relationship ( html ) small set expansion problem ( html ) video
10 11.18 at Harvard (MD G125) On the optimality of sos ( html ) Digression to multiplicative weights ( html ) Lee-Raghavendra-Steurer Theorem ( html) lecture video
11 12.2 at MIT Beyond SOS? summary of course