Wasserstein barycenters are NP-hard to compute
  Computing Wasserstein barycenters (a.k.a. Optimal Transport barycenters) is a
fundamental problem in geometry which has recently attracted considerable
attention due to many applications in data science. While there exist
polynomial-time algorithms in any fixed dimension, all known running times
suffer exponentially in the dimension. It is an open question whether this
exponential dependence is improvable to a polynomial dependence. This paper
proves that unless P=NP, the answer is no. This uncovers a "curse of
dimensionality" for Wasserstein barycenter computation which does not occur for
Optimal Transport computation. Moreover, our hardness results for computing
Wasserstein barycenters extend to approximate computation, to seemingly simple
cases of the problem, and to averaging probability distributions in other
Optimal Transport metrics.
