How to Play Unique Games on Expanders

DOI10.1007/978-3-642-18318-8_17zbMATH Open1314.68401arXiv0903.0367OpenAlexW1511070007MaRDI QIDQ3075461FDOQ3075461

Authors: Konstantin Makarychev, Yury Makarychev 

Publication date: 15 February 2011

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Abstract: In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a $(1-varepsilon)$-satisfiable instance of Unique Games with the constraint graph $G$, our algorithm finds an assignment satisfying at least a $1-Cvarepsilon/h_G$ fraction of all constraints if $varepsilon<clambd{a}_G$ where $h_G$ is the edge expansion of $G$, $lambd{a}_G$ is the second smallest eigenvalue of the Laplacian of $G$, and $C$ and $c$ are some absolute constants.

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

Recommendations

• Playing unique games on certified small-set expanders
• A note on unique games
• Unique games on the hypercube
• scientific article; zbMATH DE number 16387
• scientific article; zbMATH DE number 2086402
• Games with uniqueness properties
• How to win a game with features
• How to win a game with features
• How to play Thue games

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Games on graphs (graph-theoretic aspects) (05C57)

Cited In (12)

• Computational topology and the unique games conjecture
• Approximating unique games using low diameter graph decomposition
• Title not available (Why is that?)
• How to play Thue games
• List-Decoding with Double Samplers
• Approximation Algorithms for CSPs
• Approximately counting independent sets in bipartite graphs via graph containers
• Tilings of rectangles with T-tetrominoes
• Spectral algorithms for unique games
• Algorithms for \#BIS-hard problems on expander graphs
• Efficient algorithms for the Potts model on small-set expanders
• Unique games on expanding constraint graphs are easy (extended abstract)

This page was built for publication: How to Play Unique Games on Expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3075461)