Brandeis-Harvard-MIT-Northeastern

JOINT MATHEMATICS COLLOQUIUM


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

 

Assaf Naor

NYU
 

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:  a.suciu@neu.edu  
Posted: March 30, 2010    URL: http://www.math.neu.edu/bhmn/naor10.html