Subject: Subhash Khot visit Subhash Khot will be here next Monday. Talk to Chris (ckoch@cs) to get on his schedule. He'll be giving his talk in the morning (10:30am). I've appended his title/abstract below. On Embeddability of Negative Type Metrics into L_1 ---------------------------------------------------------------- Goemans and Linial conjectured 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 Graph Partitioning problems. The GL-conjecture implies that the "integrality ratio" for the SDP-relaxation is bounded by a constant (which gives constant factor approximation algorithm). The recent breakthrough algorithm of [Arora Rao Vazirani] gave O(\sqrt{log n}) upper bound on the integrality ratio and they too conjectured a constant upper bound. We disprove both the above conjectures by constructing an integrality ratio example with ratio (log log n)^c for some constant c > 0. Surprisingly, our construction is inspired from complexity theoretic tools, namely PCPs, Fourier Analysis, and the Unique Games Conjecture (UGC) by [Khot]. The techniques have no a priori connection with metric embeddings ! In this talk, I will give a overview of our construction and other research that UGC has led to (e.g. optimal hardness results for Vertex Cover and MAX-CUT assuming UGC). The talk will be self-contained. Mostly based on joint work with Nisheeth Vishnoi.