Efficient Algorithms for the Earth Mover's Distance from Average Distortion Embeddings

Add to your list(s) Download to your calendar using vCal

• Erik Waingarten (Pennsylvania State University)
• Tuesday 22 July 2025, 13:30-14:20
• External.

If you have a question about this talk, please contact nobody.

OGGW05 - Geometric and combinatorial methods in the foundations of computer science and artificial intelligence

We give new algorithmic primitives for the Earth Mover’s Distance (EMD), and as a result, improve the best approximation for nearest neighbor search under EMD by a quadratic factor. Here, the metric EMD _s(R^{d,\ell_p) consists of sets of s vectors in R}d, and for any two sets x,y of s vectors the distance  EMD is the minimum cost of a perfect matching between x,y, where the cost of matching two vectors is their \ell_p distance. Previously, Andoni, Indyk, and Krauthgamer gave a bi-Lipschitz embedding of EMD _s([Delta]^d,\ell_p) when p in [1,2] to l_1 with approximation O(log s log(dDelta)). By using “data-dependent” trees, we give average-distortion embeddings with distortion \tilde{O}(log s). 

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• External
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.