TY - GEN
T1 - Identification Capacity of Correlation-Assisted Discrete Memoryless Channels
T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019
AU - Boche, Holger
AU - Schaefer, Rafael F.
AU - Vincent Poor, H.
N1 - Funding Information:
This work of H. Boche was supported in part by the German Ministry of Education and Research (BMBF) within the national initiative for molecular communication under Grant 16KIS0914, in part by the Gottfried Wilhelm Leibniz Programme of the German Research Foundation (DFG) under Grant BO 1734/20-1, and in part by the DFG under Germany’s Excellence Strategy – EXC-2111 – 390814868. This work of H. V. Poor was supported by the U.S. National Science Foundation under Grants CCF-0939370 and CCF-1513915.
Publisher Copyright:
© 2019 IEEE.
PY - 2019/7
Y1 - 2019/7
N2 - The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not. Identification via correlation-assisted discrete memoryless channels is studied, where the transmitter and the receiver further have access to correlated source observations. Analytical properties and representations of the corresponding identification capacity are studied. In this paper, it is shown that the identification capacity cannot be represented as a maximization of a single-letter (or multi-letter with fixed length) expression of entropic quantities. Further, it is shown that the identification capacity is not Banach-Mazur computable and therewith not Turing computable. Consequently, there is no algorithm that can simulate or compute the identification capacity, even if there are no limitations on computational complexity and computing power.
AB - The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not. Identification via correlation-assisted discrete memoryless channels is studied, where the transmitter and the receiver further have access to correlated source observations. Analytical properties and representations of the corresponding identification capacity are studied. In this paper, it is shown that the identification capacity cannot be represented as a maximization of a single-letter (or multi-letter with fixed length) expression of entropic quantities. Further, it is shown that the identification capacity is not Banach-Mazur computable and therewith not Turing computable. Consequently, there is no algorithm that can simulate or compute the identification capacity, even if there are no limitations on computational complexity and computing power.
UR - http://www.scopus.com/inward/record.url?scp=85072321682&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85072321682&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2019.8849851
DO - 10.1109/ISIT.2019.8849851
M3 - Conference contribution
AN - SCOPUS:85072321682
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 470
EP - 474
BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 7 July 2019 through 12 July 2019
ER -