Technical Program

Paper Detail

Paper Title Identification Capacity of Correlation-Assisted Discrete Memoryless Channels: Analytical Properties and Representations
Paper IdentifierMO3.R7.5
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 Network Information Theory
Location Bièvre, Level 5
Session Time Monday, 08 July, 14:30 - 16:10
Presentation Time Monday, 08 July, 15:50 - 16:10
Manuscript  Click here to download the manuscript
Abstract 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.