Jul 24, 2025
TCS Seminar – Approximating Earth Mover’s Distance in Sublinear Time
Date: July 24, 2025 |
11:00 am –
12:00 pm
Speaker:
Lorenzo Beretta, University of California, Santa Cruz
Location: Moonstone Bldg / Ground floor / Seminar Room G (I24.EG.030g)
Language:
English
This talk explores the complexity of approximating the Earth Mover's Distance (EMD), a widely used similarity measure for subsets of a metric space. Over the past two decades, the use of Optimal Transport and the corresponding EMD metric have enjoyed significant adoption in the ML community. On the other hand, the complexity of approximating EMD remains unclear.
In this talk, we present recent algorithmic results on the trade-offs between approximation and running time for general metrics, as well as for more structured norms like $\ell_1$ and $\ell_2$. Notably, these results draw from two distinct areas: sublinear-time matching algorithms and high-dimensional computational geometry.
This talk is based on joint works with Vincent Cohen-Addad, Rajesh Jayaram, Aviad Rubinstein, and Erik Waingarten.
