Can Non-Signaling Assistance Increase the Degrees of Freedom of a Wireless Network?

Abstract

An open question recently posed by Fawzi and Ferme [IEEE Transactions on Information Theory 2024], asks whether non-signaling (NS) assistance can increase the capacity of a broadcast channel (BC). We answer this question in the affirmative, by showing that for a certainK-receiver BC model, called Coordinated Multipoint broadcast (CoMP BC) that arises naturally in wireless networks, NS-assistance provides multiplicative gains in both capacity and degrees of freedom (DoF), even achievingK-fold improvements in extremal cases. Somewhat surprisingly, this is shown to be true even for 2-receiver broadcast channels that are semi-deterministic and/or degraded. In a CoMP BC,Bsingle-antenna transmitters, supported by a backhaul that allows them to share data, act as oneB-antenna transmitter, to send independent messages toKreceivers, each equipped with a single receive antenna. A fixed and globally known connectivity matrix specifies for each transmit antenna, the subset of receivers that are connected to (have a non-zero channel coefficient to) that antenna. Besides the connectivity, there is no channel state information at the transmitter. The receivers have perfect channel knowledge. We show that NS-assistance has no DoF advantage in a fully connected CoMP BC. The DoF region is fully characterized for a class of connectivity patterns associated with tree graphs, for which the classical sum-DoF value is shown to be the number of leaf nodes, while the NS-assisted sum-DoF value is the total number of all (non-root) nodes. For arbitrary connectivity patterns, the sum-capacity with NS-assistance is bounded above and below by the min-rank and triangle number of the connectivity matrix, respectively, leading to matching bounds in many cases, e.g., if min(B,K) ≤ 6. While translations to Gaussian settings are demonstrated, for simplicity most of our results are presented under noise-free, finite-field (Fq) models. Converse proofs for classical DoF are found by adapting the Aligned Images bounds to the finite field model. Converse bounds for NS-assisted DoF/capacity extend the same-marginals property to the BC with NS-assistance available to all parties. Beyond the BC setting, even stronger (unbounded) gains in capacity due to NS-assistance are established for certain ‘communication with side-information’ settings, such as the fading dirty paper channel.