Subexponential algorithms for unique games and related problems

Sanjeev Arora, Boaz Barak, David Steurer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

101 Scopus citations

Abstract

We give a subexponential time approximation algorithm for the Unique Games problem. The algorithms run in time that is exponential in an arbitrarily small polynomial of the input size, nε. The approximation guarantee depends on ε, but not on the alphabet size or the number of variables. We also obtain a subexponential algorithms with improved approximations for SMALL-SET EXPANSION and MULTICUT. For MAX CUT, SPARSEST CUT, and VERTEX COVER, we give subexponential algorithms with improved approximations on some interesting subclasses of instances. Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for the 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 3SAT, MAX 3LIN, LABEL COVER and more, that are believed not to have a subexponential algorithm achieving a non-trivial approximation ratio. The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every ε > 0 and every regular n-vertex graph G, by changing at most ε fraction of G's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most nε eigenvalues larger than 1 - η, where η depends polynomially on ε.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Pages563-572
Number of pages10
DOIs
StatePublished - Dec 1 2010
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, NV, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
CountryUnited States
CityLas Vegas, NV
Period10/23/1010/26/10

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Approximation algorithms
  • Constraint satisfaction problems
  • Eigenvalues
  • Graph decompositions
  • Spectral methods
  • Subexponential algorithms
  • Unique games

Fingerprint Dive into the research topics of 'Subexponential algorithms for unique games and related problems'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., Barak, B., & Steurer, D. (2010). Subexponential algorithms for unique games and related problems. In Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 (pp. 563-572). [5671307] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2010.59