Capacity of Finite State Channels with Feedback: Algorithmic and Optimization Theoretic Properties


Konferenz / Medium


Harold Vincent Poor Rafael Schaefer Holger Boche Andrea Grigorescu

Research Hub

Research Hub A: Kryptographie der Zukunft
Research Hub B: Eingebettete Sicherheit

Research Challenges

RC 5: Physical-Layer Security


The capacity of finite state channels (FSCs) with feedback has been expressed by a limit of a sequence of multi-letter expressions. Despite many efforts, a closed-form single-letter capacity characterization remains unknown to date. In this paper, the feedback capacity is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. To this aim, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that the feedback capacity of FSCs is not Banach-Mazur computable and therefore also not Borel-Turing computable. As a consequence, it is shown that either achievability or converse (or both) is not Banach-Mazur computable, which means that there are FSCs for which it is impossible to find computable tight upper and lower bounds. Furthermore, it is shown that the feedback capacity cannot be characterized as the maximization of a finite-letter formula of entropic quantities.


Coding Theory
Complexity Theory
Information Theory
Implementation Attacks
Post-Quantum Cryptography