Fetching the paper…

Reading the bibliography…

2009

How to Play Unique Games on Expanders

Makarychev, Konstantin, Makarychev, Yury

Original
PDF
Post on X

Understand

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- C \varepsilon/h_G$ fraction of all constraints if $\varepsilon < c \lambda_G$ where $h_G$ is the edge expansion of $G$, $\lambda_G$ is the second smallest eigenvalue of the Laplacian of $G$, and $C$ and $c$ are some absolute constants.

How to Play Unique Games on Expanders · Around

Built on

On the power of unique 2-prover 1-round games
S. Khot · 2002
Earlier work this paper cites.
Approximation Algorithms for Unique Games
L. Trevisan · 2005
Earlier work this paper cites.
Near-Optimal Algorithms for Unique Games
M. Charikar, K. Makarychev, and Y. Makarychev · 2006
Earlier work this paper cites.

Similar

Unique games on expanding constraint graphs are easy
E. Chlamtac, K. Makarychev, and Y. Makarychev · 2006
Cited alongside, same era.
Approximating Unique Games
A. Gupta and K. Talwar · 2006
Cited alongside, same era.

Then

Optimal inapproximability results for MAX-CUT and other two-variable CSPs?
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell · 2007
Later among the works it cites.
Near-Optimal Algorithms for Unique Games
S. Arora, S. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. Vishnoi · 2008
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…