Integrality gaps for strong SDP relaxations of Unique Games

with Prasad Raghavendra. FOCS 2009.

PDF

abstract

Based on the work of Khot and Vishnoi (FOCS 2005), we construct the first integrality gaps for strong SDP relaxations of Unique Games. By composing these gaps with UG-hardness reductions, we obtain tight integrality gaps for strong SDP relaxations of a large class of problems including Max Cut, Max q-Cut, Max k-Sat, Max Acyclic Subgraph, and Multiway Cut.

The relaxation we consider is the standard SDP relaxation strengthened by all valid linear inequalities on up to almost a logarithmic number of variables. In addition, we apply a doubly-logarithmic number of rounds of Sherali–Adams lift-and-project.

Our techniques also yield the following non-embeddability result: There exists negative-type metrics which require doubly-logarithmic distortion to embed into L1\mathrm{L}_1, even though all sub-metrics of almost logarithmic size embed isometrically into L1\mathrm{L}_1.

keywords

  • lower bounds
  • Unique Games Conjecture
  • strong relaxations
  • semidefinite programming