Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Unique Games:
TR05-034 | 5th April 2005
Luca Trevisan

Approximation Algorithms for Unique Games

Revisions: 1 , Comments: 1

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an ... more >>>

TR07-043 | 7th May 2007
Uriel Feige, Guy Kindler, Ryan O'Donnell

Understanding Parallel Repetition Requires Understanding Foams

Motivated by the study of Parallel Repetition and also by the Unique
Games Conjecture, we investigate the value of the ``Odd Cycle Games''
under parallel repetition. Using tools from discrete harmonic
analysis, we show that after $d$ rounds on the cycle of length $m$,
the value of the game is ... more >>>

TR09-021 | 2nd March 2009
Konstantin Makarychev, Yury Makarychev

How to Play Unique Games on Expanders

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 - epsilon)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignments satisfying at least a (1 - C ... more >>>

TR09-099 | 16th October 2009
Venkatesan Guruswami, Ali Kemal Sinop

Improved Inapproximability Results for Maximum k-Colorable Subgraph

Revisions: 1

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>

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