1 Introduction↩︎

The no-signaling principle is a fundamental consequence of special relativity that precludes any controllable physical influence from propagating beyond the light cone, and therefore forbids superluminal (faster than light) communication. It plays a central role in reconciling quantum non-locality — non-local correlation across space-like separated quantum systems — with relativistic causality. Indeed, quantum non-locality is a non-signaling (NS) resource,¹ and by itself such a resource shared across multiple parties, cannot allow any communication among those parties.

This leads naturally to the following questions: What if the parties sharing a NS resource are also connected by a classical communication network? Can NS assistance improve the Shannon capacity region of that classical communication network? How significant can such an improvement be? What kinds of communication networks allow significant improvements? Are such networks naturally encountered? And, how much of these improvements are achievable with quantum correlations? These fundamental questions lie at the intersection of classical and quantum information theory and define a research frontier that has experienced recent progress [1]–[4]. The motivation of this work is to further advance this frontier.

While not all NS correlations are realizable by quantum systems, the simpler formulation of NS correlations makes them more amenable to analysis than quantum correlations. Thus, NS models offer, firstly, a tractable path to explore the potential impact of quantum-nonlocality on the capacity of classical communication networks. Clearly, the quantum-assisted capacity region of a classical communication network is sandwiched between its capacity regions with and without NS-assistance. It follows then that strong benefits of quantum nonlocality can only exist where large improvements are possible through NS-assistance. In this sense, the search for large improvements in capacity due to NS-assistance, serves a similar purpose as a metal detector for a treasure hunt. Secondly, NS models, which encapsulate the maximal non-locality that is allowed by relativistic causality, are especially important within the broad framework of generalized probabilistic theories [5], [6] to explore the fundamental limits of information processing supported by non-local correlations, and thereby potentially discover new information processing principles as well as new physical theories. Thirdly, the study of NS-assisted capacity contributes new converse bounds, or a better understanding of existing converse bounds in classical information theory. Examples include the Polyanskiy-Poor-Verdu one-shot metaconverse [7], a cornerstone of finite-blocklength classical information theory, which is alternatively recovered (and found to be tight!) under NS assistance [8], and algorithmic approaches to classical converses for one-shot settings inspired by NS-assisted models [3], [9], [10]. Finally, NS-assistance is also explored in stochastic control theory for decentralized information structures [11]–[14], with several intriguing parallels, e.g., between [7], [8], [12].

Many of the results on NS-assisted capacity of classical communication networks are negative results, showing that there can be no Shannon capacity advantage from NS assistance (which subsumes quantum entanglement assistance) in certain settings. It is known, for instance, that NS assistance does not improve the Shannon capacity of a classical point to point channel[8], [9], generalizing a prior result for quantum assistance from [15]. NS assistance also does not improve the capacity region of a deterministic broadcast channel (BC) [3], or a BC where NS resources are only shared among receivers [3] (generalizing a result for the corresponding quantum-assisted setting from [2]), or a multiple access channel (MAC) where independent NS resources are shared between each transmitter and the receiver [1]. Positive results, showing strict capacity improvements from NS assistance started with the work of Quek and Shor [16] on interference channels, which introduced the key idea of translating NS and/or quantum strategies for nonlocal games into capacity improvements for carefully constructed artificial channels. This was followed by the works by Leditzky et al. [17], Seshadri et al. [18], Fawzi and Ferme [1], and Pereg et al. [19] on multiple access channels where similar advantages were established for NS and/or quantum-assistance, and by Hawellek et al. who established capacity advantages in interference channels with entangled transmitters [20]. The capacity of NS-assisted broadcast channels was studied by Fawzi and Ferme in [3], who posed the question: can NS assistance improve the Shannon capacity region of a broadcast channel? The question was answered in the affirmative in [4], somewhat surprisingly even for semi-deterministic and degraded broadcast channels where an improvement was not expected, and it was shown that for certain \(K\) user BC’s that occur naturally in wireless networks, the improvement in Shannon capacity due to NS assistance approaches a factor of \(K\). On one hand, considering that the improvements in Shannon capacity reported previously were relatively modest amounts (not exceeding 5% [18], [20] to our knowledge²), a \(K\)-fold improvement in Shannon capacity seems shockingly large (e.g., 100% improvement for \(K=2\) users, 900% for \(K=10\) users) and represents a strong ‘metal detector’ signal in our earlier analogy. On the other hand it is important to note that it is not yet known how much, if any, of this gain is actually achievable under the restriction to strictly quantum-correlations. The scenarios pinpointed in [4] provide a focused target for future quantum-theoretic analysis. For our present purpose let us note that reference [4] also considers a NS-assisted single-user fading-dirt channel model, where even larger (unbounded as channel alphabet size approaches infinity) multiplicative gains in Shannon capacity are established. The present work seeks a more fundamental understanding of these findings.

There are three classes of communication networks considered in this work. The first is a general point to point discrete memoryless channel \(\mathsf{N}_{Y|XS}\) with input \(X\), output \(Y\), and state \(S\) that is known non-causally to the transmitter. By the well known Gelfand-Pinsker Theorem [25] the classical capacity of such a channel is \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\mathsf{N}) = \max_{\mathsf{P}_{X U}} I(U;Y) - I(U;S)\). We show (Theorem 2) that the NS-assisted capacity of this channel is \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N}) = \max_{\mathsf{P}_{X|S}} I(X;Y|S)\). The form of the capacity expression is recognizable as the classical capacity of a variant of the channel setting \(\mathsf{N}\), denoted \(\bar\mathsf{N}\), where the state \(S\) is also made available to the receiver [26]. Thus, \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N}) = C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\bar\mathsf{N})\). It is noteworthy that the multiplicative gap between \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\mathsf{N})\) and \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N}) = C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\bar\mathsf{N})\) is in general unbounded (Example 1), underpinning the corresponding observation in [4]. Going beyond Shannon capacity, we study optimal probability of successful decoding (denoted as \(\eta\)) over finite blocklengths. We prove (Theorem 1) that with NS-assistance, for any finite-blocklength, the optimal probability of success over \(\mathsf{N}\) is the same as over \(\bar\mathsf{N}\), i.e., \(\eta(\mathsf{N})=\eta(\bar\mathsf{N})\). In words, with NS-assistance, the channel setting \(\mathsf{N}\) where the state \(S\) is known to the transmitter, is exactly as good as the channel setting \(\bar\mathsf{N}\) where the state \(S\) is also given to the receiver. Equivalence of finite-blocklength success probability is stronger than, and therefore implies, the equivalence of Shannon capacity, i.e., \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N}) = C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\bar\mathsf{N})\). In effect, it is as if NS-assistance allows CSIT to be shared with the receiver. This insight, which is encapsulated as the titular ‘virtual signaling of CSIT via NS-assistance,’ is the central insight of this work. The intuition of ‘virtual CSIT signaling’ is helpful to anticipate and interpret our results for the next two classes of communication networks.

The second class that we consider comprises \(2\) user discrete memoryless broadcast channels, \(\mathsf{N}_{Y_1Y_2|X}\). While in this case there is no notion of state inherent to the channel per se, it is well known that broadcast channels are intimately related to channels with state known non-causally at the transmitter. This is because the message (say, \(W_2\)) to be transmitted to a user (User \(2\)) impacts the codebook that can be used to communicate with the other user (User \(1\)). Since \(W_2\) is known non-causally (i.e., prior to the beginning of transmission) to the transmitter, it acts somewhat like a channel state that is known non-causally to the transmitter, from the perspective of the point to point communication between the transmitter and User \(1\). For a general \(2\) user discrete memoryless broadcast channel \(\mathsf{N}_{Y_1Y_2|X}\) with NS-assistance between the transmitter and User \(1\), we prove (Theorem 3) that the capacity region \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N})\) is the union (over all \(\mathsf{P}_{XU}\)) of the rate pairs \((R_1,R_2)\) such that \(R_1\leq I(X;Y_1)\), \(R_2\leq I(U;Y_2)\) and \(R_1+R_2\leq I(X;Y_1\mid U)+I(U;Y_2)\). This region is recognizable as the classical capacity region \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})\) of a related setting of \(\mathsf{N}\), where User \(2\)’s desired message \(W_2\) is provided in advance to User \(1\) as side-information. The characterization of \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})\) is available explicitly as a special case of a more general result of Kramer and Shamai in [27]. In particular, we show (Theorem 3) that \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N})=\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})=\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})\), i.e., NS assistance between transmitter and User \(1\) is as helpful as providing User \(1\) with \(W_2\), but not any more helpful than that. Note that the result is consistent with the ‘virtual signaling of CSIT’ insight, as in this case, it is as if NS-assistance to User \(1\) effectively signaled the CSIT \((W_2)\) to User \(1\). Within the class of \(2\)-user broadcast channels, we then consider the sub-class of semi-deterministic broadcast channels. For this class we characterize the capacity region even with full (tripartite) NS-assistance between the transmitter and both receivers. The capacity region is the same as if NS-assistance is provided only between the transmitter and the non-deterministic receiver. In fact if NS-assistance is provided only between the transmitter and the deterministic receiver, then it does not improve the capacity region at all compared to the classical setting (without NS assistance). This is consistent with the observation that in a semi-deterministic BC, the capacity region is unchanged if the deterministic receiver is provided the desired message of the other user as side information. We then offer a limited generalization of the semi-deterministic BC, to the stochastic BC obtained by passing the semi-deterministic BC outputs through separate erasure channels for the two users (provided that the deterministic output does not experience the worse erasure channel). The capacity region with full (tripartite) NS assistance is characterized for this setting in Corollary 2 and matches exactly the region described by Sato’s converse bound [26].

Finally, the third class that we consider comprises \(K\) user discrete memoryless broadcast channels. Our main result for this setting (Theorem 5) shows that the finite-blocklength optimal probability of successful decoding under full \((K+1)\)-partite NS assistance is the same as if each User \(k\), \(k\in[K]\) was additionally provided the desired messages of Users \(k+1,\cdots,K\) as side-information. The side-information structure intuitively corresponds to a causal encoding order where the users’ messages are encoded sequentially starting from User \(K\) and ending with User \(1\), so that in terms of the encoding for User \(k\), the messages of previously encoded users with indices \(k+1,\cdots, K\) comprise non-causal CSIT available to the encoder. Note that the ordering of users can be chosen arbitrarily.

2 Preliminaries↩︎

2.1 Notation↩︎

\(\mathbb{R}_+\) is the set of non-negative reals. \(\mathbb{N}\) is the set of positive integers. For \(n \in \mathbb{N}\), \([n] \triangleq \{1,2,\cdots, n\}\). \(A_i^j\) denotes \([A_i,A_{i+1},\cdots, A_j]\), and \(A^n\) denotes \([A_1,A_2,\cdots, A_n]\). \(\mathbb{F}_q\) is the finite field with order \(q\), where \(q\) is a power of a prime. We write \(g(n) = o(f(n))\) if \(\lim_{n\to \infty} \frac{g(n)}{f(n)}\) \(= 0\). The Cartesian product of sets \(\mathcal{A}\) and \(\mathcal{B}\) is \(\mathcal{A} \times \mathcal{B}\). The indicator function \(\mathbb{I}(p)\) returns \(1\) if the predicate \(p\) is true, and \(0\) otherwise. \(\Pr(E)\) denotes the probability of the event \(E\). “If and only if" is written as”iff".

2.2 Non-signaling correlations↩︎

For a discrete set \(\mathcal{X}\) of finite cardinality \(|\mathcal{X}|<\infty\), let \(\mathcal{P}(\mathcal{X})\) denote the set of probability mass functions on \(\mathcal{X}\). Let \(\mathcal{P}(\mathcal{Y} \mid \mathcal{X})\) denote the set of conditional probability distributions where the input variable is defined on the set \(\mathcal{X}\) and the output variable is defined on the set \(\mathcal{Y}\). Given \(\mathsf{P}_{Y_1Y_2\mid X} \in \mathcal{P}(\mathcal{Y}_1\times \mathcal{Y}_2\mid \mathcal{X})\), the conditional marginal distribution of \(Y_1\) is defined as \(\mathsf{P}_{Y_1\mid X} \in \mathcal{P}(\mathcal{Y}_1\mid \mathcal{X})\) such that \(\mathsf{P}_{Y_1\mid X}(y_1\mid x) =\sum_{y_2\in \mathcal{Y}_2} \mathsf{P}_{Y_1Y_2\mid X}(y_1,y_2\mid x)\) for all \(y_1\in \mathcal{Y}_1,x\in \mathcal{X}\). The conditional marginal distribution of \(Y_2\) is defined similarly.

For \(K\geq 2\), let \(\mathcal{P}_K^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathcal{B}_1,\cdots, \mathcal{B}_K\mid \mathcal{A}_1,\cdots, \mathcal{A}_K) \subseteq \mathcal{P}(\mathcal{B}_1\times \cdots \times \mathcal{B}_K\mid \mathcal{A}_1\times \cdots \times \mathcal{A}_K)\) be the set of \(K\)-partite non-signaling (NS) correlations (boxes), defined such that \(\mathsf{P}_{B_1B_2\cdots B_K\mid A_1A_2\cdots A_K}\in \mathcal{P}_K^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathcal{B}_1,\cdots, \mathcal{B}_K\mid \mathcal{A}_1,\cdots, \mathcal{A}_K)\) iff for all³ non-trivial bipartitions \([K]=\mathcal{U} \cup \mathcal{V}\), say \(\mathcal{U} = \{u_1,u_2,\cdots,\) \(u_m\}\), \(\mathcal{V} = \{v_1,v_2,\cdots,v_n\}\), the (conditional) marginal distribution of \((B_{u_1},\cdots, B_{u_m})\) satisfies, \[\begin{align} \label{eq:def95NS95condition} &\mathsf{P}_{B_{u_1}\cdots B_{u_m} \mid A_{u_1}\cdots A_{u_m}A_{v_1}\cdots A_{v_n}}(b_{u_1},\cdots,b_{u_m}\mid a_{u_1},\cdots, a_{u_m}, a_{v_1},\cdots, a_{v_n}) \notag \\ &=\mathsf{P}_{B_{u_1}\cdots B_{u_m} \mid A_{u_1}\cdots A_{u_m}A_{v_1}\cdots A_{v_n}}(b_{u_1},\cdots,b_{u_m}\mid a_{u_1},\cdots, a_{u_m}, a_{v_1}',\cdots, a_{v_n}') \\ &\triangleq \mathsf{P}_{B_{u_1}\cdots B_{u_m} \mid A_{u_1}\cdots A_{u_m}}(b_{u_1},\cdots,b_{u_m}\mid a_{u_1},\cdots, a_{u_m}) \end{align}\tag{1}\] for all \(\{b_{u_i},a_{u_i}\}_{i=1}^m, \{a_{v_j},a'_{v_j}\}_{j=1}^n\) with values chosen from their respective alphabets. In words, the condition says that the marginal distribution of the outputs of any subset of parties only depends on the inputs of those parties. Note that in the last step we have redefined the marginal distribution for the parties indexed by \((u_1,\cdots, u_m)\) as \(\mathsf{P}_{B_1B_2\cdots B_K\mid A_1A_2\cdots A_K}\), to reflect that it is only a function of their own inputs and outputs.

3 Problem Formulation I: Channel with State↩︎

Let \(\mathcal{X}\), \(\mathcal{Y}\) and \(\mathcal{S}\) denote the alphabets for the input, output, and state, respectively. A channel with state is described by \(\mathsf{N}= (\mathsf{N}_{Y\mid XS},\mathsf{P}_S)\). Here \(\mathsf{N}_{Y\mid XS} \in \mathcal{P}(\mathcal{Y}\mid \mathcal{X}\times \mathcal{S})\) describes the output distribution of the channel given any input and state, and \(\mathsf{P}_S \in \mathcal{P}(\mathcal{S})\) is the probability distribution of the states. A message \(W\in \mathcal{M}\) is uniformly generated and made available to the transmitter, and needs to be communicated to the receiver.

3.1 Coding for Channel with State↩︎

A coding scheme \(\mathsf{Z}\) for \(\mathsf{N}\) is specified by \(\mathsf{Z}\in \mathcal{P}(\mathcal{X} \times \mathcal{M} \mid \mathcal{M} \times \mathcal{S} \times \mathcal{Y})\). See Fig. 1. Without loss of generality, assume \(\mathcal{M} = [M]\), so that \(M = |\mathcal{M}|\). We are interested in two kinds of coding schemes (cf. [8], [21]), denoted as \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M,\mathsf{N})\) and \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})\), for \(M\in \mathbb{N}\), defined as follows.

