Playing Games with Multiple Access Channels

Felix Leditzky; Graeme Smith; Joshua Levin; Mohammad A. Alhejji

REVIEW 2 major objections 6 minor 47 references

Playing Games with Multiple Access Channels

T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Entanglement shared by two senders can strictly increase the capacity region of a classical multiple access channel, and deciding this capacity can be NP-hard or even undecidable.

desk verdict A mostly solid and important paper that shows entanglement can strictly boost classical MAC capacity and that capacity regions are computationally hard; the main caveat is an unproven generalization of Proposition 3 to quantum strategies that is load-bearing for the unbounded-entanglement and undecidability claims. read the letter →

arxiv 1909.02479 v2 pith:K7AXLNSU submitted 2019-09-05 quant-ph cs.ITmath.IT

Felix Leditzky , Mohammad A. Alhejji , Joshua Levin , Graeme Smith This is my paper · ORCID

classification quant-phcs.ITmath.IT MSC 94A1581P6868Q17

keywords multipleaccesschannelnon-localgamesentanglementassistancecapacityregionmagicsquaregamelinearsystemundecidabilityNP-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

This paper proves that a two-sender classical multiple access channel can be built from any two-player non-local game so that the channel's noise is exactly the players' losing probability. The central theorem states that whenever the game cannot be won with certainty using the resources available to the senders, the achievable sum rate is strictly below the maximum $\log|X_1|+\log|X_2|$. That single gap mechanism yields four concrete consequences: entanglement shared between senders strictly increases the capacity of some classical MACs; some MACs with bounded input alphabets require unbounded entanglement to approach their ideal rates; checking whether the ideal rate pair is achievable with finite-dimensional entanglement is undecidable; and checking membership in the unassisted capacity region to inverse-cubic precision is NP-hard. This refutes the assumption that the computable single-letter formula for MAC capacity makes the problem easy.

What carries the argument

The load-bearing construction is the game-to-MAC encoding (2): the input alphabets are question-answer pairs $(X_1\times Y_1)$ and $(X_2\times Y_2)$, the output alphabet is $X_1\times X_2$, and on a winning tuple the channel outputs the question pair $(x_1,x_2)$ deterministically while on a losing tuple it outputs a uniformly random pair. The identity (3), $I(X_1Y_1X_2Y_2;Z)=H(Z)-p_L(\log|X_1|+\log|X_2|)$, reduces the sum-rate bound from the classical single-letter MAC capacity formula to a statement about the losing probability $p_L$. Proposition 3 converts the condition $\omega_U(G)<1$ into a quantitative entropy bound, giving Theorem 1. All four main results are corollaries of that single separation mechanism.

What would settle it

Pick a non-local game $G$ with $\omega_U(G)<1$ and small alphabet sizes, then exhaustively optimize over all product input distributions and all strategies to compute the exact sum capacity of $N_G$; if it equals $\log|X_1|+\log|X_2|$ for any such game, Theorem 1 is false. For the unbounded-entanglement claim, exhibit a finite-$d$ quantum strategy for the particular linear system game used in the paper whose losing probability is exactly zero; then the claimed $\Omega(1/d^{13})$ gap would be contradicted.

Watch

Extended reading notes

Core claim

The paper's central claim is that a two-sender classical MAC $N_G$ can be defined from any non-local game $G$ so that the channel is noiseless exactly when Alice and Bob win the game and maximally noisy otherwise. The decisive result (Theorem 1) is that whenever $G$ has no perfect strategy using the same resources available to the communication strategy, the sum rate $R_1+R_2$ is strictly smaller than $\log|X_1|+\log|X_2|$. The same gap then yields four results: the magic square game gives a classical MAC whose entanglement-assisted rate region contains a point $(\log 3,\log 3)$ that is provably outside the unassisted capacity region; a particular linear system game gives a MAC whose $d$-dimensional entanglement-assisted rate regions are bounded away from the ideal point for every finite $d$ but approach it as $d\to\infty$; deciding whether the ideal rate pair belongs to the finite-dimensional entanglement-assisted region is undecidable; and deciding whether an arbitrary rate point lies in the unassisted capacity region, to inverse-cubic precision, is NP-hard.

