Semidefinite Programming — Approximation & Complexity

RWTH Aachen summer school on semidefinite optimization.

PDF

abstract

Lecture 1: Introduction & optimal rounding scheme for constraint satisfaction problems.

Lecture 2: Rounding hierarchies via global correlation & subexponential-time algorithm for Unique Games.

Lecture 3: Strong limitations of sum-of-squares methods.