• “Classical" (C): \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M,\mathsf{N})\) iff there exists an encoder \(\mathsf{E}\in \mathcal{P}(\mathcal{X}\mid \mathcal{M}\times \mathcal{S} \times \mathcal{Q})\), a decoder \(\mathsf{D}\in \mathcal{P}(\mathcal{M}\mid \mathcal{Y}\times \mathcal{Q})\) and a distribution \(\mathsf{P}_Q\in \mathcal{P}(\mathcal{Q})\) such that \(\mathsf{Z}(x,\hat{w} \mid w,s,y) = \sum_{q\in \mathcal{Q}} \mathsf{P}_Q(q) \mathsf{E}(x\mid w,s,q) \mathsf{D}(\hat{w}\mid y,q)\) for all \(w\in \mathcal{M}, \hat{w} \in \mathcal{M}, x\in \mathcal{X}, y\in \mathcal{Y}, s\in \mathcal{S}\).

• “Non-signaling" (NS): \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})\) iff \(\mathsf{Z}\in \mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_2(\mathcal{X},\mathcal{M}\mid \mathcal{M}\times \mathcal{S}, \mathcal{Y})\).⁴

Since any classical coding scheme is non-signaling, \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M,\mathsf{N}) \subseteq \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})\). A coding scheme \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})\) works as follows. The transmitter inputs \((W,S)\) to \(\mathsf{Z}\), and obtains the output \(X\). This \(X\) is sent through the channel \(\mathsf{N}\). The user inputs \(Y\) to \(\mathsf{Z}\), and obtains the decoded message \(\hat{W}\). For any given \(\mathsf{N}=(\mathsf{N}_{Y\mid XS}, \mathsf{P}_S)\) and \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})\), the joint distribution of all variables of interest is, \[\begin{align} &\Pr(W=w,\hat{W}=\hat{w},S=s,X=x,Y=y)\notag\\ &=\frac{1}{M} \mathsf{P}_S(s)\Pr(\hat{W}=\hat{w},X=x,Y=y\mid W=w,S=s)\\ &=\frac{1}{M} \mathsf{P}_S(s) \mathsf{N}_{Y\mid XS}(y\mid x,s) \mathsf{Z}(x,\hat{w} \mid w, s, y) \end{align}\] where the last step holds because \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})\) (cf. [8]).

Define the probability of success \(\eta(\mathsf{Z})\) associated with \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})\) as \[\begin{align} &\eta(\mathsf{Z}) \triangleq \Pr(W=\hat{W})\\ &= \frac{1}{M}\sum_{w\in \mathcal{M},s\in \mathcal{S}, x\in \mathcal{X}, y\in \mathcal{Y}} \mathsf{P}_S(s) \mathsf{N}_{Y\mid XS}(y\mid x,s) \mathsf{Z}(x,w\mid w, s, y) \label{eq:def95eta95cws} \end{align}\tag{2}\] Note that \(\eta\) also depends on \((M, \mathsf{N}_{Y\mid XS}, \mathsf{P}_S)\), but we suppress these parameters for compact notation, as they can be inferred from the context.

3.2 Classical and Non-Signaling Assisted Capacity of Channel with State↩︎

For \(n\in \mathbb{N}\), let \(\mathsf{N}^{\otimes n}= (\mathsf{N}_{Y^n\mid X^nS^n}, \mathsf{P}_{S^n})\) represent \(n\) uses of the channel \(\mathsf{N}=(\mathsf{N}_{Y\mid XS}, \mathsf{P}_S)\). Then \(\mathsf{N}^{\otimes n}\) is also a channel with state, defined such that, \[\begin{align} \begin{cases} \mathsf{N}_{Y^n\mid X^nS^n}(y^n \mid x^n, s^n) = \prod_{i=1}^n \mathsf{N}_{Y\mid XS}(y_i\mid x_i,s_i), \\ \mathsf{P}_{S^n}(s^n) = \prod_{i=1}^n \mathsf{P}_S(s_i). \end{cases} \end{align}\]

A rate \(R\in \mathbb{R}_+\) (measured in bits/channel-use) is said to be achievable classically (or with NS assistance) iff there exists a sequence of coding schemes \(\mathsf{Z}_n\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M_n,\mathsf{N}^{\otimes n})\) (or \(\mathsf{Z}_n \in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_n,\mathsf{N}^{\otimes n})\)) such that the limit of the probability of success \(\lim_{n\to \infty} \eta(\mathsf{Z}_n) = 1\) and the limit of the ratio \(\lim_{n\to \infty}\frac{\log_2 M_n}{n} \geq R\). The classical capacity \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\mathsf{N})\) (or NS assisted capacity \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N})\)) is defined as the supremum of the set of rates that are achievable classically (or with NS assistance).

3.3 Results: NS Assisted Success Probability and Capacity for Channel with State↩︎

Given a channel with state, \(\mathsf{N}=(\mathsf{N}_{Y\mid XS}, \mathsf{P}_S)\), let \(\bar{\mathsf{N}} = (\bar{\mathsf{N}}_{YS_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \mid XS}, \mathsf{P}_S)\) be another channel with state where the state is made available to the receiver (as an additional output, \(S_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\)). Formally, we define, \[\begin{align} \bar{\mathsf{N}}_{YS_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\mid XS}(y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \mid x,s) \triangleq \mathsf{N}_{Y\mid XS}(y\mid x,s) \times \mathbb{I}(s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }=s),\label{eq:defnbar} \end{align}\tag{3}\] for all \(s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\in \mathcal{S}, s \in \mathcal{S}, x\in \mathcal{X}, y\in \mathcal{Y}\). Note that \(\bar{\mathsf{N}}\) is still within the framework of channel with state. With this we are ready to present our first theorem.

Note that the LHS is the maximal (optimal) probability of success for NS assisted coding schemes over a channel with state, \(\mathsf{N}\), whereas the RHS is for NS assisted coding schemes over \(\bar{\mathsf{N}}\). The theorem says that under NS assistance, making the CSIT also available to the receiver cannot improve the maximal probability of success, i.e., any advantage in terms of optimal probability of success, of having CSIT also available to the receiver, is already available due to the NS assistance. In effect, it is as if all CSIT was already signaled to the receiver via NS assistance. This insight is what we refer to as virtual signaling of CSIT. Note that there is no actual signaling of CSIT, i.e., the receiver may not explicitly acquire any knowledge of the CSIT. The ‘virtual’ signaling of CSIT refers only to the impact/effect of NS assistance on optimal success probability. The details of the proof of Theorem 1 are left to Appendix 7. Let us provide a sketch here.

(Proof Sketch): The direction \(\max_{\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})}\eta(\mathsf{Z}) \leq \max_{\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\bar{\mathsf{N}})}\eta(\mathsf{Z})\) is obvious, as giving the CSIT to the receiver cannot hurt the optimal probability of success. To show the other direction, consider any NS assisted coding scheme \(\mathsf{Z}\) with CSIR, i.e., \[\begin{align} \mathsf{Z}(x,\hat{w}\mid [w,s],[y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M, \bar{\mathsf{N}}). \end{align}\] The square brackets on \([w,s]\) and \([y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]\) simply group inputs to the NS box that correspond to the same party. Such a scheme needs both \(Y\) and \(S_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\) at the receiver. What we will do next is to construct in two steps an NS assisted coding scheme \(\mathsf{Z}''(x,\hat{w} \mid [w,s], y) \in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M, \mathsf{N})\) that achieves the same probability of success as \(\mathsf{Z}\), but only needs \(Y\) at the receiver. This will prove the other direction. First, let \(\mathbb{C}_M\) be the cyclic permutation group operating on \([M]\). Then construct \[\begin{align} \mathsf{Z}'(x,\hat{w}\mid [w,s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) = \frac{1}{M}\sum_{\pi \in \mathbb{C}_M}\mathsf{Z}(x, \pi(\hat{w})\mid [\pi(w),s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }])\label{eq:twirl} \end{align}\tag{4}\] for all \((w,\hat{w}, x,y,s, s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} })\in \mathcal{M}^2\times \mathcal{X}\times \mathcal{Y} \times \mathcal{S}^2\). We argue that \(\eta(\mathsf{Z})=\eta(\mathsf{Z}')\), which can be seen from the fact that \(\mathsf{Z}'\) is simply a convex combination (with uniform coefficients \(1/M\)) of \(M\) schemes, each of which is \(\mathsf{Z}\) after relabeling the message indices according to the cyclic permutation \(\pi\), and that relabeling does not affect the probability of success since the message is uniformly generated.

Next, construct \[\begin{align} \mathsf{Z}''(x,\hat{w}\mid [w,s],y) = \mathsf{Z}'(x,\hat{w} \mid [w,s],[y,s]) \end{align}\] for all \((w, \hat{w}, x,y,s)\in \mathcal{M}^2\times \mathcal{X}\times \mathcal{Y} \times \mathcal{S}\). One should verify that \(\eta(\mathsf{Z}'')=\eta(\mathsf{Z}')\) simply by definition. The last thing is to verify that \(\mathsf{Z}''\) is indeed non-signaling, in particular that \(\sum_{x}\mathsf{Z}''(x,\hat{w} \mid [w,s],y) =1/M\) and that \(\sum_{\hat{w}}\mathsf{Z}''(x,\hat{w} \mid [w,s],y)\) only depends on \((x,w,s)\) (in fact only \((x,s)\)). We illustrate the idea in Fig. 2. The details appear in Appendix 7. 0◻

The proof is provided in Appendix 8. Recall that in the channel \(\bar{\mathsf{N}}\) the state \(S\) is available not only to the transmitter – as CSIT, but also to the receiver – as CSIR. It is known that the RHS of ?? represents the classical capacity of \(\bar{\mathsf{N}}\), i.e., \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\bar\mathsf{N})=\max_{\mathsf{P}_{X|S}}I(X;Y|S)\) [26]. From Theorem 1 it follows immediately that \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N})=C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\bar\mathsf{N})\). The achievability argument for ?? also follows immediately, as \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N}) = C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\bar{\mathsf{N}}) \geq C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\bar{\mathsf{N}})= RHS of \eqref{eq:capacity95NS95cws}\). To complete the proof of Theorem 2, we only need to show the converse, that the RHS of ?? serves also as an upper bound for \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N})\).

This result stands in contrast with the capacity for the corresponding classical setting, known as the Gelfand-Pinsker Theorem [26], [25], \[\begin{align} C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\mathsf{N}) = \max_{\mathsf{P}_{X U\mid S}} \big(I(U;Y) - I(U;S)\big), \end{align}\] where the maximum is taken over all joint distributions of \((X,U)\) conditioned on \(S\), \(\mathsf{P}_{XU\mid S} \in \mathcal{P}(\mathcal{X}\times \mathcal{U}\mid \mathcal{S})\) with \(|\mathcal{U}|\leq \min\{|\mathcal{X}||\mathcal{S}|, |\mathcal{Y}|+ |\mathcal{S}|-1\}\). The classical capacity of \(\mathsf{N}\) can be strictly smaller than that of \(\bar{\mathsf{N}}\). In fact, in general the gap between them can be arbitrarily large (see Example 1). However, Theorems 1 and 2 imply that \(\mathsf{N}\) and \(\bar{\mathsf{N}}\) have the same NS assisted capacity. Moreover, as an even stronger implication, \(\mathsf{N}\) and \(\bar{\mathsf{N}}\) have the same NS assisted optimal probability of success over any arbitrary fixed finite number of channel-uses.

4 Problem Formulation II: NS assistance for \(2\)-User Broadcast↩︎

In this section, we consider NS assisted coding for 2-user broadcast channels (BC), i.e., a broadcast channel with \(2\) receivers. The main result in this section is the complete characterization of the NS assisted capacity (region) of all 2-user BCs with bipartite NS assistance established between the transmitter and one of the receivers. Capacity is also characterized for a particular set of 2-user BCs with NS assistance among all parties. We begin with the formal definition of the framework of coding schemes.

A (2-user) broadcast channel is described by \(\mathsf{N}\in \mathcal{P}(\mathcal{Y}_1\times \mathcal{Y}_2\mid \mathcal{X})\), which specifies the output distribution (at the \(2\) users/receivers) given the channel’s input. Two independent messages \(W_1,W_2\) are generated at the transmitter, such that \(W_i\) is to be communicated to User \(i\), for \(i\in \{1,2\}\).

4.1 Coding schemes↩︎

