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 |