Compression bounds for Lipschitz maps from the Heisenberg group to L 1

Research output: Contribution to journalArticle

Abstract

We prove a quantitative bi-Lipschitz non-embedding 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.

Original languageEnglish (US)
Pages (from-to)291-373
Number of pages83
JournalActa Mathematica
Volume207
Issue number2
DOIs
StatePublished - Dec 2011

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Compression bounds for Lipschitz maps from the Heisenberg group to L <sub>1</sub>'. Together they form a unique fingerprint.

  • Cite this