On the Unique Games Conjecture Page 1 On the Unique Games Conjecture Subhash Khot
Courant Institute of Mathematical Sciences, NYU ∗ Abstract This article surveys recently …

Discrete optimization problems are everywhere, from traditional operations research
planning (scheduling, facility location and network design); to computer science databases; …

Based on a conjecture regarding the power of unique 2-prover-1-round games presented in
[S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th ACM Symp. on …

In this paper we show a reduction from the Unique Games problem to the problem of
approximating MAX-CUT to within a factor of GW+ϵ for all ϵ>0; here GW≈.878567 denotes …

We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion.
This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit …

In this paper, we study functions with low influences on product probability spaces. The
analysis of Boolean functions f {-1, 1}/sup n//spl rarr/{-1, 1} with low influences has become a …

Semidefinite Programming (SDP) is one of the strongest algorithmic techniques used in the
design of approximation algorithms. In recent years, Unique Games Conjecture (UGC) has …

The complexity and approximability of the constraint satisfaction problem (CSP) has been
actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP) …

We present a candidate reduction from the 3-Lin problem to the 2-to-2 Games problem and
present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to …

A Brief Introduction to Fourier Analysis on the Boolean Cube Page 1 Theory OF Computing
Library Graduate Surveys, TCGS 1 (2008), pp. 1–20 http://theoryofcomputing.org A Brief …