Title: Bi-Lipschitz embedding in Banach spaces, Rademacher-type theorems, and functions of bounded variation

Abstract: A mapping between metric spaces is L-bi-Lipschitz if it stretches distances by a factor of at most L, and compresses them by a factor no worse than 1/L. A basic problem in geometric analysis is to determine when one metric space can be bi-Lipschitz embedded in another, and if so, to estimate the optimal bi-Lipschitz constant. In recent years this question has generated great interest in computer science, since many data sets can be represented as metric spaces, and associated algorithms can be simplified, improved, or estimated, provided one knows that the metric space space in question can be bi-Lipschitz embedded (with controlled bi-Lipschitz constant) in a nice space, such as L^2 or L^1.
The lecture will discuss several new existence and non-existence results for bi-Lipschitz embeddings in Banach spaces. One approach to non-existence theorems is based on generalized differentiation theorems in the spirit of Rademacher's theorem on the almost everywhere differentiability of Lipschitz functions on R^n. We first show that earlier differentiation based results of Pansu and Cheeger, which proved non-existence of embeddings into R^k, generalize to many Banach space targets, such as L^p, for 1 < p < infinity. We then focus on the case when the target is L^1, where differentiation theory is known to fail, and the embedding questions are of particular interest in computer science. When the domain is the Heisenberg group with its Carnot-Caratheodory metric, we show that a modified form of differentiation still holds for Lipschitz maps into L^1, by exploiting a new connection with functions of bounded variation, and some very recent advances in geometric measure theory. This lead to a proof of a conjecture of Assaf Naor.
This is joint work with Jeff Cheeger.