### Subexponential Algorithms for Unique Games and Related ProblemsSubexponential Algorithms for Unique Games and Related Problems

Access Restriction
Subscribed

 Author Arora, Sanjeev ♦ Barak, Boaz ♦ Steurer, David Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Unique games conjecture ♦ Graph decomposition ♦ Graph partitioning ♦ Small set expansion ♦ Spectral algorithms ♦ Spectral graph theory Abstract Subexponential time approximation algorithms are presented for the Unique Games and Small-Set Expansion problems. Specifically, for some absolute constant $\textit{c},$ the following two algorithms are presented. (1) An $exp(kn^{ε})-time$ algorithm that, given as input a $\textit{k}-alphabet$ unique game on $\textit{n}$ variables that has an assignment satisfying $1-ε^{c}$ fraction of its constraints, outputs an assignment satisfying 1-ε fraction of the constraints. (2) An $exp(n^{ε}/Δ)-time$ algorithm that, given as input an $\textit{n}-vertex$ regular graph that has a set $\textit{S}$ of $Δ\textit{n}$ vertices with edge expansion at most $ε^{c},$ outputs a set $\textit{S'}$ of at most Δ $\textit{n}$ vertices with edge expansion at most ε. subexponential algorithm is also presented with improved approximation to Max Cut, Sparsest Cut, and Vertex Cover on some interesting subclasses of instances. These instances are graphs with low threshold rank, an interesting new graph parameter highlighted by this work. Khot's Unique Games Conjecture (UGC) states that it is $\textbf{NP}-hard$ to achieve approximation guarantees such as ours for Unique Games. While the results here stop short of refuting the UGC, they do suggest that Unique Games are significantly easier than $\textbf{NP}-hard$ problems such as Max 3-Sat, Max 3-Lin, Label Cover, and more, which are believed not to have a subexponential algorithm achieving a nontrivial approximation ratio. Of special interest in these algorithms is a new notion of graph decomposition that may have other applications. Namely, it is shown for every ε >0 and every regular $\textit{n}-vertex$ graph $\textit{G},$ by changing at most Δ fraction of $\textit{G}'s$ edges, one can break $\textit{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 ε. The subexponential algorithm combines this decomposition with previous algorithms for Unique Games on graphs with few large eigenvalues [Kolla and Tulsiani 2007; Kolla 2010]. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-11-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 5 Page Count 25 Starting Page 1 Ending Page 25

#### Open content in new tab

Source: ACM Digital Library