[Colloquium] Reminder: TTI-C Talk TODAY at 3:00pm Nisheeth Vishnoi

[Katherine Cumming]

Nisheeth Vishnoi 
IBM, New Delhi
The Unique Games Conjecture, Integrality Gap for Cut Problems...
June 20, 2005 3:00pm
Abstract:
...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. 
If you have questions, or would like to meet the speaker, please contact
Katherine at773-834-1994 or kcumming at tti-c.org. For information on
future TTI-C talks or events, please go to the TTI-C Events
<http://ttic.uchicago.edu/events/events_dyn.php>  page. 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050620/5fcdb3cc/attachment.htm