Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNIQUE GAMES, SPECTRA, ALGORITHM, INTEGRALITY GAP, SDP:
Reports tagged with Unique Games, Spectra, algorithm, integrality gap, SDP:
TR10-029 | 3rd March 2010
Alexandra Kolla

Spectral Algorithms for Unique Games

We present 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 ... more >>>




ISSN 1433-8092 | Imprint