Jason (jcreed) wrote,
Jason
jcreed

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.
Tags: funny, words
Subscribe

  • (no subject)

    Some further progress cleaning up the https://xkcd.com/1360/ -esque augean stables that is my hard drive. Tomato chicken I made a couple days ago…

  • (no subject)

    Did some personal archaeology. Helped a little with laundry. Threw some chicken, onions, tomato, stock, peppers in the slow cooker and hopefully…

  • (no subject)

    Dinner with akiva and dannel at nuevo portal in carroll gardens. Ate a pile of chicken stew and rice and beans and maduros, good times. I do miss…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 5 comments