# Discrete Optimal Transport with Independent Marginals is #P-Hard

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 79 references that are in the map.
- First posted on arXiv 2 Mar 2022.

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

- [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)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Large-Scale Optimal Transport and Mapping Estimation](https://mlsanity.com/paper/1711.02283/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Sliced Wasserstein Kernel for Persistence Diagrams](https://mlsanity.com/paper/1706.03358/) (2017)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [Regularized Optimal Transport and the Rot Mover's Distance](https://mlsanity.com/paper/1610.06447/) (2016)
- [Quadratically-Regularized Optimal Transport on Graphs](https://mlsanity.com/paper/1704.08200/) (2017)
- [Tsallis Regularized Optimal Transport and Ecological Inference](https://mlsanity.com/paper/1609.04495/) (2016)
- [Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling](https://mlsanity.com/paper/1801.02790/) (2018)
- [Hardness results for Multimarginal Optimal Transport problems](https://mlsanity.com/paper/2012.05398/) (2020)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Towards Optimal Running Times for Optimal Transport](https://mlsanity.com/paper/1810.07717/) (2018)
- [Approximating optimal transport with linear programs](https://mlsanity.com/paper/1810.05957/) (2018)
- [Greedy stochastic algorithms for entropy-regularized optimal transport problems](https://mlsanity.com/paper/1803.01347/) (2018)
- [Wasserstein Distance to Independence Models](https://mlsanity.com/paper/2003.06725/) (2020)
- [Worst-Case Expected Shortfall with Univariate and Bivariate Marginals](https://mlsanity.com/paper/1701.04167/) (2017)
- [Convex Histogram-Based Joint Image Segmentation with Regularized Optimal Transport Cost](https://mlsanity.com/paper/1610.01400/) (2016)

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

- [Quantum Theory and Application of Contextual Optimal Transport](https://mlsanity.com/paper/2402.14991/) (2024)
- [Optimal Transport for ε-Contaminated Credal Sets: To the Memory of Sayan Mukherjee](https://mlsanity.com/paper/2410.03267/) (2024)
- [PeTeR: Post-Training Robustification of Probabilistic Circuits](https://mlsanity.com/paper/2607.07671/) (2026)

## Abstract (arXiv)

We study the computational complexity of the optimal transport problem that evaluates the Wasserstein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in the maximum of the number of atoms of the two distributions. However, if the components of either random vector are independent, then this number can be exponential in K even though the size of the problem description scales linearly with K. We prove that the described optimal transport problem is #P-hard even if all components of the first random vector are independent uniform Bernoulli random variables, while the second random vector has merely two atoms, and even if only approximate solutions are sought. We also develop a dynamic programming-type algorithm that approximates the Wasserstein distance in pseudo-polynomial time when the components of the first random vector follow arbitrary independent discrete distributions, and we identify special problem instances that can be solved exactly in strongly polynomial time.