Given a graph with maximum cut of (fractional) size c, the Goemans-Williamson [GW95] semidefinite programming (SDP) algorithm is guaranteed to find a cut of size .878 ? c. However this guarantee becomes trivial when c is near 1/2, since a random cut has expected size 1/2. Recently, Charikar and Worth [CW04] (analyzing an algorithm of Feige and Langberg [FL01]) showed that given a graph with maximum cut 1/2 + \in, one can find a cut of size 1/2 + \Omega(\in/ log(1/\in)). The main contribution of our paper is twofold:

1. We give a natural 1/2+\in vs. 1/2+O(\in/ log(1/\in)) SDP gap for MAXCUT in Gaussian space. This shows that the SDP-rounding algorithm of Charikar-Worth is essentially best possible. Further, the "s-linear rounding functions" used in [CW04, FL01] arise as optimizers in our analysis, somewhat confirming a suggestion of [FL01].

2. We show how this SDP gap can be translated into a Long Code test with the same parameters. This implies that beating the Charikar-Worth guarantee with any efficient algorithm is NP-hard, assuming the Unique Games Conjecture (UGC) [Kho02]. We view this result as essentially settling the approximability of MAXCUT, assuming UGC.

Building on (1) we show how "randomness reduction" on related SDP gaps for the QUADRATICPROGRAMMING programming problem lets us make the \Omega(log(1/\in)) gap as large as \Omega(log n) for n-vertex graphs. In addition to optimally answering an open question of [AMMN06], this technique may prove useful for other SDP gap problems.

Finally, illustrating the generality of our technique in (2), we also show how to translate Reeds?s [Ree93] SDP gap for the Grothendieck Inequality into a UGChardness result for computing the \parallel ? \parallel\infty \mapsto 1 norm of a matrix.