SDP gaps and UGC-hardness for MAXCUTGAIN

Subhash Khot, Ryan O'Donneil

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pages217-226
Number of pages10
DOIs
StatePublished - 2006
Event47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, United States
Duration: Oct 21 2006Oct 24 2006

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
CountryUnited States
CityBerkeley, CA
Period10/21/0610/24/06

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'SDP gaps and UGC-hardness for MAXCUTGAIN'. Together they form a unique fingerprint.

Cite this