Winter school on Sum of Squares algorithm

January 4-7, 2017
University of California, San Diego

Location: CSE building (EBU3B), room 1202

Speakers: Boaz Barak (Harvard) and David Steurer (Cornell)


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

Slides and videos:

Instructions for navigating the slides: Lecture 1: Lecture 2: Lecture 3: Lecture 4: Lecture 5: Lecture 6: Lecture 7: