Algorithmic Aspects of Optimal Channel Coding
arXiv:1508.04095 · doi:10.1109/TIT.2017.2696963
Abstract
A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1. There is a simple greedy polynomial-time algorithm that computes a code achieving a (1-1/e)-approximation of the maximum success probability. Moreover, for this problem it is NP-hard to obtain an approximation ratio strictly better than (1-1/e). 2. Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most 1/(1-1/e). In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3. We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdu.
arXiv commentv2: 16 pages. Added alternate proof of main result with random coding
References in corpus (8)
- Bell nonlocality
- Entanglement-Assisted Classical Capacity of Noisy Quantum Channels
- Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
- Improving zero-error classical communication with entanglement
- A Tight Upper Bound for the Third-Order Asymptotics for Most Discrete Memoryless Channels
- A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via non-signalling codes
- Entanglement-Enhanced Classical Communication over a Noisy Classical Channel
- On optimal entanglement assisted one-shot classical communication
Cited by in corpus (6)
- Semidefinite programming hierarchies for constrained bilinear optimization
- Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
- Multiple-Access Channel Coding with Non-Signaling Correlations
- Quantum channel coding: Approximation algorithms and strong converse exponents
- Classical communication cost of a bipartite quantum channel assisted by non-signalling correlations
- Can Non-Signaling Assistance Increase the Degrees of Freedom of a Wireless Network?