On the Power of Semidefinite Programming Hierarchies

with Prasad Raghavendra. STOC 2012 Workshop on Unique Games Conjecture.

PDF

abstract

The study of the unique games conjecture (UGC) has led to deeper understanding of the power of semidefinite programs (SDP) — in form of new algorithms, integrality gap constructions and tight hardness results. In this tutorial, we will survey some of the recent advances in approximation algorithms based on SDP hierarchies, fuelled by the UGC. The talk will include a gentle algorithmic introduction to SDP hierarchies and their limits.

We will discuss a general technique toward rounding SDP hierarchies, with application to subexponential time algorithm for unique games and related problems. This general technique has found applications to other approximation problems such as MaxBisection. The talk will explore recent work on relations between SDP hierarchies and the spectrum of the input graph and their applications to algorithms and lower bounds. We will also show why algorithms of this general type must indeed take (almost) subexponential time for unique games, and discuss how sum-of-squares type arguments might help to go beyond these limitations.