Load-bearing premise

The upper-bound proofs take a bound proved for classical probabilistic strategies and apply it to arbitrary $d$-dimensional quantum entanglement-assisted coding strategies, replacing the classical maximal winning probability by the quantum one; if that generalized bound fails, the unbounded-entanglement and undecidability claims lose their converse direction.

Editorial extensions

If this is right

Any pseudo-telepathy game (no perfect classical strategy, but a perfect quantum one) yields a classical MAC whose entanglement-assisted rate region strictly contains its unassisted capacity region; the magic square example separates $3.13694$ from $2\log 3\approx 3.17$.
There are MACs for which, for every fixed entanglement dimension $d$, the sum rate is bounded away from $\log m+\log n$ by $\Omega(1/d^{13})$, yet the achievable region approaches that point as $d\to\infty$, so bounded input alphabets can demand unbounded entanglement.
Deciding whether the ideal rate pair $(\log m,\log n)$ lies in the finite-dimensional entanglement-assisted achievable region is undecidable for MACs built from linear system games.
Deciding whether a rate pair belongs to the unassisted capacity region of a classical MAC, to additive error $\Theta(1/n^3)$, is NP-hard; hence the single-letter formula does not provide an efficient algorithm.
Unless $\mathrm{P}=\mathrm{NP}$, there is no polynomial-time algorithm for computing the boundary of the capacity region of a general discrete MAC; under the exponential-time hypothesis, no subexponential algorithm exists either.

Reading between the lines

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

The same construction would likely turn any Bell-type inequality violation into a communication-rate separation: any game whose classical and quantum winning probabilities differ should produce a MAC whose entanglement-assisted and unassisted regions differ, so quantitative gaps such as CHSH could yield an explicit family of small separations.
The unbounded-entanglement phenomenon suggests a resource-theoretic reading: if entanglement is priced per dimension, the optimal rate-cost tradeoff for these MACs has no finite optimum, and one can only approach the ideal rate asymptotically.
The NP-hardness proof targets the unassisted capacity region; a parallel hardness result for the entanglement-assisted region or for quantum MACs would complete the picture across the two settings.
The numerical gap between the proven upper bound ($3.13694$) and the computed lower bound ($2.84195$) for the magic square channel suggests that the true classical-quantum separation is larger than the theorem guarantees, so a direct proof of a tighter bound would be a natural test of the mechanism.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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,

Here is my read on Leditzky et al. The new content that matters: they apply the non-local game construction of MACs (credited to Quek–Shor and Nötzel–Winter) to prove that shared entanglement between senders strictly increases the capacity region of a classical MAC, that unbounded entanglement may be needed to approach the ideal rate, that membership in the finite-dimensional entanglement-assisted rate region is undecidable, and that approximating the unassisted capacity region is NP-hard. The magic-square separation and the PCP-based NP-hardness result are the most robust, since they rely only on classical strategies. The construction is clean, the paper credits prior work honestly, and the point about single-letter formulas not implying computational tractability is well made.

The soft spot is exactly what the stress-test flagged. Proposition 3 is proved for classical probabilistic strategies, but Appendix D.1 (Proposition 5) and the converse direction of Proposition 8 apply it to d-dimensional entanglement-assisted coding strategies without proving the needed generalization. The induced question-answer correlation after post-processing need not itself be a d-dimensional game strategy, so the uniform-questions losing probability could behave differently than the classical bound assumes. If that generalized statement fails, the unbounded-entanglement and undecidability converses lose support. The classical results are not affected. This looks like a repairable gap rather than a fatal flaw: one likely needs a quantum version of Proposition 3, proven by a similar data-processing argument with the appropriate d-dimensional quantum winning probability. But it must be addressed before those headline claims are accepted.

