Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.13860

The Capacity Region of the Multiple Access Channel with Non-Signaling Assistance

Yuhang Yao, Syed A. Jafar

cs.ITquant-phSubmitted Aug 14, 2026• Announced Aug 17, 2026• 0 citations
arXivHTMLPDF

Abstract

The capacity region of the $K$-sender discrete memoryless multiple access channel (MAC) is fully characterized when non-signaling (NS) assistance is available to all $K$ transmitters and the receiver. It is shown to have the same form as the classical capacity region of the MAC, except that the input distribution is allowed to be arbitrarily dependent across the senders. In particular, the NS-assisted capacity region matches the natural generalization to $K$ senders of an outer bound that was previously established by Fawzi and Fermé for $K=2$ senders. Additionally, we provide examples of $K$-sender MACs where the multiplicative gain in capacity from NS-assistance is arbitrarily close to $K$. Combined with an upper bound from prior work, this establishes $K$ as the extremal value of the multiplicative gain from NS-assistance across all $K$-sender MAC settings.

Related papers

Multiple-Access Channel Coding With Non-Signaling Correlations

Omar Fawzi, Paul Fermé

We address the problem of coding for classical multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of classical point-to-point channels. However, it was recently observed that one can construct MACs from two-player nonlocal games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity. In this work, we make several contributions towards understanding the capacity region for MACs with the assistance of non-signaling correlations between the parties. We develop a linear program computing the optimal success probability for coding over$n$copies of a MAC$W$with size growing polynomially in$n$. Solving this linear program allows us to achieve inner bounds for MACs. Applying this method to the binary adder channel, we show that using non-signaling assistance, the sum-rate$\frac {\log _{2}(72)}{4} \simeq 1.5425$can be reached even with zero error, which beats the maximum sum-rate capacity of 1.5 in the unassisted case. For noisy channels, where the zero-error non-signaling assisted capacity region is trivial, we can use concatenated codes to obtain achievable points in the capacity region. Applied to a noisy version of the binary adder channel, we show that non-signaling assistance still improves the sum-rate capacity. Complementing these achievability results, we give an outer bound on the non-signaling assisted capacity region that has the same expression as the unassisted region except that the channel inputs are not required to be independent. Finally, we show that the capacity region with non-signaling assistance shared only between each sender and the receiver independently is the same as without assistance.

arXiv:2206.10968•IEEE Transactions on Information Theory•Aug 8, 2023•13 citations

The Capacity Region of the Broadcast Channel with Non-Signaling Assistance

Yuhang Yao, Syed A. Jafar

The capacity region of the $K$-user discrete memoryless broadcast channel is fully characterized when non-signaling (NS) assistance is available to the transmitter and all $K$ receivers. The NS-assisted capacity region is shown to coincide with Sato's region, i.e., the region defined by sum-rate bounds over all subsets of messages, where each bound corresponds to full cooperation among that subset of receivers under a worst-case joint channel law consistent with the marginal channels.

cs.ITCross-listedarXiv:2607.27434•Jul 31, 2026•0 citations

Virtual Signaling of CSIT via Non-Signaling Assistance

Yuhang Yao, Syed A. Jafar

Non-signaling correlations, which (strictly) include quantum correlations, provide a tractable path to explore the potential impact of quantum nonlocality on the capacity of classical communication networks. Motivated by a recent discovery that certain wireless network settings benefit significantly from non-signaling (NS) correlations, various generalizations are considered. First, it is shown that for a point to point discrete memoryless channel with a non-causal channel state information at the transmitter (CSIT), the NS-assisted Shannon capacity matches the classical (without NS assistance) capacity of the channel for the setting where the state is also made available to the receiver. The key insight is summarized as 'virtual signaling of CSIT via NS-assistance' and is supported by further results as follows. For a discrete memoryless 2-user broadcast channel (BC), the Shannon capacity region with NS-assistance available only between the transmitter and User 1, is found next. Consistent with the aforementioned key insight, the result matches the classical capacity region for the setting where the desired message of User 2 is made available in advance as side-information to User 1. The latter capacity region is known from a result of Kramer and Shamai. Next, for a semi-deterministic BC, the Shannon capacity region with full (tripartite) NS-assistance is shown to be the same as if only bipartite NS-assistance was available between the transmitter and the non-deterministic user. Bipartite NS-assistance between the transmitter and only the deterministic user, does not improve the capacity region relative to the corresponding classical setting. Finally, the analysis is extended to a K-user BC with full NS-assistance among all parties.

arXiv:2506.17803•IEEE Transactions on Information Theory•Aug 10, 2026•0 citations

Non-signaling Assisted Capacity of a Classical Channel with Causal CSIT

Yuhang Yao, Syed A. Jafar

The non-signaling (NS) assisted capacity of a classical discrete memoryless channel with causal channel state information at the transmitter (CSIT) is shown to be $C^{NS,ca}=\max_{P_{X|S}}I(X;Y\mid S)$, where $X, Y, S$ correspond to the input, output and state of the channel. Remarkably, this is the same as the capacity of the channel in the NS-assisted non-causal CSIT setting, $C^{NS,nc}=\max_{P_{X|S}}I(X;Y\mid S)$, which was previously established, and also matches the (either classical or with NS assistance) capacity of the channel where the state is available not only (either causally or non-causally) to the transmitter but also to the receiver. While the capacity remains unchanged, the optimal probability of error for fixed message size and blocklength, in the NS-assisted causal CSIT setting can be further improved if channel state is made available to the receiver. This is in contrast to corresponding NS-assisted non-causal CSIT setting where it was previously noted that the optimal probability of error cannot be further improved by providing the state to the receiver. As a separate result we prove that non-signaling assistance, feedback, and strictly causal CSIT (i.e., transmitter knows only past channel states but not the current or future states), each of which is individually already known to not increase capacity, also cannot increase capacity when they are collectively made available to the transmitter.

arXiv:2602.11568•Feb 12, 2026•0 citations

Beating the Sum-Rate Capacity of the Binary Adder Channel with Non-Signaling Correlations

Omar Fawzi, Paul Fermé

We address the problem of coding for multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of point-to-point channels. However, it was recently observed that one can construct MACs from two-player non-local games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity.Here, we show that the increase in capacity from non-signaling assistance goes beyond such special channels and applies even to a simple deterministic MAC: the binary adder channel. In particular, we show that, with non-signaling assistance, a sum-rate of $\frac{{{{\log }_2}(72)}}{4} \simeq 1.5425$ can be reached with zero error, which beats the maximum classical sum-rate capacity of $\frac{3}{2}$.In order to achieve this, we show that efficient linear programs can be formulated to compute the success probability of the best non-signaling assisted code for a finite number of copies of a multiple-access channel. In particular, this can be used to give lower bounds on the zero-error non-signaling assisted capacity of multiple-access channels.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•10 citations

On the Separation of Correlation-Assisted Sum Capacities of Multiple Access Channels

Akshay Seshadri, Felix Leditzky, Vikesh Siddhu +1 more

The capacity of a channel characterizes the maximum rate at which information can be transmitted through the channel asymptotically faithfully. For a channel with multiple senders and a single receiver, computing its sum capacity is possible in theory, but challenging in practice because of the nonconvex optimization involved. To address this challenge, we investigate three topics in our study. In the first part, we study the sum capacity of a family of multiple access channels (MACs) obtained from nonlocal games. For any MAC in this family, we obtain an upper bound on the sum rate that depends only on the properties of the game when allowing assistance from an arbitrary set of correlations between the senders. This approach can be used to prove separations between sum capacities when the senders are allowed to share different sets of correlations, such as classical, quantum or no-signalling correlations. We also construct a specific nonlocal game to show that the approach of bounding the sum capacity by relaxing the nonconvex optimization can give arbitrarily loose bounds. Owing to this result, in the second part, we study algorithms for non-convex optimization of a class of functions we call Lipschitz-like functions. This class includes entropic quantities, and hence these results may be of independent interest in information theory. Subsequently, in the third part, we show that one can use these techniques to compute the sum capacity of an arbitrary two-sender MACs to a fixed additive precision in quasi-polynomial time. We showcase our method by efficiently computing the sum capacity of a family of two-sender MACs for which one of the input alphabets has size two. Furthermore, we demonstrate with an example that our algorithm may compute the sum capacity to a higher precision than using the convex relaxation.

arXiv:2205.13538•IEEE Transactions on Information Theory•May 15, 2023•11 citations
The capacity region of the KKK-sender discrete memoryless multiple access channel (MAC) is fully characterized when non-signaling (NS) assistance is available to all KKK transmitters and the receiver. It is shown to have the same form as the classical capacity region of the MAC, except that the input distribution is allowed to be arbitrarily dependent across the senders. In particular, the NS-assisted capacity region matches the natural generalization to KKK senders of an outer bound that was previously established by Fawzi and Fermé for K=2K=2K=2 senders. Additionally, we provide examples of KKK-sender MACs where the multiplicative gain in capacity from NS-assistance is arbitrarily close to KKK. Combined with an upper bound from prior work, this establishes KKK as the extremal value of the multiplicative gain from NS-assistance across all KKK-sender MAC settings.
We address the problem of coding for classical multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of classical point-to-point channels. However, it was recently observed that one can construct MACs from two-player nonlocal games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity. In this work, we make several contributions towards understanding the capacity region for MACs with the assistance of non-signaling correlations between the parties. We develop a linear program computing the optimal success probability for coding overnnncopies of a MACWWWwith size growing polynomially innnn. Solving this linear program allows us to achieve inner bounds for MACs. Applying this method to the binary adder channel, we show that using non-signaling assistance, the sum-ratelog⁡2(72)4≃1.5425\frac {\log _{2}(72)}{4} \simeq 1.54254log2​(72)​≃1.5425can be reached even with zero error, which beats the maximum sum-rate capacity of 1.5 in the unassisted case. For noisy channels, where the zero-error non-signaling assisted capacity region is trivial, we can use concatenated codes to obtain achievable points in the capacity region. Applied to a noisy version of the binary adder channel, we show that non-signaling assistance still improves the sum-rate capacity. Complementing these achievability results, we give an outer bound on the non-signaling assisted capacity region that has the same expression as the unassisted region except that the channel inputs are not required to be independent. Finally, we show that the capacity region with non-signaling assistance shared only between each sender and the receiver independently is the same as without assistance.
The capacity region of the KKK-user discrete memoryless broadcast channel is fully characterized when non-signaling (NS) assistance is available to the transmitter and all KKK receivers. The NS-assisted capacity region is shown to coincide with Sato's region, i.e., the region defined by sum-rate bounds over all subsets of messages, where each bound corresponds to full cooperation among that subset of receivers under a worst-case joint channel law consistent with the marginal channels.
Non-signaling correlations, which (strictly) include quantum correlations, provide a tractable path to explore the potential impact of quantum nonlocality on the capacity of classical communication networks. Motivated by a recent discovery that certain wireless network settings benefit significantly from non-signaling (NS) correlations, various generalizations are considered. First, it is shown that for a point to point discrete memoryless channel with a non-causal channel state information at the transmitter (CSIT), the NS-assisted Shannon capacity matches the classical (without NS assistance) capacity of the channel for the setting where the state is also made available to the receiver. The key insight is summarized as 'virtual signaling of CSIT via NS-assistance' and is supported by further results as follows. For a discrete memoryless 2-user broadcast channel (BC), the Shannon capacity region with NS-assistance available only between the transmitter and User 1, is found next. Consistent with the aforementioned key insight, the result matches the classical capacity region for the setting where the desired message of User 2 is made available in advance as side-information to User 1. The latter capacity region is known from a result of Kramer and Shamai. Next, for a semi-deterministic BC, the Shannon capacity region with full (tripartite) NS-assistance is shown to be the same as if only bipartite NS-assistance was available between the transmitter and the non-deterministic user. Bipartite NS-assistance between the transmitter and only the deterministic user, does not improve the capacity region relative to the corresponding classical setting. Finally, the analysis is extended to a K-user BC with full NS-assistance among all parties.
The non-signaling (NS) assisted capacity of a classical discrete memoryless channel with causal channel state information at the transmitter (CSIT) is shown to be CNS,ca=max⁡PX∣SI(X;Y∣S)C^{NS,ca}=\max_{P_{X|S}}I(X;Y\mid S)CNS,ca=maxPX∣S​​I(X;Y∣S), where X,Y,SX, Y, SX,Y,S correspond to the input, output and state of the channel. Remarkably, this is the same as the capacity of the channel in the NS-assisted non-causal CSIT setting, CNS,nc=max⁡PX∣SI(X;Y∣S)C^{NS,nc}=\max_{P_{X|S}}I(X;Y\mid S)CNS,nc=maxPX∣S​​I(X;Y∣S), which was previously established, and also matches the (either classical or with NS assistance) capacity of the channel where the state is available not only (either causally or non-causally) to the transmitter but also to the receiver. While the capacity remains unchanged, the optimal probability of error for fixed message size and blocklength, in the NS-assisted causal CSIT setting can be further improved if channel state is made available to the receiver. This is in contrast to corresponding NS-assisted non-causal CSIT setting where it was previously noted that the optimal probability of error cannot be further improved by providing the state to the receiver. As a separate result we prove that non-signaling assistance, feedback, and strictly causal CSIT (i.e., transmitter knows only past channel states but not the current or future states), each of which is individually already known to not increase capacity, also cannot increase capacity when they are collectively made available to the transmitter.
We address the problem of coding for multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of point-to-point channels. However, it was recently observed that one can construct MACs from two-player non-local games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity.Here, we show that the increase in capacity from non-signaling assistance goes beyond such special channels and applies even to a simple deterministic MAC: the binary adder channel. In particular, we show that, with non-signaling assistance, a sum-rate of log⁡2(72)4≃1.5425\frac{{{{\log }_2}(72)}}{4} \simeq 1.54254log2​(72)​≃1.5425 can be reached with zero error, which beats the maximum classical sum-rate capacity of 32\frac{3}{2}23​.In order to achieve this, we show that efficient linear programs can be formulated to compute the success probability of the best non-signaling assisted code for a finite number of copies of a multiple-access channel. In particular, this can be used to give lower bounds on the zero-error non-signaling assisted capacity of multiple-access channels.
The capacity of a channel characterizes the maximum rate at which information can be transmitted through the channel asymptotically faithfully. For a channel with multiple senders and a single receiver, computing its sum capacity is possible in theory, but challenging in practice because of the nonconvex optimization involved. To address this challenge, we investigate three topics in our study. In the first part, we study the sum capacity of a family of multiple access channels (MACs) obtained from nonlocal games. For any MAC in this family, we obtain an upper bound on the sum rate that depends only on the properties of the game when allowing assistance from an arbitrary set of correlations between the senders. This approach can be used to prove separations between sum capacities when the senders are allowed to share different sets of correlations, such as classical, quantum or no-signalling correlations. We also construct a specific nonlocal game to show that the approach of bounding the sum capacity by relaxing the nonconvex optimization can give arbitrarily loose bounds. Owing to this result, in the second part, we study algorithms for non-convex optimization of a class of functions we call Lipschitz-like functions. This class includes entropic quantities, and hence these results may be of independent interest in information theory. Subsequently, in the third part, we show that one can use these techniques to compute the sum capacity of an arbitrary two-sender MACs to a fixed additive precision in quasi-polynomial time. We showcase our method by efficiently computing the sum capacity of a family of two-sender MACs for which one of the input alphabets has size two. Furthermore, we demonstrate with an example that our algorithm may compute the sum capacity to a higher precision than using the convex relaxation.