The Unique Games Conjecture, Integrality Gap for
Cut Problems and the Embeddability of Negative Type metrics into L_1
Nisheeth K. Vishnoi IBM Research, New Delhi
Tuesday, June 21, 2005 10:00 a.m., 2310 CS
It has been a long standing conjecture that negative type metrics
(metrics that are squares of Euclidean metrics) embed into L_1 with
constant distortion. Negative type metrics arise naturally as
solutions of semidefinite relaxations for Sparsest Cut and other Graph
Partitioning problems. This folklore conjecture implies that the
"integrality ratio" for the SDPrelaxation is bounded by a constant
(which in turn gives a constant factor approximation algorithm for
Sparsest Cut). The recent breakthrough algorithm of [Arora Rao
Vazirani] gave O(\sqrt{log n}) upper bound on the integrality ratio
and they conjectured a constant upper bound.
We disprove both of the
above conjectures by constructing an integrality ratio example with
ratio (loglog n)^{1/4}. Surprisingly, our construction is inspired
from complexity theoretic tools: PCPs, Fourier Analysis, and the
Unique Games Conjecture (UGC) by [Khot]. The techniques have no a
priori connection with metric embeddings!
In this (selfcontained)
talk, I will give a overview of our construction. This is joint work
with Subhash Khot of Georgia Tech.
