CSAIL Event Calendar: Previous Series

Near-Optimal Algorithms for Unique Games

Speaker: Moses Charikar , Princeton University
Date: April 4 2006
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Piotr Indyk, Massachusetts Institute of Technology

Unique games are constraint satisfaction problems -- a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between instances of unique games where almost all constraints are satisfiable and those where almost none are satisfiable. This has been the focus of a lot of recent attention since it has been shown to imply a number of hardness of approximation results for fundamental problems -- results that seem difficult to obtain by more standard complexity assumptions. Proving or refuting this conjecture is an important goal. Unique games are also of great algorithmic interest because they are representative of assignment problems over larger domains for which SDP rounding techniques have met with limited success.

We present significantly improved algorithms for unique games. Our algorithms are based on rounding a natural SDP relaxation for the problem. The main algorithmic contribution is a technique to extract a probability distribution over assignments from the SDP solution. Our results stop just short of disproving the Unique Games Conjecture, i.e. any improvement (beyond low order terms) would refute the conjecture.

This is joint work with Konstantin and Yury Makarychev, to appear in STOC 2006.

See other events that are part of Theory Colloquium Spring 2006

See other events happening in April 2006