Subexponential Algorithms for Unique Games and Related Problems
Speaker: David Steurer , Princeton University
Date: May 4 2010
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT
Contact: Be, 3-6098, imbe@mit.edu
Relevant URL: We give a subexponential time approximation algorithm for the Unique Games
problem: Given a Unique Games instance with alphabet size k such that a
1-epspilon^6 fraction of the constraints can be satisfied, our algorithm finds
in time exp(k*n^epsilon) an assignment that satisfies a 1-epsilon fraction of
the constraints.
We also obtain subexponential algorithms with similar approximation guarantees
for Small-Set Expansion and Multi Cut. For Max Cut, Sparsest Cut and Vertex
Cover, our techniques lead to subexponential algorithms with improved
approximation guarantees on subclasses of instances.
Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve
approximation guarantees such as ours for Unique Games. While our result
stops short of refuting the UGC, it does suggest that Unique Games is
significantly easier than NP-hard problems such as Max 3-SAT, Label Cover
and more, that are believed not to have subexponential algorithms achieving
a non-trivial approximation ratio.
The main component in our algorithms is a new kind of graph decomposition
that may have other applications: We show that by changing an epsilon
fraction of its edges, any regular graph on n vertices can be broken into
disjoint parts such that the stochastic adjacency matrix of each part has
at most n^epsilon eigenvalues larger than 1-epsilon^6.
Joint work with Sanjeev Arora and Boaz Barak.
See other events that are part of Theory Colloquium 2009/2010
See other events happening in May 2010
