{"ID":2867415,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.19598","arxiv_id":"2509.19598","title":"Efficient $\\varepsilon$-approximate minimum-entropy couplings","abstract":"Given $m \\ge 2$ discrete probability distributions over $n$ states each, the minimum-entropy coupling is the minimum-entropy joint distribution whose marginals are the same as the input distributions. Computing the minimum-entropy coupling is NP-hard, but there has been significant progress in designing approximation algorithms; prior to this work, the best known polynomial-time algorithms attain guarantees of the form $H(\\operatorname{ALG}) \\le H(\\operatorname{OPT}) + c$, where $c \\approx 0.53$ for $m=2$, and $c \\approx 1.22$ for general $m$ [CKQGK '23]. A main open question is whether this task is APX-hard, or whether there exists a polynomial-time approximation scheme (PTAS). In this work, we design an algorithm that produces a coupling with entropy $H(\\operatorname{ALG}) \\le H(\\operatorname{OPT}) + \\varepsilon$ in running time $n^{O(\\operatorname{poly}(1/\\varepsilon) \\cdot \\operatorname{exp}(m) )}$: showing a PTAS exists for constant $m$.","short_abstract":"Given $m \\ge 2$ discrete probability distributions over $n$ states each, the minimum-entropy coupling is the minimum-entropy joint distribution whose marginals are the same as the input distributions. Computing the minimum-entropy coupling is NP-hard, but there has been significant progress in designing approximation a...","url_abs":"https://arxiv.org/abs/2509.19598","url_pdf":"https://arxiv.org/pdf/2509.19598v2","authors":"[\"Spencer Compton\"]","published":"2025-09-23T21:44:54Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"cs.DS\"]","methods":"[]","has_code":false}