The algebraic degree of the Wasserstein distance
Chiara Meroni, Bernhard Reinke, Kexin Wang · Acta Universitatis Sapientiae Mathematica · 2025
Given two rational univariate polynomials, the Wasserstein distance of their associated measures is an algebraic number. We determine the algebraic degree of the squared Wasserstein distance, serving as a measure of algebraic complexity of the corresponding optimization problem. The computation relies on Galois theory and on the combinatorial structure of a specific subpolytope of the Birkhoff polytope, invariant under a transformation induced by complex conjugation. Proofs and computations also draw on notions from graph theory and elimination ideals.