IDEAL Workshop: Assaf Naor, Randomized clustering in high dimensions

The separation modulus of a metric space M is the smallest positive S such that for every positive D there exists a random partition of M into clusters of diameter at most D such that for any two points in M the probability that they belong to different clusters is at most their distance times (S/D). By relating it to well-studied volumetric quantities such as volume ratios and projection bodies, we will obtain asymptotic evaluations of the separation modulus for many high-dimensional normed spaces and their subsets. We will show how these bounds can be used to make progress on classical questions on the extension of Lipschitz functions, and how they relate to the question of reversing the classical isoperimetric inequality.