In fall 2024 we hosted a seminar on the Sum of Squares method. The program was prepared in collaboration with Chris Jones and Tommaso d'Orsi. This webpage is used to make lecture notes available to the public. 

We wish to dedicate this seminar to the memory of our friend and colleague Luca Trevisan.

Lecture 1 (September 20th): Introduction to The Sum of Squares Method
Speaker: Chris Jones
Lecture Notes: PDF

Lecture 2 (September 27th): Pseudodistributions and the Lasserre Hierarchy
Speaker: Marek Elias
Lecture Notes: PDF

Lecture 3 (October 4th): Clustering Mixtures of Gaussians
Speaker: Tommaso d'Orsi
Lecture Notes: PDF (Video Recording)

Lecture 4 (October 11th): Global Correlation Rounding
Speaker: Lucas Pesenti
Lecture Notes: PDF (Video Recording)

Lecture 5 (October 18th): Clustering Mixtures of Gaussians II
Speaker: Tommaso d'Orsi
Lecture Notes: PDF (Video Recording)

Lecture 6 (October 25th): Unique Games and Hardness of Approximation
Speaker: Siu On Chan
Lecture Notes: PDF (Video Recording)

Lecture 7 (November 8th): Integrality Gap and Dictator Test
Speaker: Siu On Chan
Lecture Notes: PDF (Video Recording)

Lecture 8 (November 15th): Approximation Algorithms for Graph Expansion
Speaker: Jiyu Zhang
Lecture Notes: PDF (Video Recording)

Lecture 9 (November 22nd): Approximation Algorithms for Graph Expansion II
Speaker: Jiyu Zhang
Lecture Notes: PDF (Video Recording)

Lecture 10 (November 29th): Grothendieck Inequality
Speaker: Giulio Malavolta
Lecture Notes: PDF (Video Recording)

Lecture 11 (December 13th): Tsirelson's Theorem
Speaker: Giulio Malavolta
Lecture Notes: PDF (Video Recording)