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

Jeff Cheeger; Bruce Kleiner; Assaf Naor

doi:10.1007/s11511-012-0071-9

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

Jeff Cheeger, Bruce Kleiner, Assaf Naor

Research output: Contribution to journal › Article › peer-review

38 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 language	English (US)
Pages (from-to)	291-373
Number of pages	83
Journal	Acta Mathematica
Volume	207
Issue number	2
DOIs	https://doi.org/10.1007/s11511-012-0071-9
State	Published - Dec 2011
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1007/s11511-012-0071-9

Cite this

@article{fb98b1dcc9b942eebbc123de12123787,

title = "Compression bounds for Lipschitz maps from the Heisenberg group to L 1 ",

abstract = "We prove a quantitative bi-Lipschitz non-embedding theorem for the Heisenberg group with its Carnot-Carath{\'e}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.",

author = "Jeff Cheeger and Bruce Kleiner and Assaf Naor",

note = "Funding Information: J.C. was supported in part by NSF grant DMS-0704404. B.K. was supported in part by NSF grant DMS-0805939. A.N. was supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009 and the Packard Foundation.",

year = "2011",

month = dec,

doi = "10.1007/s11511-012-0071-9",

language = "English (US)",

volume = "207",

pages = "291--373",

journal = "Acta Mathematica",

issn = "0001-5962",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

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

AU - Cheeger, Jeff

AU - Kleiner, Bruce

AU - Naor, Assaf

N1 - Funding Information: J.C. was supported in part by NSF grant DMS-0704404. B.K. was supported in part by NSF grant DMS-0805939. A.N. was supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009 and the Packard Foundation.

PY - 2011/12

Y1 - 2011/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84857992921&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84857992921&partnerID=8YFLogxK

U2 - 10.1007/s11511-012-0071-9

DO - 10.1007/s11511-012-0071-9

M3 - Article

AN - SCOPUS:84857992921

SN - 0001-5962

VL - 207

SP - 291

EP - 373

JO - Acta Mathematica

JF - Acta Mathematica

IS - 2

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this