6.S898 Proofs, beliefs and algorithms through the lens of Sum of Squares


Units: 3-0-9
Prerequisites: Main requirements are a combination of algorithms (6.046/18.410 or equivalent), probability (6.041 or 18.600), discrete math (6.042 or 18.200), and/or mathematical optimization (6.251/6.255 or equivalent).
Instructors: Boaz Barak (Harvard CS),  Pablo A. Parrilo (MIT EECS)
Schedule:  Fridays 10-1, room 5-234
This graduate seminar 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 "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.  The course location will alternate between Harvard and MIT.