  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\'eodory geometry
with the geometry of the Lebesgue space $L_1$.
