Large 00004

Semidefinite Programming Hierarchies and the Unique Games Conjecture

David Steurer

Recorded 14 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute

Abstract

We survey recent results about semidefinite programming (SDP) hierarchies in the context of the Unique Games Conjecture. This conjecture has emerged as a unifying approach towards settling many central open problems in the theory of approximation algorithms. It posits the hardness of a certain constraint satisfaction problem, called Unique Games.

We explain recent approximation algorithms based on SDP hierarchies that approximate this problem in subexponential time. This result relies on a connection between the spectrum of graphs and the expansion of small sets. Recent constructions show that algorithms based on this connection cannot run much faster than in subexponential time. Finally, we discuss evidence how stronger SDP hierarchies based on sum-of-squares proofs might be able to go beyond this limitation.

Watched 6966 times.

 Watch