Geometric Analysis and Topology Seminar

---

Distortion of Embeddings of Transportation Cost Spaces on Recursive Families of Graphs into $L_1$

Speaker: Mikhail Ostrovskii, St. John's University

Location: Warren Weaver Hall 512

Date: Friday, October 31, 2025, 11 a.m.

Synopsis:

Computer Scientists (Charikar, Indyk, Thaper) noticed that one of the useful ways for studying Transportation Cost on finite metric spaces is by using a low-distortion embedding of TC(X) (transportation cost space) into L₁. It is known (Charikar (2002), Fakcharoenphol-Rao-Talwar (2004)) that the distortion is at most O(log n).

It is a natural question to check whether this estimate can be improved for natural families of graphs known to admit low-distortion embeddings into L₁.  We develop a method that shows that the log n-estimate cannot be improved for many families of graphs, including such recursive families as diamond and Laakso graphs. (Based on a joint paper with Chris Gartland)