Deterministic Identification in Maximally Asymmetric Error Regimes

Abstract:
We study the performance of deterministic identification (DI) codes under maximally asymmetric error regimes. This setting lies outside the scope of recent results on the tradeoff between rate and reliability in DI, which show that when both error probabilities vanish exponentially, i.e., lambda1 = 2−nE1 , lambda2 = 2−nE2 , the number of bits of identifiable messages can grow only linearly with the block length n, in contrast to the linearithmic (message length Rn log n) growth observed in the setting of slowly vanishing errors. We show that even if only one error vanishes exponentially (Ei > 0) while the other decays arbitrarily slowly (lambdaj < 1), a regime we refer to as maximally asymmetric, this is still insufficient to recover the linearithmic behaviour. Our result is based on a generalized converse bound for finite block length n, closely connected to binary hypothesis testing at finite n. The results are extended to classical-quantum channels.