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 - 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 -