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

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 $L_1$.

arXiv commentTo appear in Proceedings of the International Congress of Mathematicians, Hyderabad India, 2010

References in corpus (1)

• Compression bounds for Lipschitz maps from the Heisenberg group to $L_1$

Cited by in corpus (7)

• Distance covariance in metric spaces
• Nonlinear spectral calculus and super-expanders
• Expanders with respect to Hadamard spaces and random graphs
• Sparse quadratic forms and their geometric applications (after Batson, Spielman and Srivastava)
• On the coarse geometry of James spaces
• Nonparametric independence tests in metric spaces: What is known and what is not
• Vertical versus horizontal Poincaré inequalities on the Heisenberg group