L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry |
Abstract:
We will show that any L_1-valued mapping of an epsilon net in the
unit ball of the Heisenberg group incurs bi-Lipschitz distortion
(log(1/epsilon))^c, where c is a universal constant. We will also explain
how this result implies an exponential improvement to the best known
integrality gap for the Goemans-Linial semidefinite relaxation of the
Sparsest Cut problem. |
Web page: Alexandru I. Suciu | Comments to: a.suciu@neu.edu | |
Posted: March 30, 2010 | URL: http://www.math.neu.edu/bhmn/naor10.html |