Abstract:

We give a subexponential-time approximation algorithm for the Unique Games problem: Given a Unique Games instance with optimal value 1-epsilon and alphabet size k, our algorithm finds in time exp(k*n^beta) a solution of value 1-sqrt(epsilon/beta^3). Here, beta>0 is a parameter of the algorithm that can be chosen arbitrarily small.

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^beta eigenvalues above 1-eta, such that at most a sqrt(epsilon/beta^3) fraction of the edges of the graph does not respect the partition.

Joint work with Sanjeev Arora and Boaz Barak.