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.