Analysis Seminar

---

Bounding the Euclidean Distortion of Negative-Type Metric Spaces

Speaker: Kevin Ren, Princeton University

Location: Warren Weaver Hall 1302

Date: Thursday, February 27, 2025, 11 a.m.

Synopsis:

We show that any N-point negative-type metric space admits a bi-Lipschitz embedding into Euclidean space with distortion O(sqrt(log N)), which is sharp up to constant factors. The proof relies on a refined Arora-Rao-Vazirani chaining argument and a novel metric compression scheme, with new implications for concentration of measure and the Sparsest Cut problem. Joint work with Assaf Naor and Alan Chang.