The citation pattern is fair and the mathematics in the parts I checked is sound. The numerical optimization in Appendix C is clearly labeled as a heuristic lower bound, not a proof. I saw no circularity.

Who should read this? Network information theorists and quantum information researchers interested in entanglement assistance and the complexity of capacity regions. It deserves a serious referee. My recommendation: send it to peer review, but make sure the referee requires a generalized Proposition 3 before the unbounded-entanglement and undecidability claims are taken as established. I would cite the paper, mainly for the game-MAC construction and the classical NP-hardness result.

Referee Report

2 major / 6 minor

Summary. The paper constructs, for any two-player non-local game G, a classical two-sender multiple access channel N_G whose output is the question pair when the players win the game and a uniformly random question pair when they lose. The central identity (Proposition 2) expresses the sum-rate mutual information as H(Z) − p_L log(|X_1||X_2|), tying the channel noise directly to the game losing probability. Proposition 3 converts this identity into a quantitative gap for games with no perfect classical strategy. Using this tool, the authors claim four results: (i) the magic-square game gives a classical MAC whose unassisted sum rate is strictly below 2 log 3 while an entanglement-assisted strategy achieves 2 log 3; (ii) a linear-system game of Slofstra and Vidick yields MACs whose d-dimensional entanglement-assisted single-letter rate region approaches the perfect rate pair only in the limit d→infty; (iii) via Slofstra's undecidability theorem, deciding whether the perfect rate pair lies in the finite-dimensional entanglement-assisted single-letter region is undecidable; and (iv) via the PCP theorem, deciding whether the unassisted capacity region contains a point is NP-hard to inverse-cubic precision.

Significance. The game-to-MAC construction is elegant and connects non-local games to network information theory in a way that yields surprising consequences: entanglement assistance for a classical MAC, unbounded entanglement requirements, undecidability, and NP-hardness for a channel family covered by a single-letter capacity formula. The identity in Proposition 2 is clean, the numerical work for the magic square is reproducible from the supplied code, and the provenance of the construction is transparently credited to Quek-Shor and Nötzel-Winter. The classical applications (magic-square separation and NP-hardness) are already interesting. However, the quantum converse claims rest on an unproven extension of Proposition 3 to entanglement-assisted coding strategies, and the proof of Proposition 3 itself contains an unjustified entropic step. If the authors repair these points, the paper would be a strong contribution; as it stands, the formal support for the unbounded-entanglement and undecidability statements is incomplete.

major comments (2)

[Appendix D.1 / D.3 (Propositions 5 and 8)] Proposition 3 is stated and proved only for classical probabilistic strategies, but Propositions 5 and 8 apply it to arbitrary d-dimensional entanglement-assisted coding strategies of the form in Appendix A.3. The proof of Proposition 3 relies on the bound q_L ≥ 1 − ω_U(G) for the losing probability of the same strategy under uniformly drawn questions; for a coding strategy E the paper never proves that the induced conditional distribution p(y1,y2|x1,x2) is a d-dimensional quantum game strategy, nor that its uniform-question losing probability satisfies q_L ≥ 1 − ω_U^q_d(G). Because x1 and x2 are outputs of the post-processed measurement rather than external questions, the conditional distribution can in principle depend on the message pair, so the Slofstra–Vidick bound (50), which applies to game strategies, does not by itself constrain coding strategies. Without a proof of the quantum generalization of Proposition 3, the converse directions of Propositions 5 and 8 (and hence the unbounded-entanglement and undecidability headline claims) are unsupported. The magic-square separation and the NP-hardness result are classical and are not affected.
[Appendix B, proof of Proposition 3, Eq. (29)] The expansion of H(ZW) in Eq. (29) replaces H(X1X2|W=1) with H(X1X2). The inequality (1−pL)H(X1X2|W=1) ≥ (1−pL)H(X1X2) is not valid in general; conditioning on the win/loss event can either increase or decrease the entropy of the question variables, depending on how the question distribution is tilted toward winning or losing question pairs. This step is what produces the divergence bound D(πX1πX2‖πU) ≤ γ in Eq. (31), on which the data-processing argument for the gap in Eq. (22) depends. The proof should be repaired, for instance by bounding I(X1X2;W) ≤ h(pL) and absorbing the additional terms, and the statement of Proposition 3 should be checked against the repaired proof.

minor comments (6)

[Appendix C.3, Eq. (38)] The channel definition (38) has codomain R×S and uses the factor δ_s\hat{s}, but the output of N_G must be the question pair (r,c), so the codomain should be R×C and the delta should be δ_c\hat{c}. The subsequent entropy calculation log 9 and the comparison with 2 log 3 assume the output is the question pair, so this is a typographical error in the displayed channel definition.
[Appendix A.3] In the definition of the second sender's measurements, 'for b1∈A1' should read 'for b1∈B1'; the same alphabet misassignment appears in a later sentence describing the post-processing f2.
[Appendix D.2, proof of Proposition 6] In the line 'the trivial bound H(X2|W = 1)≤ log|X2| = n', the right-hand side should be log n, not n; otherwise the dimension and the logarithm are conflated.
[Proposition 5] The statement says the sum rate capacity is bounded away from the perfect value 'by Θ(1/d^13)'. The proof gives only an upper bound on the sum capacity, i.e., the gap is Ω(1/d^13). The achievable strategy in Proposition 6 has gap O(1/d^2), so the gap is not established to be Θ(1/d^13); the notation should be Ω(1/d^13) or 'at least', unless a matching upper bound on the gap is supplied.
[Proposition 3, Eq. (23)] The symbol δ is overloaded: it is the additive parameter in Eq. (22) and also the binary relative entropy function δ(·‖·) in Eq. (23) and Eq. (32). Using a different symbol for the divergence, e.g., D_2, would remove ambiguity.
[Section 2.3 and Proposition 10] The introduction describes the gap as (1−ω*)^3 with ω*=1−(1−c)/n, which is Θ((1−c)^3/n^3), while Proposition 10 takes δ=(1−c)/n^3. These are asymptotically compatible but the constants differ; the two displays should be harmonized.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central MAC/non-local-game reduction is derived from the channel definition and external results, with no fitted parameter renamed as a prediction.

full rationale

The paper's central construction (Eq. 15) maps a non-local game G to a MAC N_G, and Proposition 2 derives I(X1Y1X2Y2;Z) = H(Z) - p_L(log|X1| + log|X2|) directly from the definition of N_G. Theorem 1's gap is then obtained from Proposition 3, whose proof is a self-contained entropic argument using data processing and the classical winning probability ω_U(G); no step assumes the theorem it proves. The unbounded-entanglement and undecidability claims rest on external results by Slofstra-Vidick [16] and Slofstra [17], which are cited with attribution and are not products of the present authors; the PCP-based NP-hardness argument likewise invokes Håstad's game and the PCP theorem as independent inputs. None of the paper's inequalities is fitted to data and then reported as a prediction, and no load-bearing premise is justified by a self-citation. A possible concern is that Proposition 3 is stated for classical probabilistic strategies but is applied in Appendix D.1 and Proposition 8 to d-dimensional entanglement-assisted coding strategies without an explicit proof that the induced question-answer correlations satisfy the same bound; that is a completeness/correctness gap rather than a circularity, since the Proposition is not derived from the target claim and the cited Slofstra-Vidick bound is external. Accordingly no circular step is identified.

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

No free parameters are fitted in this paper; constants such as C1, C', c, a, and b are inherited from cited external results (PCP theorem, Slofstra-Vidick) and are not tuned to data. The paper introduces no new physical entities; the MAC NG is a defined mathematical object constructed from a nonlocal game. The main theorems rest on standard external results in information theory and complexity theory, plus the authors' own derivations.

assumptions (4)

standard math Ahlswede-Liao capacity theorem: C(N) is the convex hull of rate regions over product input distributions (Eq. 6).
Used throughout to define the unassisted capacity region and to define the entanglement-assisted achievable region C(N∘E) in Eq. (11).
standard math PCP theorem as formulated in Theorem 9: deciding if a 3-CNF-5 formula is satisfiable or at most c-satisfiable is NP-hard.
The basis of the NP-hardness reduction in Section E, providing the constant-gap hard instance used to construct the game GH.
domain assumption Slofstra's undecidability result (Corollary 1.3 in [17]): it is undecidable whether a linear system game has a perfect finite-dimensional quantum strategy.
Used in Proposition 8 to infer undecidability for the MAC rate region membership problem.
domain assumption Slofstra-Vidick bounds (49) and Lemma 4.2 from [16] relating local dimension, losing probability, and worst-case winning probability for the game GSV.
Used to prove the unbounded entanglement gap (Proposition 5) and the achievability of the ideal rate pair in the limit (Proposition 6).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Playing Games with Multiple Access Channels." pith.science (2026). https://pith.science/paper/K7AXLNSU

@misc{pith2026190902479,
  author       = {Pith},
  title        = {Pith review of: Playing Games with Multiple Access Channels},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K7AXLNSU}},
  note         = {Machine review of arXiv:1909.02479}
}

read the original abstract

Communication networks have multiple users, each sending and receiving messages. A multiple access channel (MAC) models multiple senders transmitting to a single receiver, such as the uplink from many mobile phones to a single base station. The optimal performance of a MAC is quantified by a capacity region of simultaneously achievable communication rates. We study the two-sender classical MAC, the simplest and best-understood network, and find a surprising richness in both a classical and quantum context. First, we find that quantum entanglement shared between senders can substantially boost the capacity of a classical MAC. Second, we find that optimal performance of a MAC with bounded-size inputs may require unbounded amounts of entanglement. Third, determining whether a perfect communication rate is achievable using finite-dimensional entanglement is undecidable. Finally, we show that evaluating the capacity region of a two-sender classical MAC is in fact NP-hard.

Figures

Figures reproduced from arXiv: 1909.02479 by the authors.

**Figure 1.** Multiple access channels. (a) Realistic scenario of a multiple access channel (MAC), in which two cell phones send data to a cell tower. (b) Mathematical model of a MAC N, characterized by finite input alphabets A and B, an output alphabet Z, and a conditional probability distribution N(z|a, b) for a ∈ A, b ∈ B, z ∈ Z. The random variables corresponding to the senders and the receiver are denoted by A, B, and Z, res… view at source ↗

**Figure 2.** Classical and quantum strategies for the magic square game. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Mathematical model of a multiple access channel. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Entanglement-assisted coding scenario for a multiple access channel. [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

**Figure 5.** Figure 5: Upper bounds on the classical sum rate for the multiple access channel based on the magic square [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]

**Figure 6.** Figure 6: Inner and outer bounds on the capacity region of the multiple access channel based on the magic [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]

**Figure 7.** Figure 7: Entanglement-assisted coding strategy for the multiple access channel based on a linear system [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 43 canonical work pages

[1]

Shannon, C. E. A mathematical theory of communication. Bell System Technical Journal 27, 379–423 (1948)

1948
[2]

Multi-way communication channels

Ahlswede, R. Multi-way communication channels. Second International Symposium on Information Theory: Tsahkadsor, Armenia, USSR, Sept. 2-8, 1971 (1971), 23–52

work page 1971
[3]

Multiple access channels PhD thesis (Department of Electrical Engineering, University of Hawaii, 1972)

Liao, H. Multiple access channels PhD thesis (Department of Electrical Engineering, University of Hawaii, 1972)

work page 1972
[4]

Bennett, C. H. & Wiesner, S. J. Communication via one- and two-particle operators on Einstein- Podolsky-Rosen states. Physical Review Letters 69, 2881–2884 (1992)

work page 1992
[5]

H., Brassard, G., Cr´ epeau, C., Jozsa, R., Peres, A

Bennett, C. H., Brassard, G., Cr´ epeau, C., Jozsa, R., Peres, A. & Wootters, W. K. Teleporting an un- known quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters 70, 1895–1899 (1993)

work page 1993
[6]

H., Shor, P

Bennett, C. H., Shor, P. W., Smolin, J. A. & Thapliyal, A. V. Entanglement-Assisted Classical Capacity of Noisy Quantum Channels. Physical Review Letters 83, 3081–3084 (1999)

work page 1999
[7]

& Shor, P

Quek, Y. & Shor, P. W. Quantum and superquantum enhancements to two-sender, two-receiver chan- nels. Physical Review A 95, 052329 (2017)

work page 2017
[8]

F., Horne, M

Clauser, J. F., Horne, M. A., Shimony, A. & Holt, R. A. Proposed Experiment to Test Local Hidden- Variable Theories. Physical Review Letters 23, 880–884 (1969)

work page 1969

Show all 47 references

[9]

Personal communication

Winter, A. Personal communication. 2019. 5

2019
[10]

Entanglement-Enabled Communication

N¨ otzel, J. Entanglement-Enabled Communication. arXiv preprint. arXiv: 1910 . 03796 [quant-ph] (2019)

2019
[11]

Mermin, N. D. Simple uniﬁed form for the major no-hidden-variables theorems. Physical Review Letters 65, 3373–3376 (1990)

1990
[12]

Incompatible results of quantum measurements

Peres, A. Incompatible results of quantum measurements. Physics Letters A 151, 107–108 (1990)

1990
[13]

Aravind, P. K. A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities. arXiv preprint. arXiv: quant-ph/0206070 (2002)

2002 arXiv
[14]

& Tapp, A

Brassard, G., Broadbent, A. & Tapp, A. Quantum Pseudo-Telepathy. Foundations of Physics 35, 1877– 1907 (2005)

2005
[15]

& Mittal, R

Cleve, R. & Mittal, R. Characterization of binary constraint system games. International Colloquium on Automata, Languages, and Programming (2014), 320–331. arXiv: 1209.2729 [quant-ph]

2014 arXiv
[16]

& Vidick, T

Slofstra, W. & Vidick, T. Entanglement in Non-local Games and the Hyperlinear Proﬁle of Groups. Annales Henri Poincar´ e19, 2979–3005 (2018)

2018
[17]

The set of quantum correlations is not closed

Slofstra, W. The set of quantum correlations is not closed. Forum of Mathematics, Pi 7, e1 (2019)

2019
[18]

Some Optimal Inapproximability Results

H˚ astad, J. Some Optimal Inapproximability Results. Journal of the ACM 48, 798–859 (July 2001)

2001
[19]

A Threshold of Ln N for Approximating Set Cover

Feige, U. A Threshold of Ln N for Approximating Set Cover. Journal of the ACM 45, 634–652 (1998)

1998
[20]

& Saket, R

Khot, S. & Saket, R. A 3-query non-adaptive PCP with perfect completeness. Proceedings of the 21st Annual IEEE Conference on Computational Complexity (2006), 11 pp.–169

2006
[21]

P., Fonollosa, J

Calvo, E., Palomar, D. P., Fonollosa, J. R. & Vidal, J. On the Computation of the Capacity Region of the Discrete MAC. IEEE Transactions on Communications 58, 3512–3525 (2010)

2010
[22]

& Kim, Y.-H

El Gamal, A. & Kim, Y.-H. Network Information Theory (Cambridge University Press, Cambridge, 2011)

2011
[23]

& Winter, A

Hsieh, M.-H., Devetak, I. & Winter, A. Entanglement-Assisted Capacity of Quantum Multiple-Access Channels. IEEE Transactions on Information Theory 54, 3078–3090 (2008)

2008
[24]

The capacity of the quantum multiple-access channel

Winter, A. The capacity of the quantum multiple-access channel. IEEE Transactions on Information Theory 47, 3059–3065 (2001)

2001
[25]

& Devetak, I

Yard, J., Hayden, P. & Devetak, I. Capacity theorems for quantum multiple-access channels: classical- quantum and quantum-quantum capacity regions.IEEE Transactions on Information Theory 54, 3091– 3113 (2008)

2008
[26]

& Horodecki, P

Czekaj, L. & Horodecki, P. Purely Quantum Superadditivity of Classical Capacities of Quantum Mul- tiple Access Channels. Physical Review Letters 102, 110505 (2009)

2009
[27]

& Wilde, M

Qi, H., Wang, Q. & Wilde, M. M. Applications of position-based coding to classical communication over quantum channels. Journal of Physics A: Mathematical and Theoretical 51, 444002 (2018)

2018
[28]

A one-shot quantum joint typicality lemma

Sen, P. A one-shot quantum joint typicality lemma. arXiv preprint. arXiv: 1806.07278 [quant-ph] (2018)

2018 arXiv
[29]

Estimating Mutual Information Via Kolmogorov Distance

Zhang, Z. Estimating Mutual Information Via Kolmogorov Distance. IEEE Transactions on Informa- tion Theory 53, 3280–3282 (2007)

2007
[30]

& Wunder, G

Buhler, J. & Wunder, G. A Note on Capacity Computation for the Discrete Multiple Access Channel. IEEE Transactions on Information Theory 57, 1906–1910 (2011). 6

2011
[31]

& Mario Szegedy

Arora, S., Lund, C., Motwani, R., Sudan, M. & Mario Szegedy. Proof veriﬁcation and hardness of ap- proximation problems. Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992), 14–23

1992
[32]

The PCP Theorem by Gap Ampliﬁcation

Dinur, I. The PCP Theorem by Gap Ampliﬁcation. Journal of the ACM 54, 12 (June 2007)

2007
[33]

Vazirani, V. V. Approximation Algorithms (Springer-Verlag, Berlin, Heidelberg, 2001)

2001
[34]

& Safra, S

Arora, S. & Safra, S. Probabilistic checking of proofs; a new characterization of NP. Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992), 2–13

