These are the powerpoint slides corresponding to
the whiteboard lectures I gave for my sum of squares seminar at
KTH in fall 2017.
Lecture 1: Introduction to the Sum of
Squares Hierarchy
Lecture 2: Linear Programming
and Duality
Lecture 3: Semidefinite
Programming
Lecture 4: Goemans-Williamson
Lecture 5: SOS Proofs and
the Motzkin Polynomial
Lecture 6: Linear
Programming and Sparsest Cut
Lecture 7: Arora-Rao-Vazirani
Lecture 8: SOS Lower Bound for
3-XOR
Lecture 9: SOS Lower Bound for
Knapsack
Lecture 10: Gap Reductions and
SOS
Lecture 11: Graph Matrices
Lecture 12: SOS
Lower Bounds for Planted Clique Part I
Lecture 13: SOS
Lower Bounds for Planted Clique Part II
Lecture 14: Planted Sparse
Vector
Lecture 15: Exact Tensor
Completion
Lecture 16:
Subexponential Time Algorithm for Unique Games and Small Set
Expansion