Compression bounds for Lipschitz maps from the Heisenberg group to L1
Open Access
- 1 January 2011
- journal article
- Published by International Press of Boston in Acta Mathematica
- Vol. 207 (2), 291-373
- https://doi.org/10.1007/s11511-012-0071-9
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.Keywords
This publication has 49 references indexed in Scilit:
- Compression functions of uniform embeddings of groups into Hilbert and Banach spacesJournal für die reine und angewandte Mathematik (Crelles Journal), 2009
- Euclidean distortion and the sparsest cutJournal of the American Mathematical Society, 2007
- Expander flows, geometric embeddings and graph partitioningPublished by Association for Computing Machinery (ACM) ,2004
- Fine Properties of Sets of Finite Perimeter in Doubling Metric Measure SpacesSet-Valued Analysis, 2002
- Some Fine Properties of Sets of Finite Perimeter in Ahlfors Regular Metric Measure SpacesAdvances in Mathematics, 2001
- Affine Approximation of Lipschitz Functions and Nonlinear QuotientsGeometric and Functional Analysis, 1999
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation AlgorithmSIAM Journal on Computing, 1998
- The cut cone, L1 embeddability, complexity, and multicommodity flowsNetworks, 1991
- Plongements lipschitziens dans ${\bbfR}\sp n$Bulletin de la Société Mathématiques de France, 1983
- Differentiability of Lipschitzian mappings between Banach spacesStudia Mathematica, 1976