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.