  The Earth Mover Distance (EMD) between two sets of points $A, B \subseteq
\mathbb{R}^d$ with $|A| = |B|$ is the minimum total Euclidean distance of any
perfect matching between $A$ and $B$. One of its generalizations is asymmetric
EMD, which is the minimum total Euclidean distance of any matching of size
$|A|$ between sets of points $A,B \subseteq \mathbb{R}^d$ with $|A| \leq |B|$.
The problems of computing EMD and asymmetric EMD are well-studied and have many
applications in computer science, some of which also ask for the EMD-optimal
matching itself. Unfortunately, all known algorithms require at least quadratic
time to compute EMD exactly. Approximation algorithms with nearly linear time
complexity in $n$ are known (even for finding approximately optimal matchings),
but suffer from exponential dependence on the dimension.
  In this paper we show that significant improvements in exact and approximate
algorithms for EMD would contradict conjectures in fine-grained complexity. In
particular, we prove the following results:
  (1) Under the Orthogonal Vectors Conjecture, there is some $c>0$ such that
EMD in $\Omega(c^{\log^* n})$ dimensions cannot be computed in truly
subquadratic time.
  (2) Under the Hitting Set Conjecture, for every $\delta>0$, no truly
subquadratic time algorithm can find a $(1 + 1/n^\delta)$-approximate EMD
matching in $\omega(\log n)$ dimensions.
  (3) Under the Hitting Set Conjecture, for every $\eta = 1/\omega(\log n)$, no
truly subquadratic time algorithm can find a $(1 + \eta)$-approximate
asymmetric EMD matching in $\omega(\log n)$ dimensions.
