On the relation between the relative earth mover distance and the variation distance (an exposition)

Webpage for an exposition by Oded Goldreich and Dana Ron


In this note we present a proof that the variation distance up to relabeling is upper-bounded by the ``relative earth mover distance'' (to be defined below). The relative earth mover distance was introduced by Valiant and Valiant (2011), and was extensively used in their work. The foregoing claim was made in [VV11], but was not used there. The claim appears a special case of Fact 1 (i.e., the case of $\tau=0$) in Valiant and Valiant (2015). The proof we present is merely an elaboration of (this special case of) the proof presented by Valiant and Valiant in Appendix A of [VV15].

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.