TY - GEN

T1 - Lp metrics on the Heisenberg group and the Goemans-Linial conjecture

AU - Lee, James R.

AU - Naor, Assaf

PY - 2006/12/1

Y1 - 2006/12/1

N2 - We prove that the function d : R3 x R3 → [0, ∞) given by d((x, y, z), (t, u, v)) = ( [((i - x)2 + (u - y)2f +(v - z + 2xu - 2yt)2]1/2 + (t - x) 2 + (u - y)2)1/2. is a metric on ℝ3 such that (ℝ3, √d) is isometric to a subset of Hubert space, yet (R3, d) does not admit a bi-Lipschitz embedding into L1. 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 Lp 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.

AB - We prove that the function d : R3 x R3 → [0, ∞) given by d((x, y, z), (t, u, v)) = ( [((i - x)2 + (u - y)2f +(v - z + 2xu - 2yt)2]1/2 + (t - x) 2 + (u - y)2)1/2. is a metric on ℝ3 such that (ℝ3, √d) is isometric to a subset of Hubert space, yet (R3, d) does not admit a bi-Lipschitz embedding into L1. 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 Lp 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.

UR - http://www.scopus.com/inward/record.url?scp=38749129134&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38749129134&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2006.47

DO - 10.1109/FOCS.2006.47

M3 - Conference contribution

AN - SCOPUS:38749129134

SN - 0769527205

SN - 9780769527208

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 99

EP - 108

BT - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

T2 - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

Y2 - 21 October 2006 through 24 October 2006

ER -