Winter school on Sum of Squares algorithm

The Sum of Squares (SOS) algorithm (Parrilo '00, Lasserre'01) yields a unified approach for many problems arising in optimization, control, machine learning, computational complexity and more. The winter school will provide an extended introduction to this algorithm and its applications. We will cover both the basic results in this area as well as some exciting recent results. A tentative list of topics that we plan to touch upon is:

• Upper and lower bounds for various average case problems, including random constraint satisfaction, planted clique, and problems arising from machine learning such as tensor decomposition, sparse coding, and more.
• Speeding up the Sum of Squares algorithm to obtain practically efficient algorithms.
• Relation to Khot’s Unique Games Conjecture (UGC) and the SOS approach to refuting the UGC.
• Can SOS be optimal algorithm in some settings? What kind of implications could such optimality entail?
• Semidefinite extension complexity, relations to communication complexity.
• Relation to statistical physics, and algorithms such as belief propagation and survey propagation.
• Relation to quantum information theory, quantum entanglement, and the log rank conjecture.
• SOS and extremal combinatorics via Razborov’s flag algebras.

For details see the schedule (including slides and videos)

Accommodation:

Registration:

Registration is free. Please register in advance, so that we can arrange accordingly.

---

Questions? please email Shachar Lovett.