Compression bounds for Lipschitz maps from the Heisenberg group to $L_1$

Abstract

We prove a quantitative bi-Lipschitz nonembedding theorem for the Heisenberg group with its Carnot-Carathéodory metric and apply it to give a lower bound on the integrality gap of the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem.

References in corpus (1)

• Differentiability of Lipschitz maps from metric measure spaces to Banach spaces with the Radon Nikodym property