The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n.

Assaf Naor, Robert Young

Browse the full STOC paper archive.