University of California, San Diego

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 |

- n / p for next / previous step
- o for overview
- m for menu, navigate menu by j / k or arrow keys

- Definitions, SOS for sparsest cut [slides] [video]
- Cheeger inequality as a degree-2 SOS [slides] [video]

- Max cut, Goemens-Williamson approximation algorithm, Feige-Schechtman integrality gap [slides] [video]
- Degree-2 SOS is optimal for max cut, assuming Unique Games Conjecture [slides] [video]
- Bayesian view of SOS [slides] [video]