Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > WILLIAM MATTHEWS:
All reports by Author William Matthews:

TR10-041 | 11th March 2010
Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

Improved Algorithms for Unique Games via Divide and Conquer

We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. ... more >>>




ISSN 1433-8092 | Imprint