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

[Dan Michael Stubbs]

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!


-dan

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20151008/29f5e2ba/attachment.html>