CSAIL Event Calendar: Previous Series
Near-Optimal Algorithms for Unique Games
Speaker: Moses Charikar , Princeton University
Relevant URL: http://theory.csail.mit.edu/toc-seminars/
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.