Theory of Computing ------------------- Title : SDP Gaps and UGC-hardness for Max-Cut-Gain Authors : Subhash Khot and Ryan O'Donnell Volume : 5 Number : 4 Pages : 83-117 URL : https://theoryofcomputing.org/articles/v005a004 Abstract -------- Given a graph with maximum cut of (fractional) size c, the semidefinite programming (SDP)-based algorithm of Goemans and Williamson is guaranteed to find a cut of size at least .878c. However, this guarantee becomes trivial when c is near 1/2, since making random cuts guarantees a cut of size 1/2 (i.e., half of all edges). A few years ago, Charikar and Wirth (analyzing an algorithm of Feige and Langberg) showed that given a graph with maximum cut 1/2 + \epsilon, one can find a cut of size 1/2 + Omega(epsilon/log(1/epsilon)). The main contribution of our paper is twofold: 1. We give a natural and explicit 1/2 + \epsilon vs. 1/2 + O(epsilon/log(1/epsilon)) integrality gap for the Max-Cut SDP based on Euclidean space with the Gaussian probability distribution. This shows that the SDP-rounding algorithm of Charikar-Wirth is essentially best possible. 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-Wirth guarantee with *any* efficient algorithm is NP-hard, assuming the Unique Games Conjecture (UGC). This result essentially settles the asymptotic approximability of Max-Cut, assuming UGC. Building on the first contribution, we show how "randomness reduction" on related SDP gaps for the Quadratic-Programming problem lets us make the Omega(log(1/epsilon)) gap as large as Omega(\log n) for n-vertex graphs. In addition to optimally answering an open question of Alon, Makarychev, Makarychev, and Naor, this technique may prove useful for other SDP gap problems. Finally, illustrating the generality of our second contribution, we also show how to translate the Davie--Reeds SDP gap for the Grothendieck Inequality into a UGC-hardness result for computing the ||.||_{infty --> 1} norm of a matrix.