A coding scheme \(\mathsf{Z}\) over the BC is specified by \(\mathsf{Z}\in \mathcal{P}(\mathcal{X}\times \mathcal{M}_1\times \mathcal{M}_2 \mid \mathcal{M}_1\times \mathcal{M}_2\times \mathcal{Y}_1\times \mathcal{Y}_2)\). See Fig. 3. Without loss of generality, assume \(\mathcal{M}_i = [M_i]\) for \(i\in \{1,2\}\), where \(M_i = |\mathcal{M}_i|\). We are interested in the following \(5\) subsets of coding schemes, denoted as \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M_1,M_2,\mathsf{N}), \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} -i}(M_1,M_2,\mathsf{N})\) for \(i\in \{0,1,2\}\) and \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_1,M_2,\mathsf{N})\), defined as follows. We will not write the domain of the variables explicitly as it is clear from the context.

• “Classical" (C): \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M,\mathsf{N})\) iff there exists an encoder \(\mathsf{E}\in \mathcal{P}(\mathcal{X}\mid \mathcal{M}_1\times \mathcal{M}_2)\) and two separate decoders \(\mathsf{D}_i \in \mathcal{P}(\mathcal{M}_i \mid \mathcal{Y}_i)\) for \(i\in \{1,2\}\), such that \(\mathsf{Z}(x,\hat{w}_1,\hat{w}_2 \mid [w_1,w_2],y_1,y_2)= \mathsf{E}(x\mid w_1,w_2) \times \mathsf{D}_1(\hat{w}_1\mid y_1) \times \mathsf{D}_2(\hat{w}_2\mid y_2)\), concisely written as \(\mathsf{Z}=\mathsf{E}\times \mathsf{D}_1\times \mathsf{D}_2\).

• “Bipartite NS assistance between the two users" (NS-0): \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} }(M,\mathsf{N})\) iff there exists an encoder \(\mathsf{E}\in \mathcal{P}(\mathcal{X} \mid \mathcal{M}_1\times \mathcal{M}_2)\) and an NS assisted bipartite decoder \(\mathsf{D}\in \mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_2(\mathcal{M}_1, \mathcal{M}_2\mid \mathcal{Y}_1, \mathcal{Y}_2)\), such that \(\mathsf{Z}(x,\hat{w}_1,\hat{w}_2\mid [w_1,w_2], y_1,y_2) = \mathsf{E}(x\mid w_1,w_2)\times \mathsf{D}(\hat{w}_1,\hat{w}_2\mid y_1,y_2)\), i.e., \(\mathsf{Z}=\mathsf{E}\times \mathsf{D}\). This setting allows a bipartite NS box shared only between the two receivers. There is no communication between the two receivers.

• “Bipartite NS assistance between the transmitter and User \(i\)" (NS-\(i\)): For \(i\in \{1,2\}\),
  \(\mathsf{Z}\in\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} \text{-}{i}}(M,\mathsf{N})\) iff there exists \(\mathsf{Z}_i \in \mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_2(\mathcal{X}, \mathcal{M}_i \mid \mathcal{M}_1\times \mathcal{M}_2, \mathcal{Y}_i)\) and a separate decoder \(\mathsf{D}_j\in \mathcal{P}(\mathcal{M}_j\mid \mathcal{Y}_j)\) (\(\{j\}=\{1,2\}\setminus \{i\}\)), such that \(\mathsf{Z}(x,\hat{w}_1,\hat{w}_2\mid [w_1,w_2],y_1,y_2) = \mathsf{Z}_i(x,\hat{w}_i\mid [w_1,w_2], y_i)\times D_j(\hat{w}_j\mid y_j)\), i.e., \(\mathsf{Z}=\mathsf{Z}_i\times \mathsf{D}_j\).

• “Full NS assistance between three parties" (NS): \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,\mathsf{N})\) iff \(\mathsf{Z}\in \mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_3(\mathcal{X},\mathcal{M}_1,\mathcal{M}_2\mid \mathcal{M}_1\times\mathcal{M}_2,\mathcal{Y}_1,\mathcal{Y}_2)\).

Clearly, \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(M_1,M_2,\mathsf{N}) \subseteq \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} \text{\tiny-}{i}}(M_1,M_2,\mathsf{N}) \subseteq \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_1,M_2,\mathsf{N})\) for \(i\in \{0,1,2\}\). A coding scheme \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_1,M_2,\mathsf{N})\) works as follows. The transmitter inputs \((W_1,W_2)\) to \(\mathsf{Z}\), and obtains the output \(X\). This \(X\) is sent through the channel \(\mathsf{N}\). For \(k\in \{1,2\}\), User \(k\) inputs \(Y_k\) to \(\mathsf{Z}\), and obtains the decoded message \(\hat{W}_k\). Given \(\mathsf{N}\in \mathcal{P}(\mathcal{Y}_1\times \mathcal{Y}_2\mid \mathcal{X})\) and \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_1,M_2,N)\), the joint distribution of all variables of interest is, \[\begin{align} &\Pr(\hat{W}_i=\hat{w}_i, W_j=w_j,X=x,Y_k=y_k,\forall (i,j,k)\in\{1,2\}^3) \\ &=\frac{1}{M_1M_2} \Pr(\hat{W}_1=\hat{w}_1, \hat{W}_2= \hat{w}_2, X=x,Y_1=y_1,Y_2=y_2 \mid W_1=w_1,W_2=w_2)\\ &=\frac{1}{M_1M_2} \mathsf{Z}(x,\hat{w}_1,\hat{w}_2\mid [w_1,w_2],y_1,y_2)\times \mathsf{N}(y_1,y_2\mid x) \end{align}\] where the last step holds because \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_1,M_2,\mathsf{N})\) (cf. [3]).

The joint probability of success associated with \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_1,M_2,\mathsf{N})\) is defined as \[\begin{align} &\eta(\mathsf{Z}) \triangleq \Pr(W_1=\hat{W}_1,W_2=\hat{W}_2) \notag \\ &= \frac{1}{M_1M_2} \sum_{w_1,w_2,x,y_1,y_2} \mathsf{Z}(x,w_1,w_2\mid [w_1,w_2],y_1,y_2)\times \mathsf{N}(y_1,y_2\mid x) \end{align}\]

The individual probability of success associated with \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_1,M_2,\mathsf{N})\) for message \(W_i\), \(i\in \{1,2\}\) is similarly defined as, (with \(\{j\}=\{1,2\}\setminus \{i\}\)) \[\begin{align} &\eta_i(\mathsf{Z}) \triangleq \Pr(W_i=\hat{W}_i) \notag \\ &= \frac{1}{M_1M_2} \sum_{w_i,w_j,\hat{w}_j,x,y_1,y_2} N(y_1,y_2\mid x) \times \begin{cases} \mathsf{Z}(x,w_1,\hat{w}_2\mid [w_1,w_2],y_1,y_2), & i=1\\ \mathsf{Z}(x,\hat{w}_1,w_2\mid [w_1,w_2],y_1,y_2), & i=2 \end{cases} \end{align}\]

4.2 Achievable rate pairs and capacity region↩︎

For \(n\in \mathbb{N}\), let \(\mathsf{N}^{\otimes n} \in \mathcal{P}(\mathcal{Y}_1^n \times \mathcal{Y}_2^n \mid \mathcal{X}^n)\) be \(n\) uses of the broadcast channel \(\mathsf{N}\), defined as \[\begin{align} \mathsf{N}^{\otimes n}(y_1^n, y_2^n \mid x^n) = \prod_{i=1}^n \mathsf{N}(y_{1,i}, y_{2,i}\mid x_i). \end{align}\] For \(\mathsf{str}\in \{``\mathrm{C}", ``\mathrm{NS}\text{-}0", ``\mathrm{NS}\text{-}1", ``\mathrm{NS}\text{-}2", ``\mathrm{NS}"\}\), a rate pair \((R_1,R_2) \in \mathbb{R}_+^2\) is said to be achievable

• classically, iff \(\mathsf{str}= ``\mathrm{C}"\)

• by bipartite NS assistance between the two users iff \(\mathsf{str}=``\mathrm{NS}\text{-}0"\)

• by bipartite NS assistance between the transmitter and User 1 iff \(\mathsf{str}=``\mathrm{NS}\text{-}1"\)

• by bipartite NS assistance between the transmitter and User 2 iff \(\mathsf{str}=``\mathrm{NS}\text{-}2"\)

• by full NS assistance among the three parties iff \(\mathsf{str}=``\mathrm{NS}"\)

and iff there exists a sequence of coding schemes \(\mathsf{Z}_n\in \mathcal{Z}^{\mathsf{str}}(M_{1,n},M_{2,n},\mathsf{N}^{\otimes n})\) such that \(\lim_{n\to \infty} \eta(\mathsf{Z}) = 1\) and \(\lim_{n\to \infty}\frac{\log_2(M_{i,n})}{n}\geq R_i\) for \(i\in \{1,2\}\). Equivalently, one can replace the first condition with \(\lim_{n\to \infty}\eta_i(\mathsf{Z}) = 1\) for \(i\in \{1,2\}\), as one implies the other.

The capacity region \(\mathcal{C}^{\mathsf{str}}\) for \(\mathsf{str}\in \{``\mathrm{C}", ``\mathrm{NS}\text{-}0", ``\mathrm{NS}\text{-}1", ``\mathrm{NS}\text{-}2", ``\mathrm{NS}" \}\) is defined as the closure of the set of rate pairs achievable by the corresponding class of coding schemes.

4.3 Coding with side information↩︎

For our purpose, it is useful to introduce another setting where User \(1\) is provided with the message \(W_2\), a special case of the problem studied in [27]. Let us refer to this setting as coding with side information (at User \(1\)). Given a broadcast channel \(\mathsf{N}\), a coding scheme with side information is specified by \(\mathsf{Z}\in \mathcal{P}(\mathcal{X}\times \mathcal{M}_1\times \mathcal{M}_2 \mid [\mathcal{M}_1\times \mathcal{M}_2] \times [\mathcal{Y}_1\times \mathcal{M}_2]\times \mathcal{Y}_2)\). The difference now is that User \(1\) decodes the message \(W_1\) from \(Y_1\) and \(W_2\) together, since \(W_2\) is given as its side information. We can similarly introduce the classes of coding schemes according to the availability of NS assistance as in Section 4.1. In particular,

• \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }\) is defined such that \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }\) iff there exists an encoder \(\mathsf{E}\in \mathcal{P}(\mathcal{X}\mid \mathcal{M}_1\times \mathcal{M}_2)\) and two separate decoders \(\mathsf{D}_1 \in \mathcal{P}(\mathcal{M}_1 \mid \mathcal{Y}_1\times \mathcal{M}_2)\), \(\mathsf{D}_2 \in \mathcal{P}(\mathcal{M}_2 \mid \mathcal{Y}_2)\) such that \(\mathsf{Z}(x,\hat{w}_1,\hat{w}_2 \mid [w_1,w_2],[y_1,w_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }],y_2)= \mathsf{E}(x\mid w_1,w_2) \times \mathsf{D}_1(\hat{w}_1\mid y_1,w_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }) \times \mathsf{D}_2(\hat{w}_2\mid y_2)\), i.e., \(\mathsf{Z}=\mathsf{E}\times \mathsf{D}_1\times \mathsf{D}_2\).

• \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }\) is defined such that \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }\) iff there exists \(\mathsf{Z}_1\in \mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_2(\mathcal{X},\mathcal{M}_1\mid \mathcal{M}_1\times \mathcal{M}_2,\mathcal{Y}_1\times \mathcal{M}_2)\) and a separate decoder \(\mathsf{D}_2\in \mathcal{P}(\mathcal{M}_2\mid \mathcal{Y}_2)\), such that \(\mathsf{Z}(x,\hat{w}_1,\hat{w}_2\mid [w_1,w_2],[y_1,w_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }],y_2) = \mathsf{Z}_1(x,\hat{w}_1\mid [w_1,w_2],[y_1,w_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }])\times \mathsf{D}_2(\hat{w}_2\mid y_2)\), i.e., \(\mathsf{Z}=\mathsf{Z}_1\times \mathsf{D}_2\).

• \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }=\mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_3(\mathcal{X},\mathcal{M}_1,\mathcal{M}_2\mid \mathcal{M}_1\times \mathcal{M}_2,\mathcal{Y}_1\times \mathcal{M}_2,\mathcal{Y}_2)\).

The extra label “\(\mathrm{SI}\text{-}1\)" indicates that the side information \(W_2\) is available to User 1. One should note the extra input at User \(1\) in the coding schemes. A coding scheme \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(M_1,M_2,\mathsf{N})\) works as follows. The transmitter inputs \((W_1,W_2)\) to \(\mathsf{Z}\), and obtains the output \(X\). This \(X\) goes through the channel \(\mathsf{N}\). User \(1\) inputs \((Y_1,W_2)\) to \(\mathsf{Z}\), and obtains the decoded message \(\hat{W}_1\). User \(2\) inputs \(Y_2\) to \(\mathsf{Z}\), and obtains the decoded message \(\hat{W}_2\). For \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(M_1,M_2,\mathsf{N})\), the joint probability of success is \[\begin{align} &\eta(\mathsf{Z}) = \Pr(W_1=\hat{W}_1, W_2=\hat{W}_2)\notag \\ &=\frac{1}{M_1M_2} \sum_{w_1,w_2,x,y_1,y_2} \mathsf{Z}(x,w_1,w_2\mid [w_1,w_2],[y_1,w_2],y_2) \times \mathsf{N}(y_1,y_2\mid x) \end{align}\] and the individual probability of success is, for \(i\in \{1,2\}\), \(\{j\}=\{1,2\}\setminus\{i\}\), \[\begin{align} &\eta_i(\mathsf{Z}) = \Pr(W_i=\hat{W}_i) \notag \\ &= \frac{1}{M_1M_2} \sum_{w_i,w_j,\hat{w}_j,x,y_1,y_2} \mathsf{N}(y_1,y_2\mid x) \times \begin{cases} \mathsf{Z}(x,w_1,\hat{w}_2\mid [w_1,w_2],[y_1,w_2],y_2), & i=1\\ \mathsf{Z}(x,\hat{w}_1,w_2\mid [w_1,w_2],[y_1,w_2],y_2), & i=2 \end{cases} \end{align}\] We accordingly define the capacity regions with side information at User \(1\) as \(\mathcal{C}^{\mathsf{str},\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }\), for \(\mathsf{str}\in \{``\mathrm{C}", ``\mathrm{NS}\text{-}0", ``\mathrm{NS}\text{-}1", ``\mathrm{NS}\text{-}2", ``\mathrm{NS}"\}\).

4.4 Results: NS Assisted \(2\)-User BC↩︎

