Semidefinite Programming Hierarchies and the Unique Games Conjecture
Speaker: Boaz Barak , MSR New England and Princeton U.
Date: April 26 2011
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, be@csail.mit.edu
Relevant URL: Semidefinite programs (SDP's) are a form of convex relaxation
that found many uses in algorithms. In the early 1990's several
researchers proposed stronger forms of SDP's known as *SDP
hierarchies*. In this talk I will present a new way of taking
algorithmic advantages of these hierarchies to solve constraint-
satisfaction problems for 2-variable constraints such as
LABEL-COVER, MAX-CUT, and UNIQUE-GAMES.
Specifically, we show SDP-hiearchy based algorithms that
provides arbitrarily good approximation to all these problems
in time poly(n)*exp(r), where r is the number of eigenvalues in the
constraintgraph larger than some constant threshold (depending on the
accuracy parameter and type of constraint used).
In particular we get quasipolynomial algorithms for instances whose
constraint graph is *hypercontractive*, as is the case for all the
canonical "hard instances" for MAX-CUT and UNIQUE-GAMES. This gives
more reason to consider relatively low (i.e. polylogarithmic) levels
of SDP hierarchy as candidate algorithms for refuting Khot's Unique
Games Conjecture.
Joint work with Prasad Raghavendra and David Steurer.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in April 2011
