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

DOI10.1007/s11511-012-0071-9zbMath1247.46020arXiv0910.2026OpenAlexW1995977886WikidataQ102217943 ScholiaQ102217943MaRDI QIDQ416849

Jeff Cheeger, Assaf Naor, Bruce Kleiner

Publication date: 10 May 2012

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

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

zbMATH Keywords

Heisenberg groupbilipschitz embeddingCarnot-Carathéodory distanceGoemans-Linial conjecturesparsest cut problem

Mathematics Subject Classification ID

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

Related Items

Sketching and Embedding are Equivalent for Norms, Metric Characterizations of Some Classes of Banach Spaces, Area-minimizing ruled graphs and the Bernstein problem in the Heisenberg group, Vertical perimeter versus horizontal perimeter, Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces, Discretization and affine approximation in high dimensions, Metric differentiation, monotonicity and maps to \(L^{1}\), Horizontally affine functions on step-2 Carnot algebras, Monotone sets and local minimizers for the perimeter in Carnot groups, On the inner cone property for convex sets in two-step Carnot groups, with applications to monotone sets, Precisely monotone sets in step-2 rank-3 Carnot algebras, Lower bounds on Ricci curvature and quantitative behavior of singular sets, A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional, Vertical versus horizontal Poincaré inequalities on the Heisenberg group, Semmes surfaces and intrinsic Lipschitz graphs in the Heisenberg group, Markov convexity and nonembeddability of the Heisenberg group, Equivalent definitions of \(BV\) space and of total variation on metric measure spaces, Coarse differentiation and quantitative nonembeddability for Carnot groups, Bourgain's discretization theorem, Quantitative Stratification and the Regularity of Harmonic Maps and Minimal Currents, Quantitative geometry, Heat flow and quantitative differentiation, Inverse limit spaces satisfying a Poincaré inequality, Differentiating maps into \(L^1\), and the geometry of BV functions, No dimension reduction for doubling subsets of \(\ell_q\) when \(q>2\) revisited, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, Quantitative affine approximation for UMD targets, Polynomial and horizontally polynomial functions on Lie groups, Sharp differentiability results for the lower local Lipschitz constant and applications to non-embedding, The Lip-lip equality is stable under blow-up

Cites Work

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