Computer Science/Discrete Mathematics Seminar II

The Lipschitz extension problem is the following basic “meta question” in metric geometry:  Suppose that X and Y are metric spaces and A is a subset of X. What is the smallest K such that every Lipschitz function f:A\to Y has an extension F:X\to Y whose Lipschitz constant is at most K times the Lipschitz constant of f. Such extension phenomena are rare, but when they are available they are useful for various applications, ranging from pure mathematics to approximation theory and algorithms. The Lipschitz extension problem has attracted the efforts of many mathematicians over the past century, and the known results introduced a variety of valuable ideas. In this talk we will explain some of the main achievements,  ideas, challenges and mysteries in this direction, as well as recent advances (both recently published and forthcoming). Among the topics that we will cover are connections to clustering, dual formulations, relations to reverse isoperimetry, and approximate versions.