These are powerpoint slides corresponding to the whiteboard
lectures I gave for a sum of squares seminar 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 |