TY - GEN

T1 - SDP gaps and UGC-hardness for MAXCUTGAIN

AU - Khot, Subhash

AU - O'Donneil, Ryan

PY - 2006

Y1 - 2006

N2 - 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 + ε, one can find a cut of size 1/2 + ω (ε / log(1/ε)). The main contribution of our paper is twofold: 1. We give a natural 1/2 + ε vs. 1/2 + O(ε/ log(1/ε)) 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 QUADRATICPRO-GRAMMlNG programming problem lets us make the Ω(log(1/ε)) gap as large as Ω(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 UGC-hardness result for computing the ∥·∥ ∞→1 norm of a matrix.

AB - 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 + ε, one can find a cut of size 1/2 + ω (ε / log(1/ε)). The main contribution of our paper is twofold: 1. We give a natural 1/2 + ε vs. 1/2 + O(ε/ log(1/ε)) 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 QUADRATICPRO-GRAMMlNG programming problem lets us make the Ω(log(1/ε)) gap as large as Ω(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 UGC-hardness result for computing the ∥·∥ ∞→1 norm of a matrix.

UR - http://www.scopus.com/inward/record.url?scp=35448938376&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35448938376&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2006.67

DO - 10.1109/FOCS.2006.67

M3 - Conference contribution

AN - SCOPUS:35448938376

SN - 0769527205

SN - 9780769527208

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 217

EP - 226

BT - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

T2 - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

Y2 - 21 October 2006 through 24 October 2006

ER -