Harald Bohr Lecture: Assaf Naor

Speaker: Assaf Naor (Professor, Princeton University, Ostrowski Prize, 2019)

Title: The story of the Sparsest Cut Problem.

Abstract: By John's theorem, any k-dimensional normed space embeds with distortion at most k^{1/2} into a Hilbert space: Is there an analog of this phenomenon for metric spaces? The surface measure on the Euclidean n-sphere is highly concentrated: Can a reasonable n-dimensional metric measure space be more concentrated than that sphere? Given a finite collection of objects with pairwise interactions between them, can one find in polynomial time a bipartition that approximately minimizes its interface? Is there an intrinsic characterization of those metric spaces that are bi-Lipschitz deformations of subsets of Euclidean space? These four topics have been studied for decades from separate perspectives and by different communities, but it turns out that they are intertwined. This talk will explain how they are related, and will feature recent answers to some central issues, though by and large they remain huge mysteries.