# Integrality gaps for strong SDP relaxations of Unique Games

with . 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 $$\mathrm{L}_1$$, even though all sub-metrics of almost logarithmic size embed isometrically into $$\mathrm{L}_1$$.

## keywords

lower bounds, Unique Games Conjecture, strong relaxations, semidefinite programming.