A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP.

link: http://arxiv.org/abs/0910.2024
Abstract

We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut
problem with general demands has integrality gap $(\log n)^{\Omega(1)}$. This
is achieved by exhibiting $n$-point metric spaces of negative type whose $L_1$
distortion is $(\log n)^{\Omega(1)}$. Our result is based on quantitative
bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group
to $L_1$ when restricted to cosets of the center.