## 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

#### Summary

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

- First version posted:
Feb. 2016.
- Revisions: none yet.

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