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

Abstract

An open question posed by Fawzi and Ferme [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 certain K-receiver BC setting, called Coordinated Multipoint (CoMP) that arises naturally in wireless networks, NS-assistance provides multiplicative gains in capacity and degrees of freedom (DoF), even achieving K-fold improvements in some 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, B single-antenna transmitters, supported by a backhaul that allows them to share data, act as one B-antenna transmitter, to send independent messages to K receivers, each equipped with a single receive antenna. A fixed and globally known connectivity matrix M, 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 DoF region is fully characterized for a class of connectivity patterns associated with tree graphs. Sum-capacity with NS-assistance for arbitrary connectivity patterns is bounded below and above by the triangle number and the min-rank of the connectivity matrix, respectively. While translations to Gaussian settings are demonstrated, most of our results are presented under noise-free, finite-field (Fq) models. Converse proofs for classical DoF adapt the Aligned Images bounds to the finite field model. Converse bounds for NS-assisted capacity extend the same-marginals property to the BC with NS-assistance available to all parties. Even stronger (unbounded) gains are established for certain 'communication with side-information' settings, such as the fading dirty paper channel.

References in corpus (22)

• Wireless Network Information Flow: A Deterministic Approach
• Non-local correlations as an information theoretic resource
• Entanglement-Assisted Classical Capacity of Noisy Quantum Channels
• Quantum Internet: Networking Challenges in Distributed Quantum Computing
• General properties of Nonsignaling Theories
• Topological Interference Management through Index Coding
• Improving zero-error classical communication with entanglement
• Closed sets of non-local correlations
• Constraints on nonlocality in networks from no-signaling and independence
• Zero-error channel capacity and simulation assisted by non-local correlations
• No-Signalling Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovasz Number
• Playing Games with Multiple Access Channels
• A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via non-signalling codes
• Entanglement-Enabled Communication
• Quantum and Super-quantum enhancements to two-sender, two-receiver channels
• Monotone Measures for Non-Local Correlations
• Algorithmic Aspects of Optimal Channel Coding
• Discrete Gaussian distributions via theta functions
• Multiple-Access Channel Coding with Non-Signaling Correlations
• Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
• On the separation of correlation-assisted sum capacities of multiple access channels
• One-time Pad Encryption Model for Non-local Correlations