L1 Embeddings of the Heisenberg Group and Fast Estimation of Graph Isoperimetry

摘要

We survey connections between the theory of bi-Lipschitz embeddings and theSparsest Cut Problem in combinatorial optimization. The story of the Spars-est Cut Problem is a striking example of the deep interplay between analysis,geometry, and probability on the one hand, and computational issues in dis-crete mathematics on the other. We explain how the key ideas evolved over thepast 20 years, emphasizing the interactions with Banach space theory, geomet-ric measure theory, and geometric group theory. As an important illustrativeexample, we shall examine recently established connections to the the structureof the Heisenberg group, and the incompatibility of its Carnot-Caratheodorygeometry with the geometry of the Lebesgue space L_1.