Identification coding lets a receiver answer 'was this message sent?' and can identify a doubly exponential number of messages as blocklength grows; this survey reviews the theory and maps it to applications.
Deterministic identification for Bernoulli channels and related channels with continuous input
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
For memoryless channels with continuous input alphabets, deterministic identification (DI) typically exhibits a linearithmic ($n\log n$) message growth. However, the exact DI capacity has long remained open due to a persistent gap between the best known achievability and converse bounds. This gap was recently closed for AWGN channels via a novel code construction optimising the "galaxy" codes. Here, we extend this approach to the Bernoulli channel and subsequently to any channel $W$ whose image contains a continuous curve of output probability distributions, and hence admits a reduction to the Bernoulli channel restricted to a subinterval of inputs. As a consequence, we prove that the converse bound is tight and establish $\dot{C}_{\text{DI}}(W) = \frac 12$ for this broad class of channels, thereby closing the long-standing capacity gap. A similar gap was also observed for the DI rate-reliability tradeoff. We analyse the tradeoff between rate and error of the proposed code and derive improved lower bounds on the reliability function, approaching the converse at leading order in the regime of small error exponents.
fields
cs.IT 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Identification Codes and Post-Shannon Communication: Theory, Architectures, and Emerging Applications
Identification coding lets a receiver answer 'was this message sent?' and can identify a doubly exponential number of messages as blocklength grows; this survey reviews the theory and maps it to applications.