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

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

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.

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 Foundations of Computer Science, IEEE, Piscataway, NJ, 99--108 (2006)]. They observed that the Carnot-Carathéodory metric on the Heisenberg group is equivalent to a negative type metric and so if one can prove that the group does not admit bilipschitz embeddings into \(L_1(0,1)\), this would give another counterexample to the Goemans-Linial conjecture. This goal was achieved by Cheeger and Kleiner [loc. cit.]. However, for Computer Science applications it was important to find quantitative estimates for the \(L_1\)-distortions of embeddings of finite subsets of the Heisenberg group. The main purpose of the present paper is to obtain such estimates.NEWLINENEWLINEOne of the main results of the paper is the following theorem, which the authors call the ``Quantitative central collapse theorem: There exists a universal constant \(\delta\in (0,1)\) such that for every point \(p\) in the Heisenberg group \(\mathbb{H}\), every \(1\)-Lipschitz \(f:B_1(p)\to L_1\) (where \(B_1(p)\) is the ball in \(\mathbb{H}\) of radius \(1\)), and every \(\varepsilon\in \left(0,\frac14\right)\), there exists \(r\geq \frac12\varepsilon\) such that, with respect to Haar measure, for at least half of the points \(x\in B_{1/2}(p)\), at least half of the points \((x_1,x_2)\in B_r(x)\times B_r(x)\) which lie on the same coset of the center of \(\mathbb{H}\), with \(d^\mathbb{H}(x_1,x_2)\in\left[\frac12\varepsilon r,\frac32\varepsilon r\right]\), satisfy: NEWLINE\[NEWLINE\frac{\|f(x_1)-f(x_2)\|_{L_1}}{d^\mathbb{H}(x_1,x_2)}\leq \frac1{(\log(1/\varepsilon))^\delta}, NEWLINE\]NEWLINE where \(d^{\mathbb{H}}\) is the Carnot-Carathéodory distance on \(\mathbb{H}\).NEWLINENEWLINEThis result allows the authors to get an exponential improvement of the previous poor-embeddabi\-li\-ty estimates of finite metric spaces of negative type into \(L_1(0,1)\) (Khot-Vishnoi, Krauth\-ga\-mer-Rabani [loc. cit]):NEWLINENEWLINEThere exist universal constants \(c,\delta>0\) such that any embedding into \(L_1(0,1)\) of the restriction of the word metric \(d_W\) of the discrete Heisenberg group to the \(n\times n\times n\) grid \(\{1,\dots,n\}^3\) incurs distortion \(\geq c(\log n)^\delta\).NEWLINENEWLINEFinding sharp estimates of the maximal possible value of \(\delta\) in this result is a challenging open problem.NEWLINENEWLINEThe starting point of the argument in the paper might be regarded as a mixture of arguments of the papers of Cheeger and Kleiner [loc. cit.]. The arguments are based on the characterization of the \(L_1\) metrics as cut metrics and on the analysis of subsets on which the measures corresponding to such metrics on the Heisenberg group can be supported. In the quantitative analysis of the present paper numerous additional difficulties arise. The main contents of the paper is an ingenious geometric analysis allowing the authors to overcome these difficulties.

Recommendations

Cites work

Cited in

(34)

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)