BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20250330T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20251026T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260424T040646Z
UID:686b78b449c2b453046602@ist.ac.at
DTSTART:20250724T110000
DTEND:20250724T120000
DESCRIPTION:Speaker: Lorenzo Beretta\nAbstract: This talk explores the comp
 lexity of approximating the Earth Mover's Distance (EMD)\, a widely used s
 imilarity measure for subsets of a metric space. Over the past two decades
 \, the use of Optimal Transport and the corresponding EMD metric have enjo
 yed significant adoption in the ML community. On the other hand\, the comp
 lexity of approximating EMD remains unclear.In this talk\, we present rece
 nt algorithmic results on the trade-offs between approximation and running
  time for general metrics\, as well as for more structured norms like $\\e
 ll_1$ and $\\ell_2$. Notably\, these results draw from two distinct areas:
  sublinear-time matching algorithms and high-dimensional computational geo
 metry.This talk is based on joint works with Vincent Cohen-Addad\, Rajesh 
 Jayaram\, Aviad Rubinstein\, and Erik Waingarten.
LOCATION:Moonstone Bldg / Ground floor / Seminar Room G (I24.EG.030g)\, IST
 A
ORGANIZER:nhahn@ist.ac.at
SUMMARY:Lorenzo Beretta: TCS Seminar - Approximating Earth Mover's Distance
  in Sublinear Time
URL:https://talks-calendar.ista.ac.at/events/5912
END:VEVENT
END:VCALENDAR