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 |