  Multimarginal Optimal Transport (MOT) is the problem of linear programming
over joint probability distributions with fixed marginals. A key issue in many
applications is the complexity of solving MOT: the linear program has
exponential size in the number of marginals k and their support sizes n. A
recent line of work has shown that MOT is poly(n,k)-time solvable for certain
families of costs that have poly(n,k)-size implicit representations. However,
it is unclear what further families of costs this line of algorithmic research
can encompass. In order to understand these fundamental limitations, this paper
initiates the study of intractability results for MOT.
  Our main technical contribution is developing a toolkit for proving
NP-hardness and inapproximability results for MOT problems. We demonstrate this
toolkit by using it to establish the intractability of a number of MOT problems
studied in the literature that have resisted previous algorithmic efforts. For
instance, we provide evidence that repulsive costs make MOT intractable by
showing that several such problems of interest are NP-hard to solve--even
approximately.
