# Wasserstein barycenters are NP-hard to compute

arXiv: https://arxiv.org/abs/2101.01100 · HTML: https://mlsanity.com/paper/2101.01100/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 4 Jan 2021.

## Builds on (most cited first, 27 of 27)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Statistical Aspects of Wasserstein Distances](https://mlsanity.com/paper/1806.05500/) (2018)
- [Multilevel Clustering via Wasserstein Means](https://mlsanity.com/paper/1706.03883/) (2017)
- [Scalable Bayes via Barycenter in Wasserstein Space](https://mlsanity.com/paper/1508.05880/) (2015)
- [Debiased Sinkhorn barycenters](https://mlsanity.com/paper/2006.02575/) (2020)
- [Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support](https://mlsanity.com/paper/1510.00012/) (2015)
- [Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm](https://mlsanity.com/paper/2002.04783/) (2020)
- [Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm](https://mlsanity.com/paper/1905.13194/) (2019)
- [Fast Optimal Transport Averaging of Neuroimaging Data](https://mlsanity.com/paper/1503.08596/) (2015)
- [Wasserstein barycenters can be computed in polynomial time in fixed dimension](https://mlsanity.com/paper/2006.08012/) (2020)
- [Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data](https://mlsanity.com/paper/1507.07218/) (2015)
- [Distilled Wasserstein Learning for Word Embedding and Topic Modeling](https://mlsanity.com/paper/1809.04705/) (2018)
- [Estimating Barycenters of Measures in High Dimensions](https://mlsanity.com/paper/2007.07105/) (2020)
- [Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure](https://mlsanity.com/paper/2008.03006/) (2020)
- [Parallel Streaming Wasserstein Barycenters](https://mlsanity.com/paper/1705.07443/) (2017)
- [Multi-marginal optimal transport and probabilistic graphical models](https://mlsanity.com/paper/2006.14113/) (2020)
- [Hardness results for Multimarginal Optimal Transport problems](https://mlsanity.com/paper/2012.05398/) (2020)
- [Context Mover's Distance & Barycenters: Optimal Transport of Contexts for Building Representations](https://mlsanity.com/paper/1808.09663/) (2018)
- [Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm](https://mlsanity.com/paper/1710.08234/) (2017)
- [An entropy minimization approach to second-order variational mean-field games](https://mlsanity.com/paper/1807.09078/) (2018)
- [Sinkhorn Barycenter via Functional Gradient Descent](https://mlsanity.com/paper/2007.10449/) (2020)
- [On the Computational Complexity of Finding a Sparse Wasserstein Barycenter](https://mlsanity.com/paper/1910.07568/) (2019)
- [Probabilistic Multilevel Clustering via Composite Transportation Distance](https://mlsanity.com/paper/1810.11911/) (2018)
- [An LP-based, Strongly-Polynomial 2-Approximation Algorithm for Sparse Wasserstein Barycenters](https://mlsanity.com/paper/1704.05491/) (2017)
- [On the Complexity of Approximating Wasserstein Barycenter](https://mlsanity.com/paper/1901.08686/) (2019)

## Built on by (most cited first, 28 of 28)

- [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [RegGS: Unposed Sparse Views Gaussian Splatting with 3DGS Registration](https://mlsanity.com/paper/2507.08136/) (2025)
- [Energy-Guided Continuous Entropic Barycenter Estimation for General Costs](https://mlsanity.com/paper/2310.01105/) (2023)
- [Trajectory Inference with Smooth Schr"odinger Bridges](https://mlsanity.com/paper/2503.00530/) (2025)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [Simultaneous linear connectivity of neural networks modulo permutation](https://mlsanity.com/paper/2404.06498/) (2024)
- [Projection Robust Wasserstein Barycenters](https://mlsanity.com/paper/2102.03390/) (2021)
- [ExGra-Med: Extended Context Graph Alignment for Medical Vision-Language Models](https://mlsanity.com/paper/2410.02615/) (2024)
- [Sliced Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2102.07115/) (2021)
- [Sampling From the Wasserstein Barycenter](https://mlsanity.com/paper/2105.01706/) (2021)
- [An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification](https://mlsanity.com/paper/2401.09191/) (2024)
- [Discrete Optimal Transport with Independent Marginals is #P-Hard](https://mlsanity.com/paper/2203.01161/) (2022)
- [Wasserstein Distributionally Robust Optimization with Wasserstein Barycenters](https://mlsanity.com/paper/2203.12136/) (2022)
- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [Distributional Matrix Completion via Nearest Neighbors in the Wasserstein Space](https://mlsanity.com/paper/2410.13112/) (2024)
- [Multi-Output Distributional Fairness via Post-Processing](https://mlsanity.com/paper/2409.00553/) (2024)
- [Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysis](https://mlsanity.com/paper/2505.13660/) (2025)
- [Schr"odinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres](https://mlsanity.com/paper/2506.17197/) (2025)
- [Finite sample bounds for barycenter estimation in geodesic spaces](https://mlsanity.com/paper/2502.14069/) (2025)
- [Wasserstein Gradient Flows for Scalable and Regularized Barycenter Computation](https://mlsanity.com/paper/2510.04602/) (2025)
- [Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs](https://mlsanity.com/paper/2603.26940/) (2026)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)
- [Computational Guarantees for Doubly Entropic Wasserstein Barycenters via Damped Sinkhorn Iterations](https://mlsanity.com/paper/2307.13370/) (2023)
- [Kullback-Leibler Barycentre of Stochastic Processes](https://mlsanity.com/paper/2407.04860/) (2024)
- [Differentiable Expectation-Maximisation and Applications to Gaussian Mixture Model Optimal Transport](https://mlsanity.com/paper/2509.02109/) (2025)
- [Optimal Transport for Efficient, Unsupervised Anomaly Detection on Industrial Data](https://mlsanity.com/paper/2609.13940/) (2026)

## Abstract (arXiv)

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.