  The problem of computing Wasserstein barycenters (a.k.a. Optimal Transport
barycenters) has attracted considerable recent attention due to many
applications in data science. While there exist polynomial-time algorithms in
any fixed dimension, all known runtimes 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.
