PACM Colloquium: Assaf Naor, Mathematics - Princeton University

PACM Colloquium
Apr 11, 2022
4:30 pm
214 Fine Hall (In Person - Princeton ID Holders Only)

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

All attendees must be masked upon entry.

Randomized clustering in high dimensions

Abstract: 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.

Bio: Assaf Naor, has  been a faculty member here at the Princeton mathematics department since 2014, after being at the Courant Institute (2007-2014) and Microsoft Research (2002-2007). He is interested in analysis and geometry, as well as their impact on other areas which include understanding the possibilities and limitations of algorithms.