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 + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique Games Conjecture of Khot~\cite{Kho02} holds then the Goemans-Williamson approximation algorithm is optimal. Our result indicates that the geometric nature of the Goemans-Williamson algorithm might be intrinsic to the MAX-CUT problem.
Our reduction relies on a theorem we call Majority Is Stablest. This was introduced as a conjecture in the original version of this paper, and was subsequently confirmed in~\cite{MOO05}. A stronger version of his conjecture called Plurality Is Stablest is still open, although~\cite{MOO05} contains a proof of an asymptotic version of it.
Our techniques extend to several other two-variable constraint satisfaction problems. In particular, subject to the Unique Games conjecture, we show tight or nearly tight hardness results for MAX-2SAT, MAX-$q$-CUT, and MAX-2LIN($q$).
For MAX-2SAT we show approximation hardness up to a factor of roughly $.943$. This nearly matches the $.940$ approximation algorithm of Lewin, Livnat, and Zwick~\cite{LLZ02}. Furthermore, we show that our $.943...$ factor is actually tight for a slightly restricted version of MAX-2SAT. For MAX-$q$-CUT we show a hardness factor which asymptotically (for large $q$) matches the approximation factor achieved by Frieze and Jerrum~\cite{FriezeJerrum:95}, namely $1 - 1/q + 2(\ln q)/q^2$.
For MAX-2LIN($q$) we show hardness of distinguishing between instances which are $(1-\epsilon)$-satisfiable and those which are not even, roughly, $(q^{-\nfrac{\epsilon}{2}})$-satisfiable. These parameters almost match those achieved by the recent algorithm of Charikar, Makarychev, and Makarychev~\cite{cmm05}. The hardness result holds even for instances in which all equations are of the form $x_i - x_j = c$. At a more qualitative level, this result also implies that $1-\eps$ vs.\ $\eps$ hardness for MAX-2LIN($q$) is \emph{equivalent} to the Unique Games Conjecture.
