We give a subexponential-time approximation algorithm for the Unique Games
problem: Given a Unique Games instance with optimal value 1-epsilon3 and
alphabet size k, our algorithm finds in time exp(k*n^epsilon) a solution of
constant value (say at least 0.99).

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 interesting 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 results
stop short of refuting the UGC, they do 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 guarantee.

The main component in our algorithms is a new kind of graph decomposition
that may have other applications: We show that every graph with n vertices
can be efficiently partitioned into disjoint induced subgraphs, each with
at most n^epsilon eigenvalues above 1-epsion3, such that at most 0.01 of
the edges do not respect the partition.

Joint work with Sanjeev Arora and Boaz Barak.