Officially we meet on Mondays and Thursdays from 10:00 to 11:30. In practice we will begin at 10:15 sharp and go until around 11:45 with a short break in the middle. On Mondays the seminar will be in room 4523. On Thursdays the seminar will be in room 1537 until October 12. From October 19 onwards, the seminar will be in room 4523 on Thursdays as well.
| Date | Lecture | ||
|---|---|---|---|
| Sep 4 | Lecture 1: Introduction to the Sum of Squares Hierarchy | ||
| Sep 7 | Lecture 2: Linear Programming and Duality | ||
| Sep 11 | Lecture 3: Semidefinite Programming | ||
| Sep 14 | Lecture 4: Goemans-Williamson | ||
| Sep 18 | Lecture 5: SOS Proofs and the Motzkin Polynomial | ||
| Sep 21 | Lecture 6: Linear Programming for Sparsest Cut | ||
| Sep 25 | Lecture 7: Arora-Rao-Vazirani | ||
| Sep 28 | Lecture 8: SOS Lower Bound for 3-XOR | ||
| Oct 2 | Lecture 9: SOS Lower Bound for Knapsack | ||
| Oct 5 | No lecture: one lecture break | ||
| Oct 9 | Lecture 10: Gap Reductions and SOS | ||
| Oct 12 | Lecture 11: Graph Matrices | ||
| Oct 16 | No lecture: FOCS | ||
| Oct 19 | Lecture 12: SOS Lower Bounds for Planted Clique Part I | ||
| Oct 23 | Lecture 13: SOS Lower Bounds for Planted Clique Part II | ||
| Oct 26 | Lecture 14: Planted Sparse Vector | ||
| Oct 30 | Lecture 15: Exact Tensor Completion | ||
| Nov 2 | No lecture: STOC deadline approaching | ||
| Nov 6 | No lecture | ||
| Nov 9 | Kilian Risse: Optimal inapproximability results for max-cut and other 2-variable csps? | ||
| Nov 13 | No lecture | ||
| Nov 16 | No lecture | ||
| Nov 20 | Joseph Swernofsky: Hypercontractivity, Sum-of-Squares Proofs, and their Applications | ||
| Nov 23 | Jan Elffers: SOS is not obviously automatizable, even approximately (slides due to Jan) | ||
| Nov 27 | Jan Van Den Brand: Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors | ||
| Nov 30 | Susanna Figueiredo De Rezende: Sum of squares lower bounds for refuting any CSP | ||
| Dec 4 and first half of Dec 7 | Lecture 16: Subexponential time algorithm for unique games and small set expansion | ||
| Second half of Dec 7 | Course summary with emphasis on open problems |
Note: Lectures will be given as blackboard talks. Lecture slides are subject to change.