February 15th, 2005

beartato phd

(no subject)

I got this talk announcement this morning. It sounds like the epitome of theadana-porn.
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.
beartato phd

(no subject)

I think the philosophy of language class over at pitt finally lost me today.

I wasted a few hours in the Carnegie reading most of Larry Gonick's "The Cartoon History of the World part III". Good stuff. Lots of interesting stuff about Turkish, Chinese, African history.