Sum-of-Squares: proofs, beliefs, and algorithms

Monday 1:30pm–4:20pm, Friend Center 108, Princeton University
piazza (sign up using this google form)

Boaz Barak is teaching a sister seminar in parallel at Harvard/MIT.


optimization landscape that is easy for sum-of-squares but hard for local search algorithms  

course description

In this graduate seminar we cover recent research results on the use of mathematical programming for problems arising from optimization, machine learning, computational complexity and more. A particular focus is on the Parrilo–Lasserre “Sum of Squares” semidefinite programming hierarchy. We 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.