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

DOI10.1007/S11511-012-0071-9zbMATH Open1247.46020arXiv0910.2026OpenAlexW1995977886WikidataQ102217943 ScholiaQ102217943MaRDI QIDQ416849FDOQ416849

Authors: Jeff Cheeger, Bruce Kleiner, Assaf Naor 

Publication date: 10 May 2012

Published in: Acta Mathematica (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/0910.2026

Recommendations

• \(L_{1}\) embeddings of the Heisenberg group and fast estimation of graph isoperimetry
• Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces
• Vertical versus horizontal Poincaré inequalities on the Heisenberg group
• Embedding the Heisenberg group into a bounded-dimensional Euclidean space with optimal distortion
• Metric differentiation, monotonicity and maps to \(L^{1}\)

zbMATH Keywords

Heisenberg groupbilipschitz embeddingGoemans-Linial conjecturesparsest cut problemCarnot-Carathéodory distance

Mathematics Subject Classification ID

Approximation algorithms (68W25) Distance in graphs (05C12) Geometric group theory (20F65) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Analysis on real and complex Lie groups (22E30)

Cites Work

• Title not available (Why is that?)
• Extensions of Lipschitz mappings into a Hilbert space
• A course in metric geometry
• Carnot-Carathéodory metrics and quasiisometries of symmetric spaces of rank 1
• On the structure of spaces with Ricci curvature bounded below. I
• Lectures on analysis on metric spaces
• Extending Lipschitz functions via random metric partitions
• Lower bounds on Ricci curvature and the almost rigidity of warped products
• On nonlinear projections in Banach spaces
• Differentiability of Lipschitz maps from metric measure spaces to Banach spaces with the Radon-Nikodym property
• A tour of subriemannian geometries, their geodesics and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sobolev met Poincaré
• On the differentiability of Lipschitz maps from metric measure spaces to Banach spaces
• Geometric algorithms and combinatorial optimization.
• On the structure of finite perimeter sets in step 2 Carnot groups
• The geometry of graphs and some of its algorithmic applications
• Measured descent: A new embedding method for finite metrics
• Su una teoria generale della misura \((r-1)\)-dimensionale in uno spazio ad \(r\) dimensioni
• Title not available (Why is that?)
• Some relations among volume, intrinsic perimeter and one-dimensional restrictions of \(BV\)functions in Carnot groups
• Realization of metric spaces as inverse limits, and bilipschitz embedding in \(L_1\)
• Plongements lipschitziens dans ${\bbfR}\sp n$
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• Title not available (Why is that?)
• Geometry of cuts and metrics
• Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces
• Rectifiability and perimeter in the Heisenberg group
• Bilipschitz embeddings of metric spaces into space forms
• Metric differentiation, monotonicity and maps to \(L^{1}\)
• Nuovi teoremi relativi alle misure \((r - 1)\)-dimensionali in uno spazio ad \(r\) dimensioni
• Differentiating maps into \(L^1\), and the geometry of BV functions
• Ahlfors \(Q\)-regular spaces with arbitrary \(Q>1\) admitting weak Poincaré inequality
• The maximum concurrent flow problem
• Title not available (Why is that?)
• Manifolds with \(1/4\)-pinched curvature are space forms
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Expander flows, geometric embeddings and graph partitioning
• Differentiability of Lipschitzian mappings between Banach spaces
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Euclidean distortion and the sparsest cut
• Fine properties of sets of finite perimeter in doubling metric measure spaces
• Compression functions of uniform embeddings of groups into Hilbert and Banach spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Affine approximation of Lipschitz functions and nonlinear quotients
• From local to global in quasiconformal structures.
• Semidefinite programming in combinatorial optimization
• Lipschitz and bi-Lipschitz functions
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• Improved lower bounds for embeddings into L₁
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Title not available (Why is that?)
• Quantitative property A, Poincaré inequalities, \(L^p\)-compression and \(L^p\)-distortion for metric measure spaces

Cited In (33)

• Sharp differentiability results for the lower local Lipschitz constant and applications to non-embedding
• The Lip-lip equality is stable under blow-up
• Vertical versus horizontal Poincaré inequalities on the Heisenberg group
• Quantitative stratification and the regularity of harmonic maps and minimal currents
• Metric differentiation, monotonicity and maps to \(L^{1}\)
• Heat flow and quantitative differentiation
• Differentiating maps into \(L^1\), and the geometry of BV functions
• Embedding the Heisenberg group into a bounded-dimensional Euclidean space with optimal distortion
• Monotone sets and local minimizers for the perimeter in Carnot groups
• The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
• Vertical perimeter versus horizontal perimeter
• Area-minimizing ruled graphs and the Bernstein problem in the Heisenberg group
• A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional
• Quantitative affine approximation for UMD targets
• Sketching and embedding are equivalent for norms
• Equivalent definitions of \(BV\) space and of total variation on metric measure spaces
• Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces
• Foliated corona decompositions
• Horizontally affine functions on step-2 Carnot algebras
• Free objects in Banach space theory
• Semmes surfaces and intrinsic Lipschitz graphs in the Heisenberg group
• Inverse limit spaces satisfying a Poincaré inequality
• No dimension reduction for doubling subsets of \(\ell_q\) when \(q>2\) revisited
• Coarse differentiation and quantitative nonembeddability for Carnot groups
• Bourgain's discretization theorem
• Precisely monotone sets in step-2 rank-3 Carnot algebras
• Polynomial and horizontally polynomial functions on Lie groups
• On the inner cone property for convex sets in two-step Carnot groups, with applications to monotone sets
• Lower bounds on Ricci curvature and quantitative behavior of singular sets
• Markov convexity and nonembeddability of the Heisenberg group
• \(L_{1}\) embeddings of the Heisenberg group and fast estimation of graph isoperimetry
• Discretization and affine approximation in high dimensions
• Quantitative geometry

This page was built for publication: Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q416849)