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


Assaf Naor


Harvard University

Thursday, April 8, 2010


Talk at 4:30 p.m. in Science Center D

Tea at 4:00 p.m. in the Math Lounge


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.

Joint work with Jeff Cheeger and Bruce Kleiner


Home Web page:  Alexandru I. Suciu   Comments to:  
Posted: March 30, 2010    URL: