Shannon Theory
Capacity Computation

On the Algorithmic Computability of Achievability and Converse: ϵ-Capacity of Compound Channels and Asymptotic Bounds of Error-Correcting Codes

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

Date & Time

01:00 am – 01:00 am


A coding theorem consists of two parts: achievability and converse which establish lower and upper bounds on the capacity. This paper analyzes these bounds from a fundamental, algorithmic point of view by studying whether or not such bounds can be computed algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers. To this end, computable continuous functions are studied and properties of computable sequences of such functions are identified. Subsequently, these findings are exemplarily applied to two different open problems. The first one is the $\epsilon$-capacity of compound channels which is unknown to date. It is studied whether or not the -capacity can be algorithmically computed and it is shown that there is no computable characterization of the difference between computable upper and lower bounds possible. Thus, computable sharp lower and upper bounds on the $\epsilon$-capacity of computable compound channels cannot exist. The crucial consequence is that the -capacity cannot be characterized by a finite-letter entropic expression. The second application involves asymptotic bounds for error-correcting codes which is a long-standing open problem in coding theory. Only lower and upper bounds are known which are not sharp. It is conjectured that the asymptotic bound is indeed a non-computable function which would then imply with the previous findings that it is impossible to find computable lower and upper bounds that are asymptotically tight.


Holger Boche

Lehrstuhl für Theoretische Informationstechnik

Rafael F. Schaefer

Technische Universität Berlin

H. Vincent Poor

Princeton University
Private Conversation

Reach out to the speaker privately

Questions & Answers

Post a publicly available question

No questions have been asked.

Session Chair

Tobias Koch

Universidad Carlos III de Madrid