BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Efficient Algorithms for the Earth Mover's Distance from Average D
 istortion Embeddings - Erik Waingarten (Pennsylvania State University)
DTSTART:20250722T123000Z
DTEND:20250722T132000Z
UID:TALK234601@talks.cam.ac.uk
DESCRIPTION:We give new algorithmic primitives for the&nbsp\;Earth&nbsp\;M
 over's&nbsp\;Distance&nbsp\;(EMD)\, and as a result\, improve the best app
 roximation for nearest neighbor search under EMD by a quadratic factor. He
 re\, 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&nbsp\;distance&nbsp\;EMD(x\,y)
  is the minimum cost of a perfect matching between x\,y\, where the cost o
 f matching two vectors is their \\ell_p&nbsp\;distance. Previously\, Andon
 i\, 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 embedding
 s with distortion \\tilde{O}(log s).&nbsp\;
LOCATION:External
END:VEVENT
END:VCALENDAR