1992
[35]

& Szegedy, M

Feige, U., Goldwasser, S., Lovasz, L., Safra, S. & Szegedy, M. Approximating clique is almost NP- complete. Proceedings of the 32nd Annual Symposium of Foundations of Computer Science (1991), 2– 12

1991
[36]

An algorithm for computing the capacity of arbitrary discrete memoryless channels

Arimoto, S. An algorithm for computing the capacity of arbitrary discrete memoryless channels. IEEE Transactions on Information Theory 18, 14–20 (1972)

1972
[37]

Computation of channel capacity and rate-distortion functions

Blahut, R. Computation of channel capacity and rate-distortion functions. IEEE Transactions on In- formation Theory 18, 460–473 (1972)

1972
[38]

& Paturi, R

Impagliazzo, R. & Paturi, R. Complexity of k-SAT. Proceedings of the Fourteenth Annual IEEE Con- ference on Computational Complexity (1999), 237–240. Acknowledgments We thank Mark M. Wilde and Andreas Winter for helpful comments and feedback. This work was partially supported ...

1999
[39]

the parity of Alice’s bit string s is even: s0⊕s1⊕s2 = 0
[40]

the parity of Bob’s bit string t is odd: t0⊕t1⊕t2 = 1
[41]

the bit strings agree in the overlapping cell ( r,c ): sc =tr. C.1 Classical Strategies The two parity constraints for Alice’s and Bob’s bit strings s andt render any deterministic perfect classical strategy for GMS impossible, since the latter corresponds to a ﬁxed valid ﬁlli...
[42]

As explained in Remark 4, we ﬁnd the optimalδ∗ = 0.03299 (using, e.g., Mathematica), which yieldsε(δ∗) = 0.01040 andI(RSCT ;Z)≤ u(δ∗) = 3.13694

