The Unique Games Conjecture, Integrality Gap for Cut Problems and the Embeddability of Negative Type metrics into L_1

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 SDP-relaxation 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 (self-contained) talk, I will give a overview of our construction. This is joint work with Subhash Khot of Georgia Tech.