Sublinear Time Algorithms for Earth Mover's Distance

Khanh Do Ba, Huy L Nguyen, Huy N Nguyen +1

We study the problem of estimating the Earth Mover's Distance (EMD) between probability distributions when given access only to samples. We give closeness testers and additive-erro…