loading...
Lp metrics on the Heisenberg group and the Goemans-Linial conjecture
Berkeley, California October 21-October 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.4747th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
James R. Lee, Institute for Advanced Study, USA
Assaf Naor, Microsoft Research
We prove that the function d : \mathbb{R}^3 \times \mathbb{R}^3 \to [0,\infty ) given by d\left( {(x,y,z),(t,u,v)} \right)= \left( {[((t - x)^2 + (u - y)^2 )^2 + (v - z + 2xu - 2yt)^2 ]^{\frac{1} {2}} + (t - x)^2 + (u - y)^2 } \right)^{\frac{1} {2}} . is a metric on \mathbb{R}^3 such that (\mathbb{R}^3, \sqrt d ) is isometric to a subset of Hilbert space, yet (\mathbb{R}^3, d) does not admit a bi-Lipschitz embedding into L_1. This yields a new simple counter example to the Goemans-Linial conjecture on the integrality gap of the semidefinite relaxation of the Sparsest Cut problem. The metric above is doubling, and hence has a padded stochastic decomposition at every scale. We also study the L_p version of this problem, and obtain a counter example to a natural generalization of a classical theorem of Bretagnolle, Dacunha-Castelle and Krivine (of which the Goemans-Linial conjecture is a particular case). Our methods involve Fourier analytic techniques, and a recent breakthrough of Cheeger and Kleiner, together with classical results of Pansu on the differentiability of Lipschitz functions on the Heisenberg group.
Citation:
James R. Lee, Assaf Naor, "Lp metrics on the Heisenberg group and the Goemans-Linial conjecture," focs, pp.99-108, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.