Technical Program

Paper Detail

Paper IDS.1.2
Paper Title On the Algorithmic Computability of Achievability and Converse: ϵ-Capacity of Compound Channels and Asymptotic Bounds of Error-Correcting Codes
Authors Holger Boche, Technische Universität München, Germany; Rafael F. Schaefer, Technische Universität Berlin, Germany; H. Vincent Poor, Princeton University, United States
Session S.1: Capacity Computation
Presentation Lecture
Track Shannon Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract 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.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!