Randomized clustering in high dimensions

-
Assaf Naor, Princeton University
Fine Hall 214

This event is in-person and open only to Princeton University ID holders

For this particular event “All attendees must be masked upon entry.”

The separation modulus of a metric space M is the smallest S>0 such that for every D>0 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). This fundamental clustering problem has a variety of applications in algorithms and pure mathematics and in this talk we will study it for subsets of high dimensional normed spaces. By relating it to classical volumetric quantities such as volume ratios and projection bodies, we will obtain asymptotic evaluations of the separation modulus for many classical spaces. We will show how these bounds can be used to obtain progress on classical questions on the extension of Lipschitz functions, and how they relate to the question of reversing the classical isoperimetric inequality.