The algebraic degree of the Wasserstein distance
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.
Authors
- Bernhard Reinke (ORCID: https://orcid.org/0000-0001-9024-2449)
- Chiara Meroni (ORCID: https://orcid.org/0000-0002-3992-4345)
- Kexin Wang (ORCID: https://orcid.org/0000-0002-9064-1316)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Aix-Marseille Université (FR)
- Harvard University Press (US)
- ETH Zurich (CH)
- Max Planck Institute for Mathematics in the Sciences (DE)
- Institut Polytechnique de Bordeaux (FR)
Publication Details
- Journal
- Acta Universitatis Sapientiae Mathematica
- Published
- 2025-06-02
- DOI
- https://doi.org/10.1007/s44426-025-00004-0
- Citations
- 1
- Primary Topic
- Polynomial and algebraic computation
- Type
- article
- Field-Weighted Citation Impact
- 1.50