$L_1$ embeddings of the Heisenberg group and fast estimation of graph isoperimetry

Assaf Naor, New York University
Fine Hall 314

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. Joint work with Jeff Cheeger and Bruce Kleiner