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.