Luca Trevisan

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 >>>

Uriel Feige, Guy Kindler, Ryan O'Donnell

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 >>>

Konstantin Makarychev, Yury Makarychev

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 >>>

Venkatesan Guruswami, Ali Kemal Sinop

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 >>>

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

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 >>>