It suffices to present the results on the classes \(``\mathrm{C}", ``\mathrm{NS}\text{-}0", ``\mathrm{NS}\text{-}1"\) and \(``\mathrm{NS}"\) because the result of \(``\mathrm{NS}\text{-}2"\) can be easily obtained by that of \(``\mathrm{NS}\text{-}1"\) by exchanging the two users’ indices. Given a broadcast channel \(\mathsf{N}\), it is useful to define the following two regions of rate pairs \((R_1,R_2)\). The first region is \[\begin{align} \mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }(\mathsf{N}) \triangleq \bigcup_{\mathsf{P}_{XU}}\left\{ \begin{array}{l} (R_1,R_2)\colon \\ R_1 \leq I(X;Y_1) \\ R_2 \leq I(U;Y_2) \\ R_1 + R_2 \leq I(X;Y_1\mid U) + I(U;Y_2) \end{array} \right. \end{align}\] where the union is over all \(\mathsf{P}_{XU}\in \mathcal{P}(\mathcal{X}\times \mathcal{U})\). It suffices to consider \(|\mathcal{U}| < |\mathcal{X}|\). We point out that \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }\) is the capacity region for classical coding schemes when \(W_2\) is known to User \(1\). This is established in [27], and ‘KS’ stands for the initials of the authors (Kramer, Shamai).

The second region is, \[\begin{align} \mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} }(\mathsf{N}) \triangleq \bigcup_{\mathsf{P}_X} \left\{ \begin{array}{l} (R_1,R_2)\colon \\ R_1 \leq I(X;Y_1) \\ R_2 \leq I(X;Y_2) \\ R_1 + R_2 \leq \min_{\mathsf{N}'} I(X;Y_1',Y_2') \end{array} \right. \end{align}\] where the union is over all \(\mathsf{P}_X\in \mathcal{P}(\mathcal{X})\), and the minimization of the bound on \(R_1+R_2\) is taken over all channels \(\mathsf{N}'\in \mathcal{P}(\mathcal{Y}_1\times \mathcal{Y}_2\mid \mathcal{X})\) (with \(Y_1',Y_2'\) denoting the outputs of \(\mathsf{N}'\)) such that \(\sum_{y_2}\mathsf{N}'(y_1,y_2\mid x) = \sum_{y_2}\mathsf{N}(y_1,y_2\mid x)\) and \(\sum_{y_1}\mathsf{N}'(y_1,y_2\mid x) = \sum_{y_1}\mathsf{N}(y_1,y_2\mid x)\), meaning that \(\mathsf{N}\) and \(\mathsf{N}'\) have the same marginal distributions for each user individually. We point out that \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} }\) serves as an outer bound of the classical capacity region \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\mathsf{N})\) for any broadcast channel \(\mathsf{N}\) [26], but it is generally not tight.

Fawzi and Fermé established in [3] that if NS assistance is only available between the two receivers, then it does not improve the capacity region, i.e., \[\begin{align} \mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\mathsf{N}) = \mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} }(\mathsf{N}). \end{align}\] This follows from the stronger result, also established in [3], that the individual probabilities of success \((\eta_1(\mathsf{Z}), \eta_2(\mathsf{Z}))\) cannot be improved by the receiver-side NS assistance.⁵

Since the classical capacity of a general broadcast channel \(\mathsf{N}\) is unknown, \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} {\mathrm{\scriptscriptstyle NS\text{-}0}} }(\mathsf{N})\) is also open for general \(\mathsf{N}\). Fortunately, our next result finds the solution for \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N})\) for general \(\mathsf{N}\).

Since \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }(\mathsf{N})\) has a computable form, Theorem 3 provides a computable form for \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N})\) and \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})\) in general. The proof is presented in Appendix 9. Recall that \(C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N}) = \mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }(\mathsf{N})\) is established in [27], and \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N}) \supseteq \mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})\) by definition. Therefore, it suffices to prove \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N})=\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})\), and that \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N}) \subseteq \mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }(\mathsf{N})\).

Next, we shift our focus to the fully NS assisted capacity region.

The proof is given in Appendix 11. Note that Theorem 4 says that the well-known Sato’s outer bound for the classical capacity region holds for fully NS assisted capacity region as well.

Before we present the next result, let \(\mathcal{N}^{\mathchoice {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} }\) be the set of 2-user BCs where User \(2\) has a deterministic channel, i.e., \(Y_2=f(X)\) is a function of \(X\). This is known as the set of semi-deterministic broadcast channels (for which User \(2\) has the deterministic channel, whereas the channel for User \(1\) remains general). The following corollary is the characterization of the fully NS assisted capacity region for semi-deterministic broadcast channels.

We are able to generalize the result beyond semi-deterministic BCs (Corollary 1) to a subset of semi-deterministic erasure BCs (Corollary 2) and to parallel reversely semi-deterministic BCs (Corollary 3).

Let us first define the set of semi-deterministic erasure BCs. For \(0\leq \gamma_1, \gamma_2\leq 1\), let \(\mathcal{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }(\gamma_1,\gamma_2)\) be the set of semi-deterministic erasure broadcast channels, obtained by concatenating erasure channels, with erasure probability \(\gamma_i\) to User \(i\)’s output of a semi-deterministic broadcast channel, for \(i\in \{1,2\}\). Formally, a channel \(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{\tilde{Y}_1\tilde{Y}_2\mid X} \in \mathcal{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }(\gamma_1,\gamma_2) \subseteq \mathcal{P}((\mathcal{Y}_1\cup \{\phi\}) \times (\mathcal{Y}_2\cup \{\phi\}) \mid \mathcal{X})\) iff there exists \(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} } \in \mathcal{N}^{\mathchoice {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} } \subseteq \mathcal{P}(\mathcal{Y}_1\times \mathcal{Y}_2 \mid \mathcal{X})\), \(\phi\not\in \mathcal{X}\cup \mathcal{Y}_1\cup \mathcal{Y}_2\), such that for \(i\in \{1,2\}\), \[\begin{align} \mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{\tilde{Y}_i\mid X}(\tilde{y}_i \mid x) = \begin{cases} \mathsf{N}_{Y_i\mid X}^{\mathchoice {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} }(\tilde{y}_i \mid x) \times (1-\gamma_i), & \tilde{y}_i \in \mathcal{Y}_i\\ \gamma_i, & \tilde{y}_i = \phi \end{cases} \end{align}\] where \(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} }_{Y_i\mid X}\) and \(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{Y_i\mid X}\) are the marginal distributions for User \(i\) of channels \(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} }_{Y_i\mid X}\) and \(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{\tilde{Y}_i\mid X}\) , respectively.

Theorem 3 and Theorem 4 already showed that \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }=C^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }\subseteq C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }\subseteq \mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} }\) for any channel. Therefore, the proof of Corollary 2 can be completed by showing that \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }\big(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{\tilde{Y}_1\tilde{Y}_2\mid X}\big)\) equals \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} }\big(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{\tilde{Y}_1\tilde{Y}_2\mid X}\big)\), with both evaluating to ?? . The details appear in Appendix 12.

Let us next define the set of parallel reversely semi-deterministic BCs. See Fig. 4 for an illustration. Let \({\sf N}'_{Y_1'Y_2'\mid X'}\) be a semi-deterministic BC where User \(2\)’s output \(Y_2'\) is deterministic given \(X'\), (i.e., \(Y_2' = f(X')\)), and let \({\sf N}''_{Y_1''Y_2''\mid X''}\) be another semi-deterministic BC where the output \(Y_1''\) of User \(1\) is deterministic given \(X''\), (i.e., \(Y_1'' = g(X'')\)). Now let \({\sf N}_{Y_1Y_2\mid X}\) be a BC for which \(X = (X',X'')\), \(Y_1 = (Y_1',Y_1'')\) and \(Y_2 = (Y_2',Y_2'')\), are obtained by placing \({\sf N}'_{Y_1'Y_2'\mid X'}\) and \({\sf N}''_{Y_1''Y_2''\mid X''}\) in parallel. Formally, \[\begin{align} {\sf N}_{Y_1Y_2\mid X}(y_1, y_2\mid x) = {\sf N}'_{Y_1'Y_2'\mid X'}(y_1', y_2'\mid x') \times {\sf N}''_{Y_1''Y_2''\mid X''}(y_1'', y_2''\mid x''), \end{align}\] where \(x=(x',x''), y_1 = (y_1',y_1''), y_2 = (y_2', y_2'')\). We say that the BC \({\sf N}_{Y_1Y_2\mid X}\) is parallel reversely semi-deterministic.

The proof of Corollary 3 is done by observing that for a parallel reversely semi-deterministic BC, \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} }\) is achieved by independently applying Theorem 3 to \({\sf N}'_{Y_1'Y_2'\mid X'}\) and \({\sf N}''_{Y_1''Y_2''\mid X''}\) and taking their Minkowski sum, for every \(\mathsf{P}_{X'}\) and \(\mathsf{P}_{X''}\). We present the details in Appendix 13.

5 Extension: NS-assisted \(K\)-user Broadcast with User Side information↩︎

In this section, we apply the insights gained from previous sections to the \(K\)-user broadcast channels with user side information. A \(K\)-user broadcast channel is described by \(\mathsf{N}\in \mathcal{P}(\mathcal{Y}_1\times \mathcal{Y}_2\times \cdots \times \mathcal{Y}_K\mid \mathcal{X})\). For \(k\in [K]\), let \(W_k\) be an independent message for User \(k\), and let \(\mathcal{W}_k \subseteq [K]\setminus \{k\}\), so that for \(k\in [K]\), User \(k\) has \(\{W_j\}_{j\in \mathcal{W}_k}\) as its side information. In this section let us only consider full NS assistance among all \(K+1\) parties (including the transmitter and \(K\) users).

To have a concise notation, let \(\mathcal{S}_k \triangleq \prod_{j\in \mathcal{W}_k}\mathcal{M}_j\) for \(k\in [K]\). Without loss of generality, assume \(\mathcal{M}_k = [M_k]\), so that \(M_k = |\mathcal{M}_k|\), for \(k\in [K]\). The set of fully NS assisted coding schemes with side information is defined as, \[\begin{align} \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=[K];M_1,\cdots, M_K) \triangleq \mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_{K+1} {\left( \begin{matrix} \mathcal{X} \\ \mathcal{M}_1 \\ \mathcal{M}_2 \\ \vdots \\ \mathcal{M}_K \end{matrix} \left| \begin{matrix} \prod_{k=1}^K \mathcal{M}_k \\ \mathcal{Y}_1 \times \mathcal{S}_1 \\ \mathcal{Y}_2 \times \mathcal{S}_2 \\ \vdots \\ \mathcal{Y}_K \times \mathcal{S}_K \end{matrix} \right. \right)}. \end{align}\] Note that we write the parameters of \(\mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_{K+1}\) in a way that each party appears in a separate row. The first parameter ‘\(\mathrm{SI}=[K]\)’ indicates that all \(K\) users have side information available. A coding scheme \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=[K];M_1,\cdots, M_K)\) works as follows. Let \(\mathbf{W}=[W_1,W_2,\cdots, W_K]\), \(S_k = (W_j)_{j\in \mathcal{W}_k}\) for \(k\in [K]\). The transmitter inputs \(\mathbf{W}\) to \(\mathsf{Z}\), and obtains the output \(X\). This \(X\) is sent through the channel \(\mathsf{N}\). For \(k\in [K]\), User \(k\) inputs \((Y_k, S_k)\) to \(\mathsf{Z}\), and obtains the decoded message \(\hat{W}_k\). Given \(\mathsf{N}\) and \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=[K];M_1,\cdots, M_K)\), the joint distribution of all variables of interest is (using the ‘bold’ notation, e.g., \(\mathbf{A}\) to represent \([A_1,A_2,\cdots, A_K]\)), \[\begin{align} &\Pr(\hat{\mathbf{W}} =\hat{\mathbf{w}}, {\mathbf{W}}=\mathbf{w},X=x,{\boldsymbol{Y}}={\boldsymbol{y}}) \notag \\ &=\frac{1}{\prod_{k=1}^K M_k} \Pr(\hat{\mathbf{W}}=\hat{\mathbf{w}}, X=x, \mathbf{Y}=\mathbf{y} \mid \mathbf{W}=\mathbf{w})\\ &= \frac{1}{\prod_{k=1}^K M_k} \mathsf{N}(\mathbf{y}\mid x) \times \mathsf{Z}{ \left( \begin{matrix} x \\ \hat{w}_1 \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} \mathbf{w} \\ [y_1,s_1] \\ [y_2,s_2] \\ \vdots \\ [y_K,s_K] \end{matrix} \right. \right)} \end{align}\] where \(s_k \triangleq (w_j)_{j\in \mathcal{W}_k} \in \mathcal{S}_k\) for \(k\in [K]\).

We also consider the cases when the side information becomes unavailable at some users. To this end we accordingly define \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=\mathcal{K})\) (the parameters \(M_1,\cdots, M_K\) are suppressed), for \(\mathcal{K}\subseteq [K]\), indicating that the side information \(S_k\) is only available for User \(k\in \mathcal{K}\). Equivalently, the side information is removed from User \(j\) for \(j\in [K]\setminus \mathcal{K}\). As an example,

\[\begin{align} \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=\{2,\cdots, K\})\triangleq \mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_{K+1} { \left( \begin{matrix} \mathcal{X} \\ \mathcal{M}_1 \\ \mathcal{M}_2 \\ \vdots \\ \mathcal{M}_K \end{matrix} \left| \begin{matrix} \prod_{k=1}^K \mathcal{M}_k \\ \mathcal{Y}_1 \\ \mathcal{Y}_2 \times \mathcal{S}_2 \\ \vdots \\ \mathcal{Y}_K \times \mathcal{S}_K \end{matrix} \right. \right)} \end{align}\] and note that \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=\{2,\cdots, K\})\) does not allow an input of \(S_1\) at User \(1\).

Our main goal of this section is to study and compare the optimal probability of success corresponding to different side information availabilities at the users, assuming full NS assistance. To this end, let \(\eta(\mathsf{Z})=\Pr(\hat{\mathbf{W}}=\mathbf{W})\) and for \(\mathcal{K} \subseteq [K]\), let \[\begin{align} \eta_{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }^*(\mathrm{SI}=\mathcal{K}) \triangleq \max_{\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=\mathcal{K})} \eta(\mathsf{Z}) \end{align}\] be the optimal (joint) probability of success of the fully NS-assisted coding schemes with user side information only available to each User \(k\), such that \(k\in \mathcal{K}\). Note that this value also depends on \((M_1,\cdots, M_K)\) and the channel \(\mathsf{N}\) but those parameters are suppressed for compact notation. Certainly, since user side information cannot hurt the optimal probability of success, we have \[\begin{align} \eta_{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }^*(\mathrm{SI}=\mathcal{K}) \geq \eta_{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }^*(\mathrm{SI}=\mathcal{K}') \end{align}\] as long as \(\mathcal{K} \supseteq \mathcal{K}'\).

The main theorem of this section is the following.

The theorem says that the optimal probability of success of fully NS-assisted coding schemes does not change (decrease) if \(S_k\) is removed from User \(k\), provided that \(W_k\) is not available as side information to any user. The proof is presented in Appendix 14. The next corollary follows directly from Theorem 5.

The corollary says that if the side information structure is defined such that each User \(k\) has \(\{W_j\}_{j>k}\) as side information, for all \(k\in [K]\), then such side information does not help the probability of success at all, with full NS assistance.

The immediate consequence of Corollary 4 is that the (fully) NS assisted capacity region of a \(K\)-user broadcast channel does not change if in addition each User \(k, k\in[K]\) is provided in advance all \(\{W_j\}_{j>k}\). This equivalence may provide useful insights for future studies of NS assisted index coding [32], topological interference management [33], linear computation broadcast [34], [35], coded caching [36], and network coding problems [37].

6 Conclusion↩︎

The key insight of this work, encapsulated as ‘virtual CSIT signaling via NS assistance,’ emerged from our study of the NS-assisted capacity of a point to point channel with non-causal CSIT. Following this insight, we found explicit computable NS-assisted capacity (region) expressions for a series of network communication problems. Let us conclude by pointing out a few promising directions for future work. First, an important open question is to determine if Sato’s outer bound always matches the fully NS assisted capacity region of a BC. Note that this possibility is supported by all available results thus far. Second, a promising avenue, based on Theorem 5, is to explore the NS assisted capacity of a BC with various forms of classical side information at each receiver, which includes the NS-assisted index coding problem as a most interesting special case. Third, another fundamental open problem is to characterize how the ‘virtual CSIT signaling’ result generalizes if the message is not uniformly distributed, which would impact the twirling argument. Last but not the least, an important direction for future work is to use the strongest ‘metal detector’ signals produced by NS-assisted capacity analysis, to search for the most significant capacity advantages achievable with quantum-correlations.

7 Proof of Theorem 1↩︎

We only need to show that \(\max_{\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,~\mathsf{N})}\eta(\mathsf{Z}) \geq \max_{\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M,~\bar{\mathsf{N}})}\eta(\mathsf{Z})\). Given any coding scheme \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M, \bar{\mathsf{N}})\), define \[\begin{align} \mathsf{Z}'(x,\hat{w}\mid [w,s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \triangleq \frac{1}{M}\sum_{\pi \in \mathbb{C}_M}\mathsf{Z}(x, \pi(\hat{w})\mid [\pi(w),s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \end{align}\] for \((w,\hat{w}, x,y,s,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} })\in \mathcal{M}^2\times \mathcal{X}\times \mathcal{Y} \times \mathcal{S}^2\), and \[\begin{align} \mathsf{Z}''(x,\hat{w}\mid [w,s],y) \triangleq \mathsf{Z}'(x,\hat{w} \mid [w,s],[y,s]), \end{align}\] for \((w,\hat{w}, x,y,s)\in \mathcal{M}^2\times \mathcal{X}\times \mathcal{Y} \times \mathcal{S}\), where \(\mathbb{C}_M\) is the cyclic permutation group operating on \([M]\).

We claim that \(\mathsf{Z}'\) and \(\mathsf{Z}''\) are non-signaling, and leave the proof to the end of this section. Recall that \[\begin{align} \bar{\mathsf{N}}_{YS_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\mid XS}(y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \mid x,s) \triangleq \mathsf{N}_{Y\mid XS}(y\mid x,s) \times \mathbb{I}(s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }=s). \end{align}\] In the following, we omit writing the domain of the variables as it is clear from the context. By the definitions of the probability of success and \(\bar{\mathsf{N}}\), \[\begin{align} \eta(\mathsf{Z}) &= \frac{1}{M} \sum_{w, s, x,y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }} \mathsf{P}_S(s) \times \bar{\mathsf{N}}_{YS_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\mid XS}(y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\mid x,s) \times \mathsf{Z}(x,w \mid [w,s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \\ &= \frac{1}{M} \sum_{s , x,y} \mathsf{P}_S(s)\times \mathsf{N}_{Y\mid XS}(y\mid x,s) \times \sum_{w\in [M]} \mathsf{Z}(x,w \mid [w,s], [y,s]) \end{align}\] whereas \[\begin{align} \eta(\mathsf{Z}') &= \frac{1}{M} \sum_{w, s, x,y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }} \mathsf{P}_S(s) \times \bar{\mathsf{N}}_{YS_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\mid XS}(y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\mid x,s) \times \mathsf{Z}'(x,w \mid [w,s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \\ &= \frac{1}{M} \sum_{s,x,y} \mathsf{P}_S(s)\times \mathsf{N}_{Y\mid XS}(y\mid x,s) \times \sum_{w\in[M]} \mathsf{Z}'(x,w \mid [w,s], [y,s]). \end{align}\] Now note that, for any \(s,x,y\), \[\begin{align} &\sum_{w\in[M]}\mathsf{Z}'(x,w \mid [w,s], [y,s]) \notag \\ &= \frac{1}{M}\sum_{w\in [M]} \sum_{\pi\in \mathbb{C}_M} \mathsf{Z}(x,\pi(w) \mid [\pi(w),s],[y,s]) \\ &= \frac{1}{M}\sum_{w\in [M]} \sum_{i\in [M]} \mathsf{Z}(x, i \mid [i,s],[y,s]) \\ &= \sum_{i\in [M]} \mathsf{Z}(x, i \mid [i,s],[y,s])\\ &= \sum_{w\in [M]} \mathsf{Z}(x, w \mid [w,s],[y,s]) \end{align}\] It follows that \(\eta(\mathsf{Z}) = \eta(\mathsf{Z}')\). Again by definition, \[\begin{align} \eta(\mathsf{Z}'') &= \frac{1}{M} \sum_{s,x,y}\mathsf{P}_S(s)\times \mathsf{N}_{Y\mid XS}(y\mid x,s) \times \sum_{w\in [M]} \mathsf{Z}''(x,w\mid [w,s],y) \\ &=\frac{1}{M} \sum_{s,x,y} \mathsf{P}_S(s)\times \mathsf{N}_{Y\mid XS}(y\mid x,s) \times \sum_{w\in [M]} \mathsf{Z}'(x,w\mid [w,s],[y,s]) \end{align}\] and therefore \(\eta(\mathsf{Z}'') = \eta(\mathsf{Z}')\). This shows that \(\eta(\mathsf{Z}'')=\eta(\mathsf{Z})\).

Let us now verify that \(\mathsf{Z}'\) and \(\mathsf{Z}''\) are non-signaling. It is not difficult to verify that \(\mathsf{Z}' \in \mathcal{P}(\mathcal{X}\times \mathcal{M}\mid \mathcal{M}\times \mathcal{S}\times \mathcal{Y}\times \mathcal{S})\) and \(\mathsf{Z}'' \in \mathcal{P}(\mathcal{X}\times \mathcal{M}\mid \mathcal{M}\times \mathcal{S}\times \mathcal{Y})\) are valid conditional distributions. Then, since \(\mathsf{Z}\) is non-signaling, \[\begin{align} \sum_{x}\mathsf{Z}(x,\hat{w} \mid [w,s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \triangleq \mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }(\hat{w}\mid [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \end{align}\] is a function of only \((\hat{w},y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} })\), and \[\begin{align} \sum_{\hat{w}}\mathsf{Z}(x,\hat{w} \mid [w,s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \triangleq \mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} }(x\mid [w,s]) \end{align}\] is a function of only \((x,w,s)\). We then have \[\begin{align} &\sum_{x}\mathsf{Z}'(x,\hat{w} \mid [w,s],[y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }])\notag \\ &= \frac{1}{M}\sum_{\pi\in \mathbb{C}_M} \sum_{x} \mathsf{Z}(x, \pi(\hat{w}) \mid [\pi(w),s],[y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \\ &= \frac{1}{M}\sum_{\pi\in \mathbb{C}_M} \mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }(\pi(\hat{w})\mid [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \\ &= \frac{1}{M} \label{eq:csittp951} \end{align}\tag{5}\] which is a constant, so it does not depend on \((w,s)\), and \[\begin{align} &\sum_{\hat{w}} \mathsf{Z}'(x,\hat{w}\mid [w,s], [y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \notag \\ & = \frac{1}{M}\sum_{\pi\in \mathbb{C}_M} \sum_{\hat{w}} \mathsf{Z}(x, \pi(\hat{w}) \mid [\pi(w),s],[y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \\ & = \frac{1}{M}\sum_{\pi\in \mathbb{C}_M} \sum_{\hat{w}} \mathsf{Z}(x, \hat{w} \mid [\pi(w),s],[y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]) \\ & = \frac{1}{M}\sum_{\pi\in \mathbb{C}_M} \mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} }(x\mid [\pi(w),s]) \label{eq:csittp952} \end{align}\tag{6}\] which does not depend on \((y,s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} })\) (and also not on \(w\) because of the summation over \(\pi\)). This proves that \(\mathsf{Z}'\) is non-signaling. Finally, let us note that 5 implies \[\begin{align} &\sum_{x}\mathsf{Z}''(x,\hat{w}\mid [w,s], y) \notag \\ &= \sum_{x}\mathsf{Z}'(x,\hat{w} \mid [w,s],[y,s]) \\ &= \frac{1}{M} \end{align}\] which does not depend on \((w,s)\) and that 6 implies \[\begin{align} &\sum_{\hat{w}}\mathsf{Z}''(x,\hat{w}\mid [w,s], y) \notag \\ &= \sum_{\hat{w}}\mathsf{Z}'(x,\hat{w}\mid [w,s], [y,s]) \\ &= \frac{1}{M}\sum_{\pi\in \mathbb{C}_M} \mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} }(x\mid [\pi(w),s]) \end{align}\] which does not depend on \(y\) (and \(w\)). This completes the proof that \(\mathsf{Z}'\) and \(\mathsf{Z}''\) are non-signaling. It follows that given \(\mathsf{Z}\), there exists a non-signaling \(\mathsf{Z}''\) which needs no input \(S_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\) but still achieves the same probability of success, as desired. 0◻

8 Proof of Theorem 2↩︎

We shall show that \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N}) = \max_{\mathsf{P}_{X\mid S}}I(X;Y\mid S)\), for a channel with state, \(\mathsf{N}=(\mathsf{N}_{Y\mid XS}, \mathsf{P}_S)\). The direction \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N}) \geq \max_{\mathsf{P}_{X\mid S}}I(X;Y\mid S)\) is a direct implication of Theorem 1, that \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N})=C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\bar{\mathsf{N}})\), and since classical coding schemes are contained in NS assisted coding schemes, we have \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\bar{\mathsf{N}}) \geq C^{\mathchoice {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} {\mathrm{\scriptscriptstyle C}} }(\bar{\mathsf{N}}) = \max_{\mathsf{P}_{X\mid S}}I(X;Y\mid S)\).

To show the converse, that \(C^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathsf{N}) \leq \max_{\mathsf{P}_{X\mid S}}I(X;Y\mid S)\), we use a similar argument to [8] to first show the following lemma.

The proof is given in Appendix 10. Applying Lemma 1 to \(\mathsf{Z}_n \in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_n,N^{\otimes n})\), we have that \[\begin{align} I(X^n;Y^n\mid S^n) \geq \eta(\mathsf{Z}_n)\log_2(M_n) - H_b(\eta(\mathsf{Z}_n)). \end{align}\] Then for any \(R\) that is achievable by NS assistance, \[\begin{align} R\leq \lim_{n\to \infty} \frac{1}{n}\log_2 (M_n) \leq \lim_{n\to \infty} \frac{1}{n}I(X^n;Y^n\mid S^n) \end{align}\] because \(\lim_{n\to \infty} \eta(\mathsf{Z}_n) = 1\). The last step is to observe that \[\begin{align} \label{eq:single95letter95cws} \frac{1}{n}I(X^n;Y^n\mid S^n) \leq \max_{\mathsf{P}_{X\mid S}} I(X;Y\mid S). \end{align}\tag{7}\] Indeed, if 7 could be violated, then classical random coding over multiple blocks of \(N^{\otimes \ell}\) for some \(\ell >1\) would have exceeded the capacity of the channel with state when CSIT and CSIR are both available. This completes the proof of the converse. 0◻

9 Proof of Theorem 3↩︎

Given a 2-user broadcast channel \(\mathsf{N}\), recall that \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N})\) is the capacity region with bipartite NS assistance between the transmitter and User 1, and \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})\) is the capacity region when, additionally, User 1 is given \(W_2\). Let us first show that \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N}) = \mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(\mathsf{N})\). This is done by showing a stronger result, that \[\begin{align} \label{eq:SI95equals95woSI} \max_{\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(M_1,M_2,\mathsf{N})} \eta(\mathsf{Z}) = \max_{\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(M_1,M_2,\mathsf{N})} \eta(\mathsf{Z}). \end{align}\tag{8}\] This is saying that the joint probability of success cannot be improved even if \(W_2\) is made available freely at User \(1\), provided that NS assistance is available between the transmitter and User \(1\). This is argued as follows. For \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} ,\mathchoice {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} {\mathrm{\scriptscriptstyle SI\text{-}1}} }(M_1,M_2,\mathsf{N})\), note that \(\mathsf{Z}=\mathsf{Z}_1\times \mathsf{D}_2\). Construct \(\mathsf{Z}_1',\mathsf{Z}_1''\) as \[\begin{align} & \mathsf{Z}_1'(x,\hat{w}_1\mid [w_1,w_2], [y_1,w_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }])= \frac{1}{M_1}\sum_{\pi \in \mathbb{C}_{M_1}}\mathsf{Z}_1(x,\pi(\hat{w}_1) \mid [\pi(w_1),w_2],[y_1,w_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }]), \\ & \mathsf{Z}_1''(x,\hat{w}_1\mid [w_1,w_2],y_1) = \mathsf{Z}_1'(x,\hat{w}_1\mid [w_1,w_2],[y_1,w_2]). \end{align}\] Following the same argument as in Appendix 7 by replacing \(\hat{w}_1 \to \hat{w}, w_1\to w, w_2\to s, w_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\to s_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\), it can be shown that \(\mathsf{Z}_1'\) and \(\mathsf{Z}_1''\) are non-signaling. One can then similarly verify that \(\eta(\mathsf{Z}) = \eta(\mathsf{Z}_1\times \mathsf{D})=\eta(\mathsf{Z}_1'\times \mathsf{D}) = \eta(\mathsf{Z}_1''\times \mathsf{D})\), essentially because relabeling the message \(W_1\) does not affect the (joint) probability of success, as \(W_1\) is uniformly distributed. The desired claim 8 then follows as \(\mathsf{Z}_1''\times \mathsf{D}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(M_1,M_2,\mathsf{N})\).

It remains to show that \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }(\mathsf{N}) \subseteq \mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }(\mathsf{N})\). We need the following lemma.

