| Day | Time | Topic |
|---|---|---|
| Jan 4 | 9-12 | Lecture 1 (David): definition of sum-of-squares (SOS); degree-2 SOS approximation for Sparsest Cut (Cheeger); deg-2 SOS lower bound for Sparsest Cut; improved approximation via deg-4 SOS (ARV) |
| Jan 4 | 12-2 | Lunch (provided) |
| Jan 4 | 2-5 | Lecture 2 (Boaz): deg-2 SOS approximation for Max Cut (GW); deg-2 SOS lower bound for Max Cut (Feige-Schechtman); UG-hardness of improved approximation (KKMO & Raghavendra’s theorem) |
| Jan 5 | 9-12 | Lecture 3 (David): SOS for machine learning: finding sparse vectors, tensor decomposition, dictionary learning |
| Jan 5 | 12-2 | Lunch (provided) |
| Jan 5 | 2-5 | Lecture 4 (David): Fast and practical algorithms from SOS |
| Jan 6 | 9-12 | Lecture 5 (Boaz): SOS lower bounds for random 3SAT and planted clique |
| Jan 6 | 12-2 | Lunch (provided) |
| Jan 6 | 2-5 | Lecture 6 (Boaz): Unique Games Conjecture; subexponential algorithm for Unique Games; small set expanders with many large eigenvalues (Short Code); subexponential algorithm for quantum separability |
| Jan 7 | 9-12 | Lecture 7 (David): On optimality of sum-of-squares and lower bounds for general semidefinite programming relaxations |
| Jan 7 | 12- | Quick lunch (provided) and excursion |