A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via non-signalling codes

Abstract

Motivated by recent work on entanglement-assisted codes for sending messages over classical channels, the larger, easily characterised class of non-signalling codes is defined. Analysing the optimal performance of these codes yields an alternative proof of the finite block length converse of Polyanskiy, Poor and Verdú, and shows that they achieve this converse. This provides an explicit formulation of the converse as a linear program which has some useful features. For discrete memoryless channels, it is shown that non-signalling codes attain the channel capacity with zero error probability if and only if the dispersion of the channel is zero.

8 pages, 2 figures, submitted to IEEE Trans. Inf. T

References in corpus (4)

• Improving zero-error classical communication with entanglement
• Zero-error channel capacity and simulation assisted by non-local correlations
• Entanglement can increase asymptotic rates of zero-error classical communication over classical channels
• Entanglement-assisted zero-error capacity is upper bounded by the Lovasz theta function

Cited by in corpus (20)

• Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Renyi relative entropy
• Quantifying the magic of quantum channels
• Finite blocklength converse bounds for quantum channels
• On the power of PPT-preserving and non-signalling codes
• Quantum Coding with Finite Resources
• Semidefinite programming strong converse bounds for classical capacity
• Quantum Channel Simulation and the Channel's Smooth Max-Information
• Semidefinite programming relaxations for quantum correlations
• On converse bounds for classical communication over quantum channels
• Semidefinite programming hierarchies for constrained bilinear optimization
• Algorithmic Aspects of Optimal Channel Coding
• Multiple-Access Channel Coding with Non-Signaling Correlations
• Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
• Separation between quantum Lovász number and entanglement-assisted zero-error classical capacity
• Channel Simulation: Finite Blocklengths and Broadcast Channels
• On optimal entanglement assisted one-shot classical communication
• 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?
• Retrocausal capacity of a quantum channel: Communicating through noisy closed timelike curves