Semidefinite Programming Hierarchies and the Unique Games Conjecture

Algorithmic Frontiers Workshop at EPFL, SIAM Discrete Mathematics Meeting.

PDF

abstract

A survey of recent results about the power of semidefinite programming hierarchies in the context of the Unique Games Conjecture. In the past decade, this conjecture has emerged as a promising approach towards a unified resolution of many central open problems in the theory of approximation algorithms. It posits the hardness of a certain constraint satisfaction problem. We will discuss both upper and lower bounds on the complexity of this problem through the lens of semidefinite programming hierarchies.