Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 10/8/15 with Dan Stubbs at 12:30pm

Dan Michael Stubbs dstubbs at
Wed Oct 7 23:15:43 PDT 2015

Greetings lunch and TCS enthusiasts,

There will be a theory lunch tomorrow, with food starting at 12:15pm and theory starting at 12:30pm.

I'll be speaking about linear sketches for the Earth Mover Distance problem when the distance metric is defined by a graph.  The Earth Mover Distance problem asks, for a given pair of point sets, what the weight of the lowest cost matching is between them -- intuitively, it asks how much mileage you'd have to pay notional "point bulldozers" to push one point set to the other, given optimal planning.  The one-dimensional case has a simple reduction to L1-estimation; we use a bag of tricks to reduce the problem on simple cycles, trees, and general graphs to this case while trying not to pay too much overhead in space usage.  This is joint work with Andrew McGregor, done while we were both at UMass Amherst.

Hope to see you there!


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list