Abstract

In these introductory lectures we will present a unified introduction to Semidefinite Programming hierarchies and Sum of Squares techniques for continuous/discrete optimization, highlighting their many different and complementary interpretations (Lagrangian/algebraic duality, geometric embeddings, proof systems, probabilistic, etc). We will concisely summarize the state of the art in both positive and negative results (e.g., planted clique, tensor completion, constraint satisfaction), as well as current algorithmic approaches.

The first session of this mini course will take place on Monday, August 21 from 2:00 - 3:00 PM; the second session of this mini course will take place on Monday, August 21 from 3:30 - 4:30 PM; the third session of this mini course will take place on Wednesday, August 23 from 9:30 - 10:30 AM; and the fourth session of this mini course will take place on Wednesday, August 23 from 11:00 AM - 12:00 PM.

Video Recording