Spectral algorithms for unique games
From MaRDI portal
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Abstract: We give a new algorithm for Unique Games which is based on purely {em spectral} techniques, in contrast to previous work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment. The approximation guarantee depends only on the completeness of the game, and not on the alphabet size, while the running time depends on spectral properties of the {em Label-Extended} graph associated with the instance of Unique Games. We further show that on input the integrality gap instance of Khot and Vishnoi, our algorithm runs in quasi-polynomial time and decides that the instance if highly unsatisfiable. Notably, when run on this instance, the standard SDP relaxation of Unique Games {em fails}. As a special case, we also re-derive a polynomial time algorithm for Unique Games on expander constraint graphs. The main ingredient of our algorithm is a technique to effectively use the full spectrum of the underlying graph instead of just the second eigenvalue, which is of independent interest. The question of how to take advantage of the full spectrum of a graph in the design of algorithms has been often studied, but no significant progress was made prior to this work.
Recommendations
Cites work
- Approximating unique games
- Graph expansion and the unique games conjecture
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 51219 (Why is no real title available?)
- Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
- Near-optimal algorithms for unique games
- On the hardness of approximating Multicut and Sparsest-Cut
- On the power of unique 2-prover 1-round games
- Spectral techniques applied to sparse random graphs
- Subexponential algorithms for unique games and related problems
- The Rotation of Eigenvectors by a Perturbation. III
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- Towards sharp inapproximability for any 2-CSP
- Unique games on expanding constraint graphs are easy (extended abstract)
Cited in
(15)- Near-optimal algorithms for unique games
- Approximation algorithms for unique games
- Subexponential algorithms for unique games and related problems
- Making the Long Code Shorter
- Unique games on expanding constraint graphs are easy (extended abstract)
- Graph Clustering using Effective Resistance
- Approximating unique games using low diameter graph decomposition
- Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
- scientific article; zbMATH DE number 7561741 (Why is no real title available?)
- Computational topology and the unique games conjecture
- Unique games on the hypercube
- Approximately counting independent sets in bipartite graphs via graph containers
- Mathematics of computation through the lens of linear equations and lattices
- Inapproximability of unique games in fixed-point logic with counting
- A note on unique games
This page was built for publication: Spectral algorithms for unique games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q645126)
