Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ALEXANDRA KOLLA:
All reports by Author Alexandra Kolla:

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