L_1 embeddings of the Heisenberg group and the Sparsest Cut problem

Assaf Naor
New York University

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




Back to Workshop IV: Analytical Methods in Combinatorics, Additive Number Theory and Computer Science