and the corresponding optimalε∗ determined through (23). As explained in Remark 4, we ﬁnd the optimalδ∗ = 0.03299 (using, e.g., Mathematica), which yieldsε(δ∗) = 0.01040 andI(RSCT ;Z)≤ u(δ∗) = 3.13694. In Figure 5 we plot the upper bound (39) as a function of δ∈ [0, log 9/8]. ...
[43]

Next, observe that for δ∈ [0, 1 2] the binary entropy termh(δ) is upper-bounded by aδα for α< 1 and a large enough. Letting α = 25 26, we can underestimate the right-hand side via Pinsker’s inequality and get δ(ε∗‖1−ωU(GSV))≥ 2 ln 2 [ ε∗− (1−ωU(GSV)) ]2 ≥ 2 ln 2 [ ε∗− C1 d6 ]2...
[44]

Completeness: If x∈L, then there exists a proof P such that V accepts with probability at least c
[45]

Note that this can be considered a generalization of NP as NP = PCP 1,0[0, poly(n)]

Soundness: If x /∈L, then V accepts with probability at most s. Note that this can be considered a generalization of NP as NP = PCP 1,0[0, poly(n)]. The original PCP theorem says that NP ⊆ PCP1,1/2[logn, 1] [34]. To illustrate its implications, consider the canonical NP- compl...
[46]

Choose k∈{ aj,bj,cj} uniformly at random and send k to Bob

Choose an integer j∈{ 1,...,m} uniformly at random and send j to Alice. Choose k∈{ aj,bj,cj} uniformly at random and send k to Bob
[47]

They win if Alice’s answer satisﬁes Cj and the two agree on the value of xk, otherwise they lose

Receive an assignment for Cj from Alice and a truth value forxk from Bob. They win if Alice’s answer satisﬁes Cj and the two agree on the value of xk, otherwise they lose. Let ψ be at most c-satisﬁable. Because the optimal strategy is deterministic, Bob will have an assignment...

Pith tools

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

[1] [1]

Shannon, C. E. A mathematical theory of communication. Bell System Technical Journal 27, 379–423 (1948)

1948

[2] [2]

Multi-way communication channels

Ahlswede, R. Multi-way communication channels. Second International Symposium on Information Theory: Tsahkadsor, Armenia, USSR, Sept. 2-8, 1971 (1971), 23–52

work page 1971

[3] [3]

Multiple access channels PhD thesis (Department of Electrical Engineering, University of Hawaii, 1972)

Liao, H. Multiple access channels PhD thesis (Department of Electrical Engineering, University of Hawaii, 1972)

work page 1972

[4] [4]

Bennett, C. H. & Wiesner, S. J. Communication via one- and two-particle operators on Einstein- Podolsky-Rosen states. Physical Review Letters 69, 2881–2884 (1992)

work page 1992

[5] [5]

H., Brassard, G., Cr´ epeau, C., Jozsa, R., Peres, A

Bennett, C. H., Brassard, G., Cr´ epeau, C., Jozsa, R., Peres, A. & Wootters, W. K. Teleporting an un- known quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters 70, 1895–1899 (1993)

work page 1993

[6] [6]

H., Shor, P

Bennett, C. H., Shor, P. W., Smolin, J. A. & Thapliyal, A. V. Entanglement-Assisted Classical Capacity of Noisy Quantum Channels. Physical Review Letters 83, 3081–3084 (1999)

work page 1999

[7] [7]

& Shor, P

Quek, Y. & Shor, P. W. Quantum and superquantum enhancements to two-sender, two-receiver chan- nels. Physical Review A 95, 052329 (2017)

work page 2017

[8] [8]

F., Horne, M

Clauser, J. F., Horne, M. A., Shimony, A. & Holt, R. A. Proposed Experiment to Test Local Hidden- Variable Theories. Physical Review Letters 23, 880–884 (1969)

work page 1969