The proof of Lemma 2 is left to Appendix 10. One may view this lemma as an application of Lemma 1 by replacing \((W_1,W_2,Y_1)\) with \((W,S,Y)\).

The rest of the proof is to apply Lemma 2, Fano’s inequality, and the same single-letterization steps as in [27], [26] by identifying the relevant auxiliary random variables.

Applying Lemma 2 to \(\mathsf{Z}_n \in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_{1,n}, M_{2,n}, \mathsf{N}^{\otimes n})\), we have \[\begin{align} I(X^n;Y_1^n\mid W_2) \geq \eta_1(\mathsf{Z}_n) \log_2(M_{1,n}) - H_b(\eta_1(\mathsf{Z}_n)). \end{align}\] Then for any \((R_1,R_2)\) that is achievable by fully NS assisted coding schemes, \[\begin{align} R_1 \leq \lim_{n\to \infty} \frac{1}{n} \log_2(M_{1,n}) \leq \lim_{n\to \infty} \frac{1}{n} I(X^n;Y_1^n\mid W_2), \end{align}\] since \(\lim_{n\to \infty} \eta_1(n) = 1\). We alternatively write it as \[\begin{align} \label{eq:NSfano95R1} nR_1 \leq I(X^n;Y_1^n\mid W_2) + o(n). \end{align}\tag{9}\] 9 also holds for \((R_1,R_2)\in \mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} }\), since \(\mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} } \subseteq \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }\).

Meanwhile, since there is no NS assistance to User \(2\), \(W_2\leftrightarrow Y_2^n \leftrightarrow \hat{W}_2\) form a Markov chain. By the data processing inequality and Fano’s inequality, \[\begin{align} \label{eq:fano95R2} n R_2\leq I(W_2;Y_2^n) + o(n). \end{align}\tag{10}\]

It is useful to have the joint distribution of \((W_1,W_2,X^n,Y_1^n, Y_2^n)\) written explicitly as, \[\begin{align} &\Pr(W_1=w_1,W_2=w_2,X^n=x^n,Y_1^n=y_1^n,Y_2^n = y_2^n)\notag \\ &=\frac{1}{M_1M_2}\mathsf{Z}_{X^n\mid W_1W_2}(x^n\mid w_1,w_2)\times \prod_{i=1}^n \mathsf{N}(y_{1,i},y_{2,i}\mid x_i) \end{align}\] where \(\mathsf{Z}_{X^n\mid W_1W_2}\) is the marginal distribution of \(\mathsf{Z}_n\) for the transmitter.

Now, define \(U_i \triangleq (W_2,Y_1^{i-1}, Y_{2,i+1}^n)\). Note that \(U_i \leftrightarrow X_i \leftrightarrow (Y_{1,i},Y_{2,i})\) form a Markov chain for \(i\in [n]\). We have \[\begin{align} &I(X^n;Y_1^n\mid W_2) \notag \\ &= \sum_{i=1}^n I(X^n;Y_{1,i}\mid W_2, Y_1^{i-1})\\ &\leq \sum_{i=1}^n I(X^n,Y_{2,i+1}^n;Y_{1,i}\mid W_2, Y_1^{i-1})\\ &= \sum_{i=1}^n I(Y_{2,i+1}^n;Y_{1,i}\mid W_2, Y_1^{i-1}) + \sum_{i=1}^n I(X^n;Y_{1,i} \mid \underbrace{W_2, Y_1^{i-1}, Y_{2,i+1}^n}_{= U_i}) \end{align}\] and \[\begin{align} &I(W_2;Y_2^n)\notag \\ &=\sum_{i=1}^n I(W_2;Y_{2,i} \mid Y_{2,i+1}^n) \\ &=\sum_{i=1}^n I(W_2, Y_1^{i-1};Y_{2,i} \mid Y_{2,i+1}^n) - \sum_{i=1}^n I(Y_1^{i-1};Y_{2,i} \mid W_2, Y_{2,i+1}^n) \\ &\leq \sum_{i=1}^n I(\underbrace{W_2, Y_1^{i-1},Y_{2,i+1}^n}_{= U_i};Y_{2,i}) - \sum_{i=1}^n I(Y_1^{i-1};Y_{2,i} \mid W_2, Y_{2,i+1}^n) \end{align}\] Therefore, \[\begin{align} &I(X^n;Y_1^n\mid W_2) + I(W_2;Y_2^n) \notag \\ &\leq \sum_{i=1}^n I(X_i;Y_{1,i} \mid U_i) + \sum_{i=1}^n I(U_i;Y_{2,i}) \tag{11} \\ &= n\big( I(X_T;Y_{1,T}\mid U_T,T) + I(U_T;Y_{2,T}\mid T) \big)\tag{12}\\ &\leq n\big( I(X_T;Y_{1,T}\mid U_T,T) + I(U_T,T;Y_{2,T})\big) \end{align}\] Step 11 is because \(\sum_{i=1}^n I(Y_{2,i+1}^n;Y_{1,i}\mid W_2, Y_1^{i-1})=\sum_{i=1}^n I(Y_1^{i-1};Y_{2,i} \mid W_2, Y_{2,i+1}^n)\) by the Korner-Marton identity (Csiszár sum identity), and \(X^n \leftrightarrow (U_i,X_i) \leftrightarrow Y_{1,i}\). In 12 we define a time sharing variable \(T\) that is uniformly distributed over \([n]\) and is independent of \(W_1W_2X^nY_1^nY_2^n\). Note that \((U_T,T)\leftrightarrow X_T \leftrightarrow (Y_{1,T}, Y_{2,T})\).

On the other hand, from 10 we have \[\begin{align} &nR_2 -o(n) \notag \\ &\leq I(W_2;Y_2^n) \\ &= \sum_{i=1}^n I(W_2;Y_{2,i}\mid Y_{2,i+1}^n) \\ &\leq \sum_{i=1}^n I(U_i;Y_{2,i})\\ &\leq n\sum_{i=1}^n I(U_T,T;Y_{2,T}) \end{align}\] Also, from 9 we have \[\begin{align} &nR_1 - o(n) \notag \\ &\leq I(X^n;Y_1^n\mid W_2)\\ &\leq I(X^n;Y_1^n) \tag{13} \\ &\leq \sum_{i=1}^n I(X_i;Y_{1,i}) \tag{14} \\ &\leq n I(X_T;Y_{1,T}) \end{align}\] where Step 13 is because \(W_2\leftrightarrow X^n\leftrightarrow Y_1^n\), and Step 14 is because \((X^n, Y_1^{i-1}) \leftrightarrow X_i \leftrightarrow Y_{1,i}\). By viewing \(X_T\) as \(X\), \(Y_{1,T}\) as \(Y_1\), \(Y_{2,T}\) as \(Y_2\), \((U_T,T)\) as \(U\), we are able to show that any \((R_1,R_2)\) achievable with bipartite NS assistance between the transmitter and User 1 must satisfy \[\begin{align} R_1 \leq I(X;Y_1), ~~R_2 \leq I(U;Y_2), ~~R_1+R_2 \leq I(X;Y_1\mid U)+I(U;Y_2) \end{align}\] for some \(\mathsf{P}_{XU}\) such that \(U\leftrightarrow X \leftrightarrow (Y_1,Y_2)\). This proves that \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} {\mathrm{\scriptscriptstyle NS\text{-}1}} } \subseteq \mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} {\mathrm{\scriptscriptstyle KS}} }\).0◻

10 Proofs of Lemma 1 and Lemma 2↩︎

We first prove Lemma 1. The proof is essentially the derivation of [7] (also see [8]), by conditioning on each \(S=s\) for \(s\in \mathcal{S}\). The key of the proof is identifying that \(\mathsf{Z}\) has probability of success equal to \(1/M\) if the channel is broken, conditioned on each \(S=s\) for \(s\in \mathcal{S}\). This observation is also useful for the generalization to broadcast channels, i.e., Lemma 2. The rest of the proof then follows from an application of the data processing inequality.

Let \(\eta(\mathsf{Z}\mid s) \triangleq \Pr(W=\hat{W}\mid S=s) = \frac{1}{M}\sum_{w,x,y} \mathsf{N}_{Y\mid XS}(y\mid x,s)\mathsf{Z}(x,w \mid [w,s],y)\) be the probability of success conditioned on \(S=s\), for \(s\in \mathcal{S}\). Let \[\begin{align} T_{x,y}^s \triangleq \Pr(W=\hat{W}\mid X=x,Y=y,S=s) \end{align}\] for \(s\in \mathcal{S}, x\in \mathcal{X}, y\in \mathcal{Y}\). By the law of total probability, \[\begin{align} \label{eq:prob95success95closed} \eta (\mathsf{Z}\mid s) = \sum_{x,y} \Pr(X=x,Y=y\mid S=s) \times T_{x,y}^s. \end{align}\tag{15}\] We point out that \(T_{x,y}^s\) does not depend on \(\mathsf{N}_{Y|XS}\). Indeed, \(T_{x,y}^{s}\) is calculated as, \[\begin{align} &T_{x,y}^s = \frac{\Pr(W=\hat{W}, X=x,Y=y\mid S=s)}{\Pr(X=x,Y=y\mid S=s)}\\ &= \frac{\frac{1}{M}\sum_{w}\mathsf{Z}(x,w \mid [w,s],y)N_{Y\mid XS}(y\mid x,s)}{\frac{1}{M}\sum_{w,\hat{w}}\mathsf{Z}(x,\hat{w} \mid [w,s],y)N_{Y\mid XS}(y\mid x,s)}\\ &=\frac{\sum_{w}\mathsf{Z}(x,w \mid [w,s],y)}{\sum_{w,\hat{w}}\mathsf{Z}(x,\hat{w} \mid [w,s],y)} \end{align}\] which does not depend on \(\mathsf{N}_{Y\mid XS}\).

On the other hand, we argue that \[\begin{align} \label{eq:prob95success95broken} \sum_{x,y} \Pr(X=x\mid S=s) \times \Pr(Y=y\mid S=s) \times T_{x,y}^s = \frac{1}{M}. \end{align}\tag{16}\] This is because 16 is equal to the probability of success of \(\mathsf{Z}\) if we replace \(\mathsf{N}_{Y\mid XS}\) with \(\mathsf{P}_{Y\mid S}\), i.e., break the channel, which makes \(X\) and \(Y\) independent conditioned on \(S=s\), and then the probability of success must be equal to \(1/M\) due to the fact that \(\mathsf{Z}\) is non-signaling. Indeed, conditioned on \(S=s\), if we calculate the probability of success for \(\mathsf{Z}\) when the channel is broken, it equals \[\begin{align} &\frac{1}{M}\sum_{w,x,y}\mathsf{Z}(x,w\mid [w,s], y) \mathsf{P}_{Y\mid S}(y\mid s) \\ &=\frac{1}{M} \sum_{w,y} \mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }(w\mid y) \mathsf{P}_{Y\mid S}(y\mid s)\\ &= \frac{1}{M} \end{align}\] where we define \(\sum_x \mathsf{Z}(x,w \mid [w,s],y)\triangleq \mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }(w\mid y)\) as \(\mathsf{Z}\) is non-signaling.

Now for \(s\in \mathcal{S}\), define a channel \(\mathsf{B}_s \in \mathcal{P}(\{0,1\}\mid \mathcal{X}\times \mathcal{Y})\) such that \(\mathsf{B}_s(1\mid x,y)=T_{x,y}^s, \mathsf{B}_s(0\mid x,y)=1-T_{x,y}^s\), for \((x,y) \in \mathcal{X}\times \mathcal{Y}\). In words, given that the input to the channel \(\mathsf{B}_s\) is \((x,y)\), the channel outputs \(1\) with probability \(T_{x,y}^s\) and outputs \(0\) with probability \(1-T_{x,y}^s\). Let \(\mathsf{B}(\mathsf{P})\in \mathcal{P}(\{0,1\})\) denote the output distribution of channel \(\mathsf{B}\) with respect to input distribution \(\mathsf{P}\). Let \(\mathsf{P}_s, \mathsf{Q}_s \in \mathcal{P}(\mathcal{X}\times\mathcal{Y})\) such that \(\mathsf{P}_s(x,y) \triangleq \Pr(X=x,Y=y\mid S=s)\) and \(\mathsf{Q}_s(x,y) \triangleq \Pr(X=x\mid S=s)\times \Pr(Y=y\mid S=s)\). Then 15 implies that \(\mathsf{B}(\mathsf{P}_s) = [1-\eta(\mathsf{Z}\mid s), \eta(\mathsf{Z}\mid s)]\) and 16 implies that \(\mathsf{B}(\mathsf{Q}_s) = [1-\frac{1}{M}, \frac{1}{M}]\). It follows from the data processing inequality that \[\begin{align} I(X;Y\mid S=s) = D_{\mathrm{KL}}(\mathsf{P}_s\Vert \mathsf{Q}_s) \geq D_{\mathrm{KL}}(\mathsf{B}(\mathsf{P}_s) \Vert \mathsf{B}(\mathsf{Q}_s)) \geq \eta(\mathsf{Z}\mid s) \log_2(M) - H_b(\eta(\mathsf{Z}\mid s)), \end{align}\] where \(D_{\mathrm{KL}}(\cdot \Vert \cdot)\) is the KL divergence and \(H_b(\cdot)\) is the binary entropy function. Taking the convex combination of both sides, we obtain \[\begin{align} &I(X;Y\mid S) = \sum_{s} \mathsf{P}_S(s) I(X;Y\mid S=s)\\ &\geq \log_2 (M) \times \sum_{s} \mathsf{P}_S(s) \eta(\mathsf{Z}\mid s) -\sum_{s} \mathsf{P}_S(s) H_b(\eta(\mathsf{Z}\mid s))\\ &= \eta(\mathsf{Z}) \log_2 (M) - \sum_{s} \mathsf{P}_S(s) H_b(\eta(\mathsf{Z}\mid s))\\ &\geq \eta(\mathsf{Z}) \log_2 (M) - H_b(\eta(\mathsf{Z})) \end{align}\] where the last step is because \(H_b\) is concave. 0◻

To prove Lemma 2, we apply the same argument that was used to prove Lemma 1. We first show that, given a 2-user broadcast channel \(\mathsf{N}\) and a coding scheme \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_1,M_2,\mathsf{N})\), if the channel \(\mathsf{N}\) is replaced with the broken channel, \(\mathsf{P}_{Y_1Y_2}\), defined such that \(\mathsf{P}_{Y_1Y_2}(y_1,y_2)=\Pr(Y_1=y_1,Y_2=y_2)\), then conditioned on \(W_2=w_2\), the probability of success for Message \(1\) must equal \(1/M_1\), for every \(w_2\in [M_2]\). This is explicitly calculated as follows. \[\begin{align} &\frac{1}{M_1} \sum_{w_1,\hat{w}_2,x,y_1,y_2} \mathsf{Z}(x,w_1,\hat{w}_2\mid [w_1,w_2],y_1,y_2)\times \mathsf{P}_{Y_1Y_2}(y_1,y_2)\\ &=\frac{1}{M_1} \sum_{w_1,\hat{w}_2,y_1,y_2} \mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} _\mathrm{\scriptscriptstyle 1}\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} _\mathrm{\scriptscriptstyle 2}}(w_1,\hat{w}_2\mid y_1,y_2)\times \mathsf{P}_{Y_1Y_2}(y_1,y_2)\\ &=\frac{1}{M_1} \end{align}\] where \(\mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} _\mathrm{\scriptscriptstyle 1}\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} _\mathrm{\scriptscriptstyle 2}}\) is the marginal distribution of \(\mathsf{Z}\) for User \(1\) and User \(2\). Then by viewing \(W_2\) as \(S\), \(Y_1\) as \(Y\), we conclude that \(I(X;Y_1\mid W_2) \geq \eta_1(\mathsf{Z})\log_2(M_1) - H_b(\eta_1(\mathsf{Z}))\) as in the proof of Lemma 1. 0◻

11 Proof of Theorem 4↩︎

The proof is simply a combination of the converse argument for the NS assisted capacity of a point-to-point channel (without states) and the same-marginals property of NS assisted coding schemes for general broadcast channels (see [4]).

First let us recall the converse for the NS assisted capacity of a point-to-point channel (without states). This can be deduced from a special case of Lemma 1 by making \(|\mathcal{S}|=1\) (i.e., no channel state \(S\)), and applying it to \(n\)-th extension of a point-to-point channel \(\mathsf{N}_{Y\mid X}^{\otimes n}\). We obtain \(I(X^n;Y^n) \geq \eta(\mathsf{Z}_n) \log_2(M_n) - H_b(\eta(\mathsf{Z}_n))\), for \(\mathsf{Z}_n\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_n,N_{Y\mid X}^{\otimes n})\), and therefore \(nR\leq I(X^n;Y^n)+o(n)\) if \(R\) is achievable by NS assistance over the channel \(\mathsf{N}_{Y\mid X}\).

Now consider the broadcast channel. Given \(\mathsf{N}_{Y_1Y_2\mid X} \in \mathcal{P}(\mathcal{Y}_1 \times \mathcal{Y}_2 \mid \mathcal{X})\), let \(\mathsf{N}_{Y_1\mid X}\) and \(\mathsf{N}_{Y_2\mid X}\) be the marginal distributions of \(\mathsf{N}_{Y_1Y_2\mid X}\) for User \(1\) and User \(2\), respectively. Let \(\mathcal{N}'(\mathsf{N}_{Y_1Y_2\mid X})\) be the subset of channels that has the same marginals as \(\mathsf{N}_{Y_1Y_2\mid X}\), i.e., \(\mathsf{N}'_{Y_1'Y_2'}\in \mathcal{N}'(\mathsf{N}_{Y_1Y_2\mid X})\) iff \(\sum_{y_i}\mathsf{N}'_{Y_1'Y_2'}(y_1,y_2\mid x) = \sum_{y_i}\mathsf{N}_{Y_1Y_2\mid X}(y_1,y_2\mid x)\), for all \(x\in \mathcal{X}, y_j\in\mathcal{Y}_j\), \(\{i,j\}=\{1,2\}\).

Now say we are given a sequence of fully NS assisted coding schemes \(\mathsf{Z}_n \in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_{1,n},M_{2,n},\) \(\mathsf{N}_{Y_1Y_2\mid X}^{\otimes n})\). Denote \(\mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} \mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} _\mathrm{\scriptscriptstyle 1},n}\) as the marginal distribution of \(\mathsf{Z}_n\) for the transmitter and User 1. It is not difficult to see that \(\mathsf{Z}_{\mathchoice {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} {\mathrm{\scriptscriptstyle T}} \mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} _\mathrm{\scriptscriptstyle 1},n} \in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(M_{1,n},\mathsf{N}_{Y_1\mid X}^{\otimes n})\) and therefore it is a valid NS assisted coding scheme over the sub-channel from the transmitter to User \(1\). If \((R_1,R_2)\) is achievable by NS assisted coding schemes, it follows that \(nR_1\leq I(X^n;Y_1^n) + o(n)\). By symmetry, we obtain that \(nR_2\leq I(X^n;Y_2^n) + o(n)\).

Similarly, if we treat User \(1\) and User \(2\) as one receiver by grouping their message \(W_1,W_2\) as one message \(W\), and letting \(Y_1,Y_2\) to be processed together, then the argument also implies \(n(R_1+R_2) \leq I(X^n;Y_1^n,Y_2^n)+o(n)\). Now according to [4], \(\mathsf{Z}_n\) achieves the same (individual) probability of success on any channel \({\mathsf{N}'}_{Y_1'Y_2'\mid X}^{\otimes n}\) as long as \(\mathsf{N}'_{Y_1'Y_2'\mid X}\in \mathcal{N}'(\mathsf{N}_{Y_1Y_2\mid X})\). It follows that, for \(k\in \{1,2\}\), \[\begin{align} &nR_k-o(n) \notag \\ &\leq I(X^n;{Y_k'}^n) \\ &= I(X^n;Y_k^n)\\ & = \sum_{i=1}^n I(X^n; Y_{k,i} \mid Y_k^{i-1}) \\ &\stackrel{(a)}{\leq} \sum_{i=1}^n I(X_i;Y_{k,i})\\ &=nI(X_T;Y_{k,T}\mid T)\\ &\stackrel{(b)}{\leq} nI(X_T;Y_{k,T}) \end{align}\] and \[\begin{align} &n(R_1+R_2)-o(n) \notag \\ &\leq \min_{\mathsf{N}'_{Y_1'Y_2'\mid X}}I(X^n; {Y_1'}^n,{Y_2'}^n)\\ &= \min_{\mathsf{N}'_{Y_1'Y_2'\mid X}} \sum_{i=1}^nI(X^n; Y_{1,i}' , Y_{2,i}' \mid {Y_1'}^{i-1},{Y_2'}^{i-1})\\ &\stackrel{(a)}{\leq} \min_{\mathsf{N}'_{Y_1'Y_2'\mid X}}\sum_{i=1}^n I(X_i; Y'_{1,i}, Y'_{2,i})\\ &=n \times \min_{\mathsf{N}'_{Y_1'Y_2'\mid X}} I(X_T; Y'_{1,T}, Y'_{2,T}\mid T) \\ &\stackrel{(b)}{\leq} n \times \min_{\mathsf{N}'_{Y_1'Y_2'\mid X}}I(X_T; Y'_{1,T}, Y'_{2,T}) \end{align}\] where \(T\) is uniformly distributed over \([n]\) and is independent of \(W_1W_2X^n{Y_1'}^n{Y_2'}^n\). Steps labeled by \((a)\) follow from the Markov chain \((X^n,{Y'_1}^{i-1},{Y'_2}^{i-1}) \leftrightarrow X_i\leftrightarrow (Y_{1,i}',Y_{2,i}')\), and steps labeled by \((b)\) follow from the Markov chain \(T\leftrightarrow X_T \leftrightarrow (Y'_{1,T},Y'_{2,T})\). We have also used the fact that if \(X\leftrightarrow Y \leftrightarrow Z\) then \(I(Y;Z\mid X)\leq I(Y;Z)\). Thus, we obtain \((R_1,R_2) \in \mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} }(\mathsf{N}_{Y_1Y_2\mid X})\), by identifying \(X= X_T, Y_1=Y_{1,T}, Y_2=Y_{2,T}, Y_1'=Y_{1,T}', Y_2'=Y_{2,T}'\). 0◻

12 Proof of Corollary 2↩︎

The following lemma will be useful.

According to Theorem 3, with \(U = f(X)=Y_2\), it follows that any \((R_1,R_2)\) is achievable by full NS assistance if \[\begin{align} R_1 &\leq I(X;\tilde{Y}_1) \\ &\stackrel{(a)}{=} (1-\gamma_1) I(X;Y_1) \end{align}\] \[\begin{align} R_2 &\leq I(Y_2;\tilde{Y}_2) \\ &= I(X;\tilde{Y}_2) \\ &\stackrel{(a)}{=} (1-\gamma_2) I(X;Y_2) \\ &= (1-\gamma_2) H(Y_2) \end{align}\] and \[\begin{align} &R_1+R_2 \notag \\ &\leq I(X;\tilde{Y}_1\mid Y_2) + I(Y_2;\tilde{Y}_2)\\ &=I(X;\tilde{Y}_1\mid Y_2) + I(X;\tilde{Y}_2)\\ &= \sum_{y_2\in \mathcal{Y}_2}\Pr(Y_2=y_2) \times I(X;\tilde{Y}_1\mid Y_2=y_2) + I(X;\tilde{Y}_2) \\ &\stackrel{(a)}{=} (1-\gamma_1) I(X;Y_1\mid Y_2) + (1-\gamma_2) I(X;Y_2)\\ &= (1-\gamma_1) I(X;Y_1\mid Y_2) + (1-\gamma_2) H(Y_2) \end{align}\] for some \(P_X\in \mathcal{P}(\mathcal{X})\). Steps labeled by \((a)\) follow from Lemma 3. This provides an inner bound on \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }\big(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{\tilde{Y}_1\tilde{Y}_2\mid X}\big)\).

On the other hand, the sub-channel to User 1, \(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{Y_1\mid X}\) can be equivalently viewed as \(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} {\mathrm{\scriptscriptstyle SD}} }_{Y_1\mid X}\) followed by a sequence of two erasure channels, with erasure probabilities \(\gamma'\) and \(\gamma_2\) such that \(1-\gamma_1= (1-\gamma')(1-\gamma_2)\) (recall that we need \(0\leq \gamma_2 \leq \gamma_1 \leq 1)\). Denote \(\tilde{Y}_1'\) as the output of the first erasure channel (the one associated with \(\gamma'\)). Note that in computing \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} }\big(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{\tilde{Y}_1\tilde{Y}_2\mid X}\big)\), we are free to choose the joint distribution subject to the same-marginals conditions, and any choice provides a valid outer bound on \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }\big(\mathsf{N}^{\mathchoice {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} {\mathrm{\scriptscriptstyle SDE}} }_{\tilde{Y}_1\tilde{Y}_2\mid X}\big)\). Let us choose the joint distributions such that the erasure at User \(2\) happens simultaneously with the second erasure at User \(1\) (both erasure channels are associated with \(\gamma_2\)), so that \([\tilde{Y}_1', Y_2]\) undergoes a block erasure channel with erasure probability \(\gamma_2\). The outer bound then implies that any achievable \((R_1,R_2)\) must satisfy \[\begin{align} R_1 &\leq I(X;\tilde{Y}_1) \\ &\stackrel{(a)}{=} (1-\gamma_1) I(X;Y_1) \end{align}\] \[\begin{align} R_2 &\leq I(X;\tilde{Y}_2) \\ &\stackrel{(a)}{=} (1-\gamma_2) I(X;Y_2) \\ &= (1-\gamma_2) H(Y_2) \end{align}\] and \[\begin{align} &R_1+R_2 \notag \\ &\stackrel{(a)}{\leq} (1-\gamma_2) I(X;\tilde{Y}_1',Y_2)\\ &=(1-\gamma_2) I(X;Y_2) + (1-\gamma_2) I(X;\tilde{Y}_1'\mid Y_2)\\ &=(1-\gamma_2) H(Y_2) + (1-\gamma_2) \sum_{y_2\in \mathcal{Y}_2}\Pr(Y_2=y_2)\times I(X;\tilde{Y}_1'\mid Y_2=y_2)\\ &\stackrel{(a)}{=} (1-\gamma_2) H(Y_2) + (1-\gamma_2)(1-\gamma') I(X;Y_1\mid Y_2)\\ &= (1-\gamma_1) I(X;Y_1\mid Y_2) + (1-\gamma_2) H(Y_2) \end{align}\] for some \(\mathsf{P}_X\in \mathcal{P}(\mathcal{X})\). Steps labeled by \((a)\) follow from Lemma 3. Note that the outer bound matches the inner bound, which completes the proof. 0◻

13 Proof of Corollary 3↩︎

To apply Sato’s outer bound (Theorem 4) for the channel \({\sf N}_{Y_1Y_2\mid X}\), let us first note that it suffices to consider \(\mathsf{P}_{X'X''} = \mathsf{P}_{X'}\times \mathsf{P}_{X''}\) for which \(X'\) and \(X''\) are independent, due to the fact that the product distribution maximizes the mutual information over a product channel (cf. [38]). It follows that \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }\big({\sf N}_{Y_1Y_2\mid X}\big)\) is contained in the set of \((R_1,R_2)\) such that \[\begin{align} R_1 &\leq I(X';Y_1') + H(Y_1''), \tag{17} \\ R_2 &\leq H(Y_2') + I(X'';Y_2''), \\ R_1+R_2 &\leq I(X';Y_1'\mid Y_2') + H(Y_2') + H(Y_1'')+ I(X'';Y_2''\mid Y_1'') \tag{18} \end{align}\] for some \(\mathsf{P}_{X'X''} = \mathsf{P}_{X'}\times \mathsf{P}_{X''}\), as \(Y_2' = f(X')\), \(Y_1''=g(X'')\).

In the following, we show that this region is achievable with full NS assistance by independently operating over \({\sf N}'_{Y_1'Y_2'\mid X'}\) and \({\sf N}''_{Y_1''Y_2''\mid X''}\). First, Theorem 3 shows that (by letting \(U = f(X')\)), \((R_1', R_2')\) is achievable with NS assistance for the BC \({\sf N}'_{Y_1'Y_2'\mid X'}\) if \[\begin{align} R_1' &\leq I(X';Y_1') \tag{19} \\ R_2' &\leq H(Y_2') \\ R_1'+R_2' &\leq I(X';Y_1'\mid Y_2') + H(Y_2') \tag{20} \end{align}\] for some \(\mathsf{P}_{X'}\). By switching the indices of the two users, Theorem 3 also shows that (by letting \(U = g(X'')\)), \((R_1'', R_2'')\) is achievable with NS assistance for the BC \({\sf N}''_{Y_1''Y_2''\mid X''}\) if \[\begin{align} R_1'' &\leq H(Y_1'') \tag{21}\\ R_2'' &\leq I(X'';Y_2'')\\ R_1''+R_2'' &\leq H(Y_1'') + I(X'';Y_2''\mid Y_1'') \tag{22} \end{align}\] for some \(\mathsf{P}_{X''}\). Then, let \(\mathcal{R}'(\mathsf{P}_{X'})\) denote the region of \((R_1', R_2')\) specified by 19 to 20 given \(\mathsf{P}_{X'}\), and let \(\mathcal{R}''(\mathsf{P}_{X''})\) denote the region of \((R_1'', R_2'')\) specified by 21 to 22 given \(\mathsf{P}_{X''}\). It follows that \((R_1, R_2)\) is achievable for the BC \({\sf N}_{Y_1Y_2\mid X}\) if \(R_1= R_1'+R_1''\), \(R_2=R_2'+R_2''\), \((R_1',R_2')\in \mathcal{R}'(\mathsf{P}_{X'})\), \((R_1'',R_2'')\in \mathcal{R}''(\mathsf{P}_{X''})\) for some \(\mathsf{P}_{X'}\) and \(\mathsf{P}_{X''}\). This can be thought of as splitting the message \(W_k\) into \((W'_k,W''_k)\) for \(k\in \{1,2\}\), sending \((W_1', W_2')\) through \({\sf N}'_{Y_1'Y_2'\mid X'}\), and sending \((W_1'', W_2'')\) through \({\sf N}''_{Y_1''Y_2''\mid X''}\). Note that given \(\mathsf{P}_{X'}\) and \(\mathsf{P}_{X''}\), the region of \((R_1,R_2)\) thus achieved is the Minkowski sum \(\mathcal{R}'(\mathsf{P}_{X'})+\mathcal{R}''(\mathsf{P}_{X''})\). Since \(\mathcal{R}'(\mathsf{P}_{X'})\) and \(\mathcal{R}''(\mathsf{P}_{X''})\) are polymatroids,⁶ their Minkowski sum is obtained as the set of \((R_1,R_2)\) such that \[\begin{align} R_1 &\leq I(X';Y_1')+H(Y_1')\\ R_2 &\leq H(Y_2')+ I(X'';Y_2'')\\ R_1+R_2 &\leq I(X';Y_1'\mid Y_2') + H(Y_2') + H(Y_1'') + I(X'';Y_2''\mid Y_1'') \end{align}\] which is again a polymatroid by adding the bounds individually (see e.g., [39]). Comparing with the bounds from 17 to 18 , we conclude that \(\mathcal{R}_{\mathchoice {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} {\mathrm{\scriptscriptstyle Sato}} }\big( {\sf N}_{Y_1Y_2\mid X} \big)\) is achievable (with full NS assistance), thus equal to the fully NS assisted capacity region \(\mathcal{C}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }\big( {\sf N}_{Y_1Y_2\mid X} \big)\). 0◻

14 Proof of Theorem 5↩︎

Without loss of generality, say \(k=1\). We shall show that, if \(W_1\) is not known by any users, then removing the side information of User \(1\) does not affect the optimal probability of success (assuming full NS assistance). Given an NS assisted coding scheme where the side information is available at all users, i.e., \(\mathsf{Z}\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=[K])\), let \[\begin{align} \mathsf{Z}' \in \mathcal{P}\Bigg(\mathcal{X} \times \prod_{k=1}^K\mathcal{M}_k ~\Bigg|~ \prod_{k=1}^K(\mathcal{M}_k\times \mathcal{Y}_k \times \mathcal{S}_k) \Bigg) \end{align}\] such that \[\begin{align} \mathsf{Z}'{ \left( \begin{matrix} x\\ \hat{w}_1 \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} w_1,w_2,\cdots, w_K \\ y_1,s_1^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)} \triangleq \frac{1}{M_1}\sum_{\pi \in \mathbb{C}_{M_1}}\mathsf{Z}{ \left( \begin{matrix} x\\ \pi(\hat{w}_1) \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} \pi(w_1),w_2,\cdots, w_K \\ y_1,s_1^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)} \end{align}\] for all \(x\in \mathcal{X}\), \(\hat{w}_k\in \mathcal{M}_k, w_k \in \mathcal{M}_k, y_k \in \mathcal{Y}_k, s_k^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \in \mathcal{S}_k, k\in [K]\), where \(\mathbb{C}_{M_1}\) is the cyclic permutation group operating on \([M_1]\). It is not difficult to verify that \(\mathsf{Z}'\in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=[K])\). We then show that \(\eta(\mathsf{Z}) = \eta(\mathsf{Z}')\), meaning that twirling \(W_1\) does not affect the probability of success. This is because \(W_1\) is uniformly distributed and no user has \(W_1\). Specifically, recall the concise notation \(s_k\triangleq (w_j)_{j\in \mathcal{W}_k}\). Then, \[\begin{align} \eta(\mathsf{Z}')&=\frac{1}{\prod_{k=1}^KM_k} \sum_{x, \mathbf{y}}\mathsf{N}(\mathbf{y}\mid x) \sum_{w_2,\cdots, w_K} \frac{1}{M_1}\sum_{w_1} \sum_{\pi\in \mathbb{C}_{M_1}}\mathsf{Z}{ \left( \begin{matrix} x \\ \pi(w_1) \\ w_2 \\ \vdots \\ w_K \end{matrix} \left| \begin{matrix} \pi(w_1),w_2,\cdots, w_K \\ y_1,s_1 \\ y_2,s_2 \\ \vdots \\ y_K,s_K \end{matrix} \right. \right)}\\ &=\frac{1}{\prod_{k=1}^KM_k} \sum_{x, \mathbf{y}}\mathsf{N}(\mathbf{y}\mid x) \sum_{w_2,\cdots, w_K} \sum_{w_1} \mathsf{Z}{ \left( \begin{matrix} x \\ w_1 \\ w_2 \\ \vdots \\ w_K \end{matrix} \left| \begin{matrix} w_1,w_2,\cdots, w_K \\ y_1,s_1 \\ y_2,s_2 \\ \vdots \\ y_K,s_K \end{matrix} \right. \right)}\\ &= \eta(\mathsf{Z}) \end{align}\]

Now let \[\begin{align} \mathsf{Z}'' \in \mathcal{P}\Bigg(\mathcal{X} \times \prod_{k=1}^K\mathcal{M}_k ~\Bigg|~ \prod_{k=1}^K(\mathcal{M}_k\times \mathcal{Y}_k) \times \prod_{j=2}^K \mathcal{S}_j \Bigg) \end{align}\] such that \[\begin{align} \label{eq:def95Zpp95extention} \mathsf{Z}''{ \left( \begin{matrix} x \\ \hat{w}_1 \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} w_1,w_2,\cdots, w_K \\ y_1\\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)} \triangleq \mathsf{Z}'{ \left( \begin{matrix} x \\ \hat{w}_1 \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} w_1,w_2,\cdots, w_K \\ y_1,s_1 \\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)} \end{align}\tag{23}\] for all \(x\in \mathcal{X}\), \(\hat{w}_k\in \mathcal{M}_k, w_k \in \mathcal{M}_k, y_k \in \mathcal{Y}_k, k\in [K], s_j^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \in \mathcal{S}_j, j\in \{2,3,\cdots, K\}\). We claim that \(\mathsf{Z}'' \in \mathcal{Z}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }(\mathrm{SI}=[K]\setminus \{1\})\), meaning that \(\mathsf{Z}''\) is also a valid NS assisted coding scheme, for which User \(1\) does not input its side information. To show it, we need to show that \(\mathsf{Z}''\) satisfies in total \(K+1\) conditions, each corresponding to tracing out the output of one of the \(K+1\) parties. It turns out that the non-trivial part corresponds to tracing out the first party (the transmitter), shown as follows.

\[\begin{align} &\sum_{x\in \mathcal{X}}\mathsf{Z}''{\left( \begin{matrix} x\\ \hat{w}_1 \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} w_1,w_2,\cdots, w_K\\ y_1 \\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)} \notag \\ &= \frac{1}{M_1} \sum_{\pi \in \mathbb{C}_{M_1}} \sum_{x\in \mathcal{X}}\mathsf{Z}{ \left( \begin{matrix} x\\ \pi(\hat{w}_1) \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} \pi(w_1),w_2,\cdots,w_K\\ y_1,s_1\\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)}\\ &= \frac{1}{M_1} \sum_{\pi \in \mathbb{C}_{M_1}} \mathsf{Z}_{\text{\tiny\mathrm{R_2...R_K}}} { \left( \begin{matrix} \pi(\hat{w}_1) \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} y_1,s_1\\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)} \tag{24}\\ &= \frac{1}{M_1} \sum_{\pi \in \mathbb{C}_{M_1}} \mathsf{Z}_{\text{\tiny\mathrm{R_2...R_K}}} { \left( \begin{matrix} \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} y_2, s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K, s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \tag{25} \right. \right)} \end{align}\] which does not depend on \((w_1,w_2,\cdots, w_K)\), for all \(\hat{w}_k\in \mathcal{M}_k, w_k \in \mathcal{M}_k, y_k \in \mathcal{Y}_k, k\in [K], s_j^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \in \mathcal{S}_j, j\in \{2,3,\cdots, K\}\). In Step 24 , \(\mathsf{Z}_{\text{\tiny\mathrm{R_1...R_K}}}\) is the marginal distribution of \(\mathsf{Z}\) for User \(1\) to User \(K\). In Step 25 , \(\mathsf{Z}_{\text{\tiny\mathrm{R_2...R_K}}}\) is the marginal distribution of \(\mathsf{Z}\) for User \(2\) to User \(K\), and note that \(\pi(\hat{w}_1)\) iterates over \([M_1]\) in the summation for every \(\hat{w}_1\).

Let us then verify the remaining \(K\) NS conditions. Tracing out the output of the second party (User \(1\)), we have

\[\begin{align} &\sum_{\hat{w}_1}\mathsf{Z}''{\left( \begin{matrix} x\\ \hat{w}_1 \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} w_1,w_2,\cdots, w_K\\ y_1 \\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)}\\ &= \frac{1}{M_1} \sum_{\pi \in \mathbb{C}_{M_1}} \sum_{\hat{w}_1}\mathsf{Z}{\left( \begin{matrix} x\\ \pi(\hat{w}_1) \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} \pi(w_1),w_2,\cdots, w_K\\ y_1,s_1\\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)}\\ &=\frac{1}{M_1} \sum_{\pi \in \mathbb{C}_{M_1}} \sum_{\hat{w}_1}\mathsf{Z}_{\text{\tiny\mathrm{TR_2...R_K}}} {\left( \begin{matrix} x \\ \hat{w}_2 \\ \vdots \\ \hat{w}_K \end{matrix} \left| \begin{matrix} \pi(w_1),w_2,\cdots, w_K\\ y_2,s_2^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} }\\ \vdots \\ y_K,s_K^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \end{matrix} \right. \right)} \label{eq:lemma95extension953} \end{align}\tag{26}\] which does not depend on \(y_1\), for all \(x\in \mathcal{X}, \hat{w}_j\in \mathcal{M}_j, w_k \in \mathcal{M}_k, y_k \in \mathcal{Y}_k, s_j^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} } \in \mathcal{S}_j, k\in [K], j\in \{2,3,\cdots, K\}\). In Step 26 , \(\mathsf{Z}_{\text{\tiny\mathrm{TR_2...R_K}}}\) is the marginal distribution of \(\mathsf{Z}\) for the transmitter together with User \(2\) to User \(K\). Similarly one can verify that tracing out \(\hat{w}_j\) of \(\mathsf{Z}''\) the distribution does not depend on \((y_j, s_j^{\mathchoice {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} {\mathrm{\scriptscriptstyle R}} })\), for \(j\in \{2,3,\cdots, K\}\).

Finally, by the definition of \(\mathsf{Z}''\) in 23 it follows that \(\eta(\mathsf{Z}'')=\eta(\mathsf{Z}')\) and thus equal to \(\eta(\mathsf{Z})\), which completes the proof of the theorem. 0◻

References↩︎

---

1. It is known that the set of NS resources, i.e., the set of correlations that do not violate the no-signaling principle, includes all quantum correlations, and the inclusion is strict.↩︎

2. Note that we are considering Shannon capacity (requiring vanishing error for large block lengths) of discrete memoryless channels. Larger improvements from NS assistance are indeed well-known in other settings, e.g., zero-error capacity [21], [22], arbitrarily varying channel capacity [23], and communication cost for computations such as binary decision problems [24]. Quek and Shor [16] demonstrated a factor of \(2\) improvement in a \(2\) user IC, but their notion of sum-rate ‘capacity’ which corresponds to maximizing single-letter mutual informations for the two users, \(\max I(X_1;Y_1)+I(X_2;Y_2)\), is different from Shannon capacity.↩︎

3. In fact [28], [29] have shown that it suffices to let \(\mathcal{U}=\{k\}\) for \(k\in [K]\).↩︎

4. According to the definition of \(\mathcal{P}^{\mathchoice {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} {\mathrm{\scriptscriptstyle NS}} }_2\), what this means explicitly is that \(\sum_{x\in \mathcal{X}}\mathsf{Z}(x,\hat{w}\mid w,s,y) = \sum_{x\in \mathcal{X}}\mathsf{Z}(x,\) \(\hat{w}\mid w',s',y)\) for all \(\hat{w} \in \mathcal{M}, y\in \mathcal{Y}, w\in \mathcal{M}, w'\in \mathcal{M}, s\in \mathcal{S}, s'\in \mathcal{S}\), and \(\sum_{\hat{w} \in \mathcal{M}}\mathsf{Z}(x,\hat{w}\mid w,s,y) = \sum_{\hat{w} \in \mathcal{X}}\mathsf{Z}(x,\hat{w}\mid w,s,y')\) for all \(x\in \mathcal{X}, w\in \mathcal{M}, s\in \mathcal{S}, y\in \mathcal{Y}, y'\in \mathcal{Y}\).↩︎

5. It is not difficult to see that if the probabilities of success could be improved by NS-assistance, then it would allow signaling between the two receivers who otherwise have no channel between them, thus violating the NS constraint.↩︎

6. It suffices to check that the bound for \(R_1'+R_2'\) is not greater than the sum, of the bound for \(R_1'\), and the bound for \(R_2'\), and similarly the bound for \(R_1''+R_2''\) is not greater than the sum, of the bound for \(R_1''\), and the bound for \(R_2''\).↩︎