Spectral algorithms for unique games

DOI10.1007/s00037-011-0011-7zbMath1234.68120arXiv1102.2300OpenAlexW2117220151MaRDI QIDQ645126

Alexandra Kolla

Publication date: 8 November 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.2300

zbMATH Keywords

algorithmsgraph spectraunique games

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Making the Long Code Shorter ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Graph Clustering using Effective Resistance ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Computational topology and the Unique Games Conjecture ⋮ Unnamed Item ⋮ Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating Multicut and Sparsest-Cut
• Graph expansion and the unique games conjecture
• Near-optimal algorithms for unique games
• Towards Sharp Inapproximability for Any 2-CSP
• Subexponential Algorithms for Unique Games and Related Problems
• On the power of unique 2-prover 1-round games
• Approximating unique games
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Spectral techniques applied to sparse random graphs
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• The Rotation of Eigenvectors by a Perturbation. III