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

Jeff Cheeger, Bruce Kleiner, Assaf Naor

Research output: Contribution to journalArticle

28 Scopus citations

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 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • 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