Efficient $\varepsilon$-approximate minimum-entropy couplings

Spencer Compton

REVIEW 2 major objections 3 minor 40 references

Efficient $\varepsilon$-approximate minimum-entropy couplings

T0 review · 2 major / 3 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that minimum-entropy coupling admits a polynomial-time approximation scheme (PTAS) for any fixed number of input distributions.

desk verdict First PTAS for minimum-entropy coupling for constant m, a real result, but the key splitting invariant is only sketched and needs a full proof. read the letter →

arxiv 2509.19598 v3 pith:73JG6VT5 submitted 2025-09-23 cs.IT cs.DSmath.IT

Spencer Compton This is my paper · ORCID

classification cs.ITcs.DSmath.IT MSC 68W2594A17

keywords minimum-entropycouplingPTASpolynomial-timeapproximationschemeadditiveepsilondynamicprogramminggridroundingstatesplittingAPX-hardness

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Minimum-entropy coupling asks for the least-random joint distribution whose marginals match given input distributions; the problem is NP-hard, and the best prior polynomial-time algorithms left a constant additive gap in entropy. This paper establishes that for any fixed number m of input distributions, the gap can be made smaller than any prescribed epsilon: a new algorithm constructs a coupling whose entropy is within epsilon of optimal, in time (n/epsilon)^{O(m^4 2^{6m} log^3(1/epsilon)/epsilon^2)} — polynomial in n when m and epsilon are constant. The method rounds all probability masses to a grid, runs a dynamic program over a sliding window of remaining masses, and splits an oversized state in half whenever it cannot be matched. A charging argument ties the entropy error of every split to mass that is later matched or left over, keeping the total error within epsilon. The result rules out APX-hardness for constant m and makes the achievable polynomial-time guarantee arbitrarily tight.

What carries the argument

The load-bearing object is the rounding grid G_epsilon = {2^{-i} epsilon^j : i in Z, j = 1,...,2/epsilon^2 - 1} intersect (0,1), together with the dynamic program that operates on it. A DP-state is a window [alpha M, M] (with alpha = epsilon^3/2) and counts of the remaining distribution states inside that window. Two transition types drive the algorithm: splitting the largest state M into two copies of M/2, and matching — choosing z in G_epsilon ∩ [epsilon M, M] and decomposing each chosen state x_i via the function Match(z, x_1,...,x_m) into two grid elements that are either zero or at least epsilon^3 M/2. The approximation analysis rests on Claim IV.8, an invariant stating that each distri

What would settle it

Run the algorithm on small instances (m=2, n up to 5) with epsilon=0.1, compute the exact optimum by brute force, and check H(ALG) <= H(OPT)+0.1; simultaneously instrument the DP to record the counts of important and pierced coupling states per distribution state. A single input where the entropy gap exceeds epsilon, or where any state's counts exceed the Claim IV.8 bounds, would refute the central theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem I.1: for any m>=2 and any 0<epsilon<1/2, there is an algorithm that outputs a coupling ALG with H(ALG) <= H(OPT) + epsilon in time (n/epsilon)^{O(m^4 2^{6m} log^3(1/epsilon)/epsilon^2)}. For constant m this is a PTAS — the first polynomial-time algorithms with approximation error below the previous best constants (about 0.53 for m=2 and 1.22 in general). The discovery is a technique as much as a bound: a distinct-values dynamic program, combined with a splitting operation that keeps the state space small, can approximate a concave entropy objective to arbitrary additive precision.

Load-bearing premise

The entire epsilon-guarantee rests on Claim IV.8, the invariant that no distribution state ever accumulates more than 1/(8 epsilon) 'important', 2^{m-1} 'left-pierced', or 2^{m-1} 'right-pierced' coupling states; if a state ever violates that, the charging bound that keeps the total splitting error small no longer goes through.

Editorial extensions

If this is right

For every fixed m, a PTAS exists: the running time is polynomial in n for any constant epsilon, so the earlier constant-gap barriers (0.53 for m=2, 1.22 in general) are not fundamental.
For constant m the minimum-entropy coupling problem is not APX-hard; the open question is whether a PTAS exists when m grows with n.
The algorithm produces a genuine coupling, not merely a cost estimate: tracing the DP's transitions constructs a joint distribution, and leftover states are finished with a greedy coupling whose entropy stays within the DP's bound.
The supports stay controlled: after preprocessing each distribution has O(n log(1/tau)) states, and the base case handles leftovers efficiently, so the construction is executable in the stated time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One next step, not pursued in the paper, is to test whether the same sliding-window-and-split engine applies to related problems with concave objectives (minimum Rényi-entropy couplings, bottleneck variants); the proof's main ingredients are concavity and a state-count invariant, so a transfer is plausible.
The running time grows doubly exponentially in m (via 2^{6m}), so the PTAS is a feasibility result rather than a practical solver for more than a few distributions; a practical algorithm would likely need a fundamentally different mechanism or a much sharper bound on the invariant.
The Claim IV.8 invariant is the axis on which everything turns; a computational search for instances that concentrate many 'pierced' states in a single distribution state would either confirm the invariant empirically or expose exactly the step that needs a more detailed proof.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague, you should know that this paper makes a serious bid to close a long-standing open question: whether minimum-entropy coupling for constant m admits a PTAS. The answer here is yes, with a running time (n/ε)^{O(m^4 2^{6m} log^3(1/ε)/ε^2)}, which is polynomial in n for constant m and ε. That is a decisive improvement over the previous best additive constants (0.53 for m=2, 1.22 for general m). The result looks credible to me.

What is genuinely new is the algorithmic machinery: a geometric rounding set G_ε, a windowed dynamic program that maintains counts of states in a sliding range, and a splitting operation that keeps the DP state small. The entropy analysis is organized into preprocessing, matching, splitting, and leftover phases, and each has an explicit bound. The matching and preprocessing bounds are straightforward and check out. The splitting analysis is where the real meat is, and it is also where the paper gets thin.

The load-bearing claim is IV.8: at any time, each distribution state has at most 1/(8ε) important, 2^{m-1} left-pierced, and 2^{m-1} right-pierced coupling states. This invariant underwrites Lemma IV.14, which bounds the cost of all splits. The proof of IV.8 is a sketch. The subtle part is the effect of a split by one distribution on the pierced counts of another. The paper argues that a pierced state has near-height at most m−1 and can be split by at most that many other distributions, so the total proliferation is bounded by 2^{m−1}. That is the right intuition, but the argument that the 2^{m−1} bound holds per distribution state, and that the near-height bound survives all the interleaved splits, is not fully written out. For a result of this importance, that needs to be a full induction. I would not be surprised if the gap is repairable; nothing in the sketch signals an actual contradiction.

Two smaller issues. The theorem statement allows any ε < 1/2, but the proof invokes ε′ ≤ 1/(23m·4m) and a power-of-2 requirement; the paper asserts the chosen ε′ satisfies this, and it does, but the verification is omitted. Also, the leftover phase relies on a carefully chosen τ and j; the calculation is dense but appears to be correct. These are minor.

In short, the paper is significant and likely correct. The right outcome is peer review, with a clear request to expand Claim IV.8. I would bring it to a reading group and would cite it if it passes.

Referee Report

2 major / 3 minor

Summary. The paper proposes an ε-additive approximation algorithm for the minimum-entropy coupling of m discrete distributions over n states, with running time (n/ε)^{O(m^4 2^{6m} log^3(1/ε)/ε^2)}. For constant m this is a PTAS, resolving in the positive the open question of whether the problem is APX-hard. The algorithm rounds all masses to a geometric grid G_ε, runs a dynamic program over a sliding window of rounded values, allows splitting the largest remaining state in half, and handles leftover mass by a final greedy coupling. The proof modifies an optimal coupling through four phases—preprocessing, matching, splitting, and leftover—and bounds the entropy increase in each phase. The claimed result would substantially improve on the previous best additive constants (≈0.53 for m=2, ≈1.22 in general).

Significance. If the proof is correct, this is a major advance: it converts a problem with only constant-factor additive approximations into a PTAS for every fixed m, directly addressing the APX-hardness question that has been open in this literature. The algorithmic idea is novel and the paper provides explicit, parameter-free bounds for the main phases, together with a careful choice of the rounding grid and DP parameters. It also honestly notes the impracticality of the resulting running time. The two caveats are that the splitting invariant—the pivot of the entire charging argument—is only sketched, and the support-size bound used for the leftover phase is not justified as written. Both points are load-bearing for the claimed theorem, though both appear repairable.

major comments (2)

[IV.D, Claim IV.8 and Lemma IV.14] The invariant that every distribution state contains at most 1/(8ε) important, 2^{m−1} left-pierced, and 2^{m−1} right-pierced coupling states is the basis for Lemma IV.14, which bounds the total splitting cost. The proof is a sketch: it asserts that an initial pierced state yields at most 2^{m−1} pierced descendants, but it does not carefully track how splits by other distributions affect counts within a single distribution state, nor does it give a full induction for all four type counts. In particular, when p_i splits a coupling state that p_j considers pierced, both parts remain pierced and remain in the same p_j distribution state; this is exactly the mechanism that can increase the pierced count, and the current text does not prove that the resulting states are spread so that no single distribution state exceeds 2^{m−1}. A complete induction is needed before inequality Cost_r ≤ ε2^
[IV.E, support-size bound on SOL′] The leftover analysis multiplies the number of root coupling states C in SOL′ by a per-root error bound. The text bounds C by nm−(m−1)+nm⌈log(1/τ)⌉, citing Lemma 5.1 of [1] and Claim III.3. As written, this is not justified: if SOL′ is obtained by splitting an optimal coupling of the original distributions at every preprocessed marginal state, the number of coupling states can grow multiplicatively. Already for m=2 and n=1, splitting both marginals into k and l pieces can create k·l cells, not k+l−1. The argument should instead apply Lemma 5.1 to the preprocessed distributions, choosing SOL′ as an optimal coupling with support at most the total number of preprocessed states minus (m−1), and use Lemma IV.4 to bound H(SOL′). This is likely fixable, but as written the bound on C—and therefore the final leftover error—does not follow.

minor comments (3)

[IV.F, proof of Theorem I.1] In the display after 'then Eq. (3) ≤ ε·(...)', the right-hand side is bounded by 1; it should be bounded by ε in order to yield the claimed additive guarantee. The subsequent sentence shows the intended meaning.
[IV.E] The phrase 'both series have consecutive ratios of at least 2' does not describe the second series, whose consecutive ratio is 4mε ≤ 1/4. The intended statement is that the second series is bounded by a geometric series with ratio at most 1/4, so that the total is at most twice the first term.
[Fig. 4] The caption contains a typo: 'right-piereced' should be 'right-pierced'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the DP construction and error analysis are self-contained; the sole self-citation supplies an independent structural lemma.

full rationale

The paper's central claim (Theorem I.1) is derived by a constructive dynamic program (Algorithm 3) followed by an approximation analysis that starts from an optimal coupling SOL and explicitly bounds the entropy increase of each modification class (preprocessing, matching, splitting, leftover). The final additive guarantee is a sum of separately proved error terms (Eq. (3)), with no fitted parameter renamed as a prediction and no quantity defined in terms of the quantity it is supposed to estimate. The only place where prior work by the same authors is invoked as a theorem is the support-size bound 'Lemma 5.1 of [1]' used in Section IV.E to bound the number of root coupling states C in SOL'. This is a parameter-free structural statement about minimum-entropy couplings, not about ε-approximation, and it does not assume the target result; it is therefore independent support rather than a circular step. The compressed proof of Claim IV.8 is a potential verification gap—its invariant induction is sketched—but a gap in proof detail is a correctness concern, not an equivalence-by-construction. No equation in the paper reduces to its input, and the PTAS conclusion does not collapse into the assumptions.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim rests on one cited structural result (support-size bound from the author's prior paper), standard entropy facts, and a technical condition on epsilon'. The parameters alpha, tau, j are chosen analytically to balance error terms; they are not fitted to data. No new physical or mathematical entities are introduced; the 'important', 'left-pierced', and 'right-pierced' coupling states are bookkeeping devices in the proof.

free parameters (4)

epsilon' (inner approximation parameter) = power of 2 in [epsilon/(7452m*2^{3m}*log(1/epsilon)), epsilon/(3726m*2^{3m}*log(1/epsilon))]
Chosen analytically to make the total error bound (Eq. 3) <= epsilon; not fitted to data.
alpha (window ratio) = epsilon'^3/2
Chosen so that split pieces a_i, b_i >= epsilon^3*M/2 stay in the window and preserve the DP invariant.
tau (threshold for tiny states) = epsilon'^9/n^6
Chosen to make the leftover entropy bound small while keeping the DP state count polynomial in n.
j (level cutoff in leftover analysis) = smallest integer with 2^{-3mj} < (epsilon'/n)^3
Chosen to split the leftover tree bound into two regimes; technical device in the proof.

assumptions (4)

standard math Shannon entropy is concave, and any coupling's entropy is at most the sum of the marginal entropies.
Used in the base case and in entropy-increase bounds (Corollary IV.3).
domain assumption There exists a minimum-entropy coupling with support size at most nm - (m-1) (Lemma 5.1 of [1]).
Used in Section IV.E to bound the number of nodes in the leftover tree analysis.
domain assumption A valid coupling of the leftover states can be constructed (e.g., greedy coupling of [8]) with entropy bounded by the independent coupling and running time O(m^2 n log n).
Used in the base case of Algorithm 3.
ad hoc to paper The inner parameter satisfies epsilon' <= 1/(2^{3m}*4^m).
Required for Claim IV.7 and for the leftover bound (4m*epsilon <= 1/4); enforced by the choice of epsilon' in Theorem I.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient $\varepsilon$-approximate minimum-entropy couplings." pith.science (2026). https://pith.science/paper/73JG6VT5

@misc{pith2026250919598,
  author       = {Pith},
  title        = {Pith review of: Efficient $\varepsilon$-approximate minimum-entropy couplings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/73JG6VT5}},
  note         = {Machine review of arXiv:2509.19598}
}

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$.

Figures

Figures reproduced from arXiv: 2509.19598 by the authors.

**Figure 1.** Coupling between two distributions p1 = [0.8, 0.15, 0.05] and p2 = [0.25, 0.3, 0.45]. The left half of the figure has a rectangular depiction of the distributions, where the bold borders represent the states of the distributions, and the subdivisions by colors represent states of the coupling. The right half of the figure gives the analogous table view of the coupling [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

**Figure 2.** Depiction of the coupling in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Depiction of how SOL′ is modified during a matching modification. This figure looks at how distribution states Ind1 of p1, and Ind2 of p2, are modified when a coupling state of size q = 0.45 motivates the dynamic program to match with z = 0.36. Ind1 is split into states of size z = 0.36, a1 = 0.07, and b1 = 0.17 (the z state is ignored since it is now fully coupled). Ind2 is split into states of size z = 0.36, a2 = … view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Depiction of how splitting some distribution state of [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

**Figure 5.** Figure 5: Depiction of how a coupling state is modified over time. Nodes in this tree represent a coupling state, and outgoing edges represent when a coupling [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 1 linked inside Pith

[1]

Minimum-entropy coupling approximation guarantees beyond the majorization barrier,

S. Compton, D. Katz, B. Qi, K. Greenewald, and M. Kocaoglu, “Minimum-entropy coupling approximation guarantees beyond the majorization barrier,” inInternational Conference on Artificial Intelligence and Statistics. PMLR, 2023, pp. 10 445–10 469

2023
[2]

Tight results on minimum entropy set cover,

J. Cardinal, S. Fiorini, and G. Joret, “Tight results on minimum entropy set cover,”Algorithmica, vol. 51, no. 1, pp. 49–60, 2008

2008
[3]

On the entropy of couplings,

M. Kova ˇcevi´c, I. Stanojevi ´c, and V . ˇSenk, “On the entropy of couplings,”Information and Computation, vol. 242, pp. 369–382, 2015

2015
[4]

Communicating via markov decision processes,

S. Sokota, C. A. S. De Witt, M. Igl, L. M. Zintgraf, P. Torr, M. Strohmeier, Z. Kolter, S. Whiteson, and J. Foerster, “Communicating via markov decision processes,” inInternational Conference on Machine Learning. PMLR, 2022, pp. 20 314–20 328

2022
[5]

Minimum-entropy couplings and their applications,

F. Cicalese, L. Gargano, and U. Vaccaro, “Minimum-entropy couplings and their applications,”IEEE Transactions on Information Theory, vol. 65, no. 6, pp. 3436–3451, 2019

2019
[6]

Minimum entropy coupling with bottleneck,

R. Ebrahimi, J. Chen, and A. Khisti, “Minimum entropy coupling with bottleneck,”Advances in Neural Information Processing Systems, vol. 37, pp. 59 655–59 688, 2024

2024
[7]

Perfectly secure steganography using minimum entropy coupling,

C. S. de Witt, S. Sokota, J. Z. Kolter, J. Foerster, and M. Strohmeier, “Perfectly secure steganography using minimum entropy coupling,”arXiv preprint arXiv:2210.14889, 2022

arXiv 2022
[8]

Entropic causal inference,

M. Kocaoglu, A. Dimakis, S. Vishwanath, and B. Hassibi, “Entropic causal inference,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 31, no. 1, 2017

2017

Show all 40 references

[9]

Computing low-entropy couplings for large-support distributions,

S. Sokota, D. Sam, C. S. de Witt, S. Compton, J. Foerster, and J. Z. Kolter, “Computing low-entropy couplings for large-support distributions,” in Uncertainty in Artificial Intelligence. PMLR, 2024, pp. 3279–3298

2024
[10]

Entropic causality and greedy minimum entropy coupling,

M. Kocaoglu, A. G. Dimakis, S. Vishwanath, and B. Hassibi, “Entropic causality and greedy minimum entropy coupling,” in2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017, pp. 1465–1469

2017
[11]

Entropic causal inference: Identifiability and finite sample results,

S. Compton, M. Kocaoglu, K. Greenewald, and D. Katz, “Entropic causal inference: Identifiability and finite sample results,”Advances in Neural Information Processing Systems, vol. 33, pp. 14 772–14 782, 2020

2020
[12]

Entropic causal inference: Graph identifiability,

S. Compton, K. Greenewald, D. A. Katz, and M. Kocaoglu, “Entropic causal inference: Graph identifiability,” inInternational Conference on Machine Learning. PMLR, 2022, pp. 4311–4343

2022
[13]

Quantum entropic causal inference,

M. A. Javidian, V . Aggarwal, F. Bao, and Z. Jacob, “Quantum entropic causal inference,” inQuantum Information and Measurement. Optica Publishing Group, 2021, pp. F2C–3

2021
[14]

Quantum causal inference in the presence of hidden common causes: An entropic approach,

M. A. Javidian, V . Aggarwal, and Z. Jacob, “Quantum causal inference in the presence of hidden common causes: An entropic approach,”Physical Review A, vol. 106, no. 6, p. 062425, 2022

2022
[15]

Multimodal learning without labeled multimodal data: Guarantees and applications,

P. P. Liang, C. K. Ling, Y . Cheng, A. Obolenskiy, Y . Liu, R. Pandey, A. Wilf, L.-P. Morency, and R. Salakhutdinov, “Multimodal learning without labeled multimodal data: Guarantees and applications,” inThe Twelfth International Conference on Learning Representations, 2024

2024
[16]

Learning to match unpaired data with minimum entropy coupling,

M. Bounoua, G. Franzese, and P. Michiardi, “Learning to match unpaired data with minimum entropy coupling,” inForty-second International Conference on Machine Learning, 2025

2025
[17]

Fundamental limits of perfect concept erasure,

S. B. R. Chowdhury, K. A. Dubey, A. Beirami, R. Kidambi, N. Monath, A. Ahmed, and S. Chaturvedi, “Fundamental limits of perfect concept erasure,” inInternational Conference on Artificial Intelligence and Statistics. PMLR, 2025, pp. 901–909

2025
[18]

Improving achievability of cache-aided private variable-length coding with zero leakage,

A. Zamani and M. Skoglund, “Improving achievability of cache-aided private variable-length coding with zero leakage,” in2024 22nd International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt). IEEE, 2024, pp. 218–224

2024
[19]

Private variable-length coding with sequential encoder,

A. Zamani, T. J. Oechtering, D. G ¨und¨uz, and M. Skoglund, “Private variable-length coding with sequential encoder,” in2025 IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 2025, pp. 1–6

2025
[20]

Variable-length coding with zero and non-zero privacy leakage,

A. Zamani and M. Skoglund, “Variable-length coding with zero and non-zero privacy leakage,”Entropy, vol. 27, no. 2, p. 124, 2025

2025
[21]

A metric between probability distributions on finite sets of different cardinalities and applications to order reduction,

M. Vidyasagar, “A metric between probability distributions on finite sets of different cardinalities and applications to order reduction,”IEEE Transactions on Automatic Control, vol. 57, no. 10, pp. 2464–2477, 2012

2012
[22]

Approximating probability distributions with short vectors, via information theoretic distance measures,

F. Cicalese, L. Gargano, and U. Vaccaro, “Approximating probability distributions with short vectors, via information theoretic distance measures,” in 2016 IEEE International Symposium on Information Theory (ISIT). IEEE, 2016, pp. 1138–1142

2016
[23]

Efficient approximate minimum entropy coupling of multiple probability distributions,

C. T. Li, “Efficient approximate minimum entropy coupling of multiple probability distributions,”IEEE Transactions on Information Theory, vol. 67, no. 8, pp. 5259–5268, 2021

2021
[24]

Greedy additive approximation algorithms for minimum-entropy coupling problem,

M. Rossi, “Greedy additive approximation algorithms for minimum-entropy coupling problem,” in2019 IEEE International Symposium on Information Theory (ISIT). IEEE, 2019, pp. 1127–1131

2019
[25]

A tighter approximation guarantee for greedy minimum entropy coupling,

S. Compton, “A tighter approximation guarantee for greedy minimum entropy coupling,” in2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022, pp. 168–173

2022
[26]

Information spectrum converse for minimum entropy couplings and functional representations,

Y . Y . Shkel and A. K. Yadav, “Information spectrum converse for minimum entropy couplings and functional representations,” in2023 IEEE International Symposium on Information Theory (ISIT). IEEE, 2023, pp. 66–71

2023
[27]

Approximation guarantees for minimum r´enyi entropy functional representations,

A. K. Yadav and Y . Y . Shkel, “Approximation guarantees for minimum r´enyi entropy functional representations,” in2025 IEEE International Symposium on Information Theory (ISIT). IEEE, 2025

2025
[28]

Efficient approximate minimum-r ´enyi entropy couplings,

Y .-J. Ma, F. Wang, and X.-Y . Wu, “Efficient approximate minimum-r ´enyi entropy couplings,”Discrete and Continuous Dynamical Systems-S, pp. 0–0, 2025

2025
[29]

Using dual approximation algorithms for scheduling problems theoretical and practical results,

D. S. Hochbaum and D. B. Shmoys, “Using dual approximation algorithms for scheduling problems theoretical and practical results,”Journal of the ACM (JACM), vol. 34, no. 1, pp. 144–162, 1987

1987
[30]

Bin packing with restricted piece sizes,

J. Y . Leung, “Bin packing with restricted piece sizes,”Information Processing Letters, vol. 31, no. 3, pp. 145–149, 1989

1989
[31]

Approximation algorithms for np-hard problems,

D. S. Hochbaum, “Approximation algorithms for np-hard problems,”ACM Sigact News, vol. 28, no. 2, pp. 40–52, 1997

1997
[32]

Approximation schemes for scheduling,

N. Alon, Y . Azar, G. J. Woeginger, and T. Yadid, “Approximation schemes for scheduling,” inSODA, 1997, pp. 493–500

1997
[33]

Approximation schemes for scheduling on parallel machines,

——, “Approximation schemes for scheduling on parallel machines,”Journal of Scheduling, vol. 1, no. 1, pp. 55–66, 1998

1998
[34]

An eptas for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables,

K. Jansen, “An eptas for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables,”SIAM Journal on Discrete Mathematics, vol. 24, no. 2, pp. 457–485, 2010

2010
[35]

On the optimality of approximation schemes for the classical scheduling problem,

L. Chen, K. Jansen, and G. Zhang, “On the optimality of approximation schemes for the classical scheduling problem,” inProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2014, pp. 657–668

2014
[36]

Closing the gap for makespan scheduling via sparsification techniques,

K. Jansen, K.-M. Klein, and J. Verschae, “Closing the gap for makespan scheduling via sparsification techniques,”Mathematics of Operations Research, vol. 45, no. 4, pp. 1371–1392, 2020

2020
[37]

Bounds on the entropy of a function of a random variable and their applications,

F. Cicalese, L. Gargano, and U. Vaccaro, “Bounds on the entropy of a function of a random variable and their applications,”IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2220–2230, 2017

2017
[38]

On the complexity of numerical analysis,

E. Allender, P. B ¨urgisser, J. Kjeldgaard-Pedersen, and P. B. Miltersen, “On the complexity of numerical analysis,”SIAM Journal on Computing, vol. 38, no. 5, pp. 1987–2006, 2009

1987
[39]

On the complexity of nash equilibria and other fixed points,

K. Etessami and M. Yannakakis, “On the complexity of nash equilibria and other fixed points,”SIAM Journal on Computing, vol. 39, no. 6, pp. 2531–2597, 2010

2010
[40]

On the sum of square roots of polynomials and related problems,

N. Kayal and C. Saha, “On the sum of square roots of polynomials and related problems,”ACM Transactions on Computation Theory (TOCT), vol. 4, no. 4, pp. 1–15, 2012. 17 APPENDIX A. Precisely computing entropy As far as we know, it is open whether the simple expressionH(x) =xlog...

2012

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Minimum-entropy coupling approximation guarantees beyond the majorization barrier,

S. Compton, D. Katz, B. Qi, K. Greenewald, and M. Kocaoglu, “Minimum-entropy coupling approximation guarantees beyond the majorization barrier,” inInternational Conference on Artificial Intelligence and Statistics. PMLR, 2023, pp. 10 445–10 469

2023

[2] [2]

Tight results on minimum entropy set cover,

J. Cardinal, S. Fiorini, and G. Joret, “Tight results on minimum entropy set cover,”Algorithmica, vol. 51, no. 1, pp. 49–60, 2008

2008

[3] [3]

On the entropy of couplings,

M. Kova ˇcevi´c, I. Stanojevi ´c, and V . ˇSenk, “On the entropy of couplings,”Information and Computation, vol. 242, pp. 369–382, 2015

2015

[4] [4]

Communicating via markov decision processes,

S. Sokota, C. A. S. De Witt, M. Igl, L. M. Zintgraf, P. Torr, M. Strohmeier, Z. Kolter, S. Whiteson, and J. Foerster, “Communicating via markov decision processes,” inInternational Conference on Machine Learning. PMLR, 2022, pp. 20 314–20 328

2022

[5] [5]

Minimum-entropy couplings and their applications,

F. Cicalese, L. Gargano, and U. Vaccaro, “Minimum-entropy couplings and their applications,”IEEE Transactions on Information Theory, vol. 65, no. 6, pp. 3436–3451, 2019

2019

[6] [6]

Minimum entropy coupling with bottleneck,

R. Ebrahimi, J. Chen, and A. Khisti, “Minimum entropy coupling with bottleneck,”Advances in Neural Information Processing Systems, vol. 37, pp. 59 655–59 688, 2024

2024

[7] [7]

Perfectly secure steganography using minimum entropy coupling,

C. S. de Witt, S. Sokota, J. Z. Kolter, J. Foerster, and M. Strohmeier, “Perfectly secure steganography using minimum entropy coupling,”arXiv preprint arXiv:2210.14889, 2022

arXiv 2022

[8] [8]

Entropic causal inference,

M. Kocaoglu, A. Dimakis, S. Vishwanath, and B. Hassibi, “Entropic causal inference,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 31, no. 1, 2017

2017