In this course will survey recent topics relating to semidefinite programming. Semidefinite programming is the largest class of optimization problems that we can solve efficiently and it has a variety of applications is areas such as combinatorial optimization, quantum cmputing, graph theory, approximation algorithms, geometry and algebraic geometry.

In this course we will start with the basics of SDPs and build towards more recent developments, with a particular focus on the Parillo-Lasserre framework for sums of squares relaxations and its applications to approximation algorithms and machine learning. We will also explore various techniques for proving what the sum of squares relaxations can and cannot do. We will also see connection to various fascinating areas of mathematics such as probability and measure concentration, geometry, information theory, spectral theory, polynomials and Fourier analysis.

For the first part of course, we will cover some of the cornerstone applications of semidefinite programming in Theoretical Computer Science: the Goemans-Williamson algorithm for MAX-CUT, Grothendieck's inequality, and time permitting, the Arora-Rao-Vazirani algorithm for SPARSEST-CUT.

For the second part of the course, we will introduce the powerful sums of squares (SOS) framework of Parillo & Lasserre which yields a hierarchy of successively more exact relaxations for a wide variety of optimization problems. We will start by showing the basic convergence results for this hierarchy, how to model the sums of squares relaxations as semidefinite programs, together with some first order properties and limitations of these hierarchies. As a first major application, we will present the hierarchy based algorithm of Raghavendra and Tan for the MAX-BISECTION problem in detail.

For the last part of the course, we will study advanced applications of the SOS hierarchy as well as their limitations. Tentative topics include: algorithms for the dictionary learning problem and low rank tensor decompositions, SOS lower bounds for classical constraint satisfaction problems as well as average case problems such as planted clique, algorithms discrepancy minimization, the unique games conjecture, lower bounds on the size of semidefinite extended formulations for classical combinatorial polytopes.