## Abstract

We prove that the function d : R^{3} x R^{3} → [0, ∞) given by d((x, y, z), (t, u, v)) = ( [((i - x)^{2} + (u - y)^{2}f +(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 (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.

Original language | English (US) |
---|---|

Title of host publication | 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 |

Pages | 99-108 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 1 2006 |

Externally published | Yes |

Event | 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, United States Duration: Oct 21 2006 → Oct 24 2006 |

### Publication series

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

ISSN (Print) | 0272-5428 |

### Other

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

Country/Territory | United States |

City | Berkeley, CA |

Period | 10/21/06 → 10/24/06 |

## All Science Journal Classification (ASJC) codes

- Engineering(all)

## Fingerprint

Dive into the research topics of 'L_{p}metrics on the Heisenberg group and the Goemans-Linial conjecture'. Together they form a unique fingerprint.