L₁ Embeddings of the Heisenberg Group and Fast Estimation of Graph Isoperimetry

Abstract

Proceedings of the International Congress of Mathematicians 2010 (ICM 2010), pp. 1549-1575 (2011) No AccessL1 Embeddings of the Heisenberg Group and Fast Estimation of Graph IsoperimetryAssaf NaorAssaf NaorNew York University, Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012, USAResearch supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.https://doi.org/10.1142/9789814324359_0110Cited by:3 PreviousNext AboutSectionsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail Abstract: We survey connections between the theory of bi-Lipschitz embeddings and the Sparsest Cut Problem in combinatorial optimization. The story of the Sparsest Cut Problem is a striking example of the deep interplay between analysis, geometry, and probability on the one hand, and computational issues in discrete mathematics on the other. We explain how the key ideas evolved over the past 20 years, emphasizing the interactions with Banach space theory, geometric measure theory, and geometric group theory. As an important illustrative example, we shall examine recently established connections to the the structure of the Heisenberg group, and the incompatibility of its Carnot-Carathéodory geometry with the geometry of the Lebesgue space L1. Keywords: Bi-Lipschitz embeddingsSparsest Cut ProblemHeisenberg groupAMSC: 46B85, 30L05, 46B80, 51F99 FiguresReferencesRelatedDetailsCited By 3DISTORTION IN THE FINITE DETERMINATION RESULT FOR EMBEDDINGS OF LOCALLY FINITE METRIC SPACES INTO BANACH SPACESS. OSTROVSKA and M. I. OSTROVSKII6 February 2018 | Glasgow Mathematical Journal, Vol. 61, No. 1Low-distortion embeddings of graphs with large girthMikhail I. Ostrovskii1 Apr 2012 | Journal of Functional Analysis, Vol. 262, No. 8On the Unique Games Conjecture (Invited Survey)Subhash Khot1 Jun 2010 Proceedings of the International Congress of Mathematicians 2010 (ICM 2010)Metrics History KeywordsBi-Lipschitz embeddingsSparsest Cut ProblemHeisenberg groupPDF download

Locations

• arXiv (Cornell University) - View - PDF
• Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) - View