Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
type: Item
instance of: scholarly article
title: Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
zbMATH Open document ID: 1247.46020
author: Jeff Cheeger
author: Bruce Kleiner
author: Assaf Naor
published in: Acta Mathematica
publication date: 2012-05-10T00:00:00Z
full work available at URL: https://arxiv.org/abs/0910.2026
Mathematics Subject Classification ID: 46B85
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 20F65
Mathematics Subject Classification ID: 22E30
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6032746
zbMATH Keywords: bilipschitz embedding
zbMATH Keywords: Carnot-Carathéodory distance
zbMATH Keywords: Goemans-Linial conjecture
zbMATH Keywords: Heisenberg group
zbMATH Keywords: sparsest cut problem
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
OpenAlex ID: W1995977886
Wikidata QID: Q102217943
arXiv ID: 0910.2026
cites work: Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces
cites work: Fine properties of sets of finite perimeter in doubling metric measure spaces
cites work: Q4954179
cites work: Differentiability of Lipschitzian mappings between Banach spaces
cites work: Euclidean distortion and the sparsest cut
cites work: Expander flows, geometric embeddings and graph partitioning
cites work: Compression functions of uniform embeddings of groups into Hilbert and Banach spaces
cites work: Plongements lipschitziens dans ${\bbfR}\sp n$
cites work: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
cites work: The cut cone,L1 embeddability, complexity, and multicommodity flows
cites work: Affine approximation of Lipschitz functions and nonlinear quotients
cites work: On Lipschitz embedding of finite metric spaces in Hilbert space
cites work: Manifolds with 1/4-pinched curvature are space forms
cites work: A course in metric geometry
cites work: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
cites work: Lower bounds on Ricci curvature and the almost rigidity of warped products
cites work: On the structure of spaces with Ricci curvature bounded below. I
cites work: Q5439813
cites work: Differentiability of Lipschitz maps from metric measure spaces to Banach spaces with the Radon-Nikodym property
cites work: Differentiating maps into \(L^1\), and the geometry of BV functions
cites work: Metric differentiation, monotonicity and maps to \(L^{1}\)
cites work: Realization of metric spaces as inverse limits, and bilipschitz embedding in \(L_1\)
cites work: A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
cites work: Su una teoria generale della misura \((r-1)\)-dimensionale in uno spazio ad \(r\) dimensioni
cites work: Nuovi teoremi relativi alle misure \((r - 1)\)-dimensionali in uno spazio ad \(r\) dimensioni
cites work: Geometry of cuts and metrics
cites work: On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
cites work: Rectifiability and perimeter in the Heisenberg group
cites work: On the structure of finite perimeter sets in step 2 Carnot groups
cites work: Semidefinite programming in combinatorial optimization
cites work: Q3140233
cites work: Geometric algorithms and combinatorial optimization.
cites work: Sobolev met Poincaré
cites work: Lectures on analysis on metric spaces
cites work: From local to global in quasiconformal structures.
cites work: Extensions of Lipschitz mappings into a Hilbert space
cites work: Lipschitz and bi-Lipschitz functions
cites work: Measured descent: A new embedding method for finite metrics
cites work: Improved lower bounds for embeddings into L1
cites work: Q5531649
cites work: Ahlfors \(Q\)-regular spaces with arbitrary \(Q>1\) admitting weak Poincaré inequality
cites work: Bilipschitz embeddings of metric spaces into space forms
cites work: Extending Lipschitz functions via random metric partitions
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: On nonlinear projections in Banach spaces
cites work: Q4549227
cites work: The geometry of graphs and some of its algorithmic applications
cites work: Q3418237
cites work: A tour of subriemannian geometries, their geodesics and applications
cites work: Carnot-Carathéodory metrics and quasiisometries of symmetric spaces of rank 1
cites work: The maximum concurrent flow problem
cites work: Q3142876
cites work: Quantitative property A, Poincaré inequalities, \(L^p\)-compression and \(L^p\)-distortion for metric measure spaces
cites work: Q4087773

Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) (cites work)
cites work: Q3995204

Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) (DOI)
DOI: 10.1007/S11511-012-0071-9

Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) (review text)
review text: The first two authors [\textit{J. Cheeger} and \textit{B. Kleiner}, Ann. Math. (2) 171, No. 2, 1347--1385 (2010; Zbl 1194.22009); Invent. Math. 182, No. 2, 335--370 (2010; Zbl 1214.46013)] recently proved (in two different ways) that the Heisenberg group with its Carnot-Carathéodory distance does not admit a bilipschitz embedding into the Banach space \(L_1(0,1)\). The purpose of this paper is to get quantitative bounds for this non-embeddability.NEWLINENEWLINEThis work as well as the papers mentioned above is motivated by Computer Science applications. In more detail: the performance guarantees of the approximation algorithm for the Sparsest Cut Problem (which is known to be NP-complete) based on semidefinite programming are controlled by the distortion of embeddings of metrics of negative type into the Banach space \(L_1(0,1)\). (A metric space \((X,d)\) is said to be of negative type if the metric space \((X,d^{1/2})\) is isometric to a subset of a Hilbert space.) Goemans and Linial conjectured that there exists an absolute bound for this distortion. This conjecture, if true, would imply that the approximation algorithm has absolute (that is, independent of the size of the problem) performance guarantee. The Goemans-Linial conjecture was disproved by \textit{S. Khot} and \textit{N. K. Vishnoi} [in: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 53--62 (2005)] who proved that there exist \(n\)-element spaces with metrics of negative type whose \(L_1\)-distortions are of the order at least \((\log\log n)^{\frac16-\delta}\). This estimate was strengthened by \textit{R. Krauthgamer} and \textit{Y. Rabani} [SIAM J. Comput. 38, No. 6, 2487--2498 (2009; Zbl 1191.68869)] to \(\log\log n\).NEWLINENEWLINEThe idea to use the Heisenberg group for getting another counterexample to the Goemans-Linial conjecture is due to \textit{James R. Lee} and \textit{Assaf Naor} [in: Proceedings of the 47th Annual IEEE Symposium on F…