Graduate
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
Description
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.
