Compression bounds for Lipschitz maps from the Heisenberg group to L₁
Cheeger, Jeff · Kleiner, Bruce · Naor, Assaf
Metric Geometry
Data Structures and Algorithms
Differential Geometry
Functional Analysis
Group Theory
Original · EN
We prove a quantitative bi-Lipschitz nonembedding 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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.