University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Efficient Algorithms for the Earth Mover's Distance from Average Distortion Embeddings

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

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

Download to your calendar using vCal

  • UserErik Waingarten (Pennsylvania State University)
  • ClockTuesday 22 July 2025, 13:30-14:20
  • HouseExternal.

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(Rd,\ell_p) consists of sets of s vectors in Rd, 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:

Note that ex-directory lists are not shown.

Other lists

Hybrid: in-person in Cambridge & online via Teams Rayleigh Seminar Room, Maxwell Building Cambridge Carbon Footprint

Other talks

Caribbean Trip and Cacti Director's Briefing Scattering Plenty: the people who made the modern countryside Discovery Investigations: Science, Empire and the Making of the British South Atlantic Cambridge RNA Club - ONLINE Secrets of the Surface: The Mathematical Vision of Maryam Mirzakhani ( EDI Film Screening)
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity