Rate-reliability tradeoff for deterministic identification

Pau Colomer, Christian Deppe, Holger Boche, and Andreas Winter · 2025

Read Rate-reliability tradeoff for deterministic identification by Pau Colomer, Christian Deppe, Holger Boche, and Andreas Winter (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02389.txt.

Introduction

Pau Colomer and three co-authors study how fast a receiver can name a sender when both kinds of error must shrink very fast, in a 2025 arXiv paper. The task is identification, not full message reading: the receiver only asks whether one set message was sent. Past work let errors fade slowly and found a near linear growth law.

Here both error odds must fall at a set pace in the block length. The team finds plain linear growth comes back, with a rate set by that pace. They give upper and lower bounds built from packing and covering counts of the channel's output set. For small paces the rate takes a neat form tied to the shape of that set. Even one fast error breaks the old growth law.

Catalog record

CREATORPau Colomer, Christian Deppe, Holger Boche, and Andreas Winter
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02389

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Rate-reliability tradeoff for deterministic identification Thanks: A preliminary version of the present work has been accepted for presentation at the 2025 IEEE International Conference on Communications, Montreal QB, 8-12 June 2025 [ 1 ] ; and the recent results session of the 2025 IEEE International Symposium on Information Theory, Ann Harbor MI (USA), 22-27 June 2025. Thanks: HB and CD are supported by the German Federal Ministry of Education and Research (BMBF) within the national initiative on 6G Communication Systems through the research hub 6G-life, grants 16KISK002 and 16KISK263, within the national initiative on Post Shannon Communication (NewCom), grants 16KIS1003K and 16KIS1005, within the national initiative “QuaPhySI”, grants 16KISQ1598K and 16KIS2234, and within the national initiative “QTOK”, grant 16KISQ038. HB has further received funding from the German Research Foundation (DFG) within Germany’s Excellence Strategy EXC-2092-390781972. AW is supported by the European Commission QuantERA grant ExTRaQT (Spanish MICIN project PCI2022-132965), by the Spanish MICIN (projects PID2019-107609GB-I00 and PID2022-141283NB-I00) with the support of FEDER funds, by the Spanish MICIN with funding from European Union NextGenerationEU (PRTR-C17.I1) and the Generalitat de Catalunya, and by the Alexander von Humboldt Foundation. PC and AW are furthermore supported by the Institute for Advanced Study of the Technical University Munich (IAS-TUM). Pau Colomer, Christian Deppe, Holger Boche, and Andreas Winter Abstract We investigate deterministic identification over arbitrary memoryless channels under the constraint that the error probabilities of first and second kind are exponentially small in the block length 𝐧 \mathbf{n} , controlled by reliability exponents 𝐄 𝟏 , 𝐄 𝟐 ≥ 𝟎 \mathbf{E_{1},E_{2}\geq 0} . In contrast to the regime of slowly vanishing errors, where the identifiable message length scales linearithmically as 𝚯 ⁡ ( 𝐧 ​ log ⁡ 𝐧 ) \mathbf{\Theta(n\log n)} , here we find that for positive exponents linear scaling is restored, now with a rate that is a function of the reliability exponents. We give upper and lower bounds on the ensuing rate-reliability function in terms of (the logarithm of) the packing and covering numbers of the channel output set, which for small error exponents 𝐄 𝟏 , 𝐄 𝟐 > 𝟎 \mathbf{E_{1},E_{2}>0} can be expanded in leading order as the product of the Minkowski dimension of a certain parametrisation the channel output set and log ⁡ min ⁡ { 𝐄 𝟏 , 𝐄 𝟐 } \mathbf{\log\min\{E_{1},E_{2}\}} . These allow us to recover the previously observed slightly superlinear identification rates, and offer a different perspective for understanding them in more traditional information theory terms. We also show that even if only one of the two errors is required to be exponentially small, the linearithmic scaling is lost. We further illustrate our results with a discussion of the case of dimension zero, and extend them to classical-quantum channels and quantum channels with tensor product input restriction. I Introduction I-A Background and previous work In Shannon’s fundamental model of communication [ 2 ] , the receiver aims to faithfully recover an original message sent through n uses of a memoryless noisy channel W:\mathcal{X}\rightarrow\mathcal{Y} , given by a probability transition kernel between measurable spaces \mathcal{X} and \mathcal{Y} . The maximum number M of transmittable messages scales exponentially with n , and thus we define the (linear-scale) rate of a transmission code as R=\frac{1}{n}\log M , with \log the binary logarithm. The maximum rate for asymptotically faithful transmission – that is, with arbitrarily small probability of error for sufficiently long code words – is known as the capacity C of the channel [ 2 , 3 ] . This model contrasts with the identification task in which instead of recovering the initial message, the receiver is only interested in knowing whether it is equal to one particular message of their choice or not. Jaja demonstrated in [ 4 ] that this task involves lower communication complexity than Shannon’s original transmission scenario. Building on this result, Ahlswede and Dueck [ 5 ] fully characterized the identification problem and analyzed its performance over general discrete memoryless channels (DMCs) using a randomized encoder. They showed that identification codes can achieve doubly exponential growth of the number N of messages as a function of the block length n , i.e. \log N\sim 2^{nR} . In other words, we can identify exponentially more messages than we can transmit. In general, randomized identification codes can achieve this exponential scaling [ 6 , 7 ] . As these results rely crucially on randomized encodings, it is natural to ask what happens if we impose a deterministic approach. Definition 1 . An (n,N,\lambda_{1},\lambda_{2}) deterministic identification (DI) code is a family \{(u_{j},\mathcal{E}_{j}):j\in[N]\} consisting of code words u_{j}\in\mathcal{X}^{n} and subsets \mathcal{E}_{j}\subset\mathcal{Y}^{n} , such that \forall j\neq k\in[N],\quad W_{u_{j}}(\mathcal{E}_{j})\geq 1-\lambda_{1},\quad W_{u_{j}}(\mathcal{E}_{k})\leq\lambda_{2}, where we use the notation W_{u_{j}}:=W^{n}(\cdot|u_{j}) for the conditional probability distributions at the output. It was initially observed that DI leads to much poorer results in terms of code size scaling in the block length [ 5 , 8 ] than the unrestricted randomized identification. Indeed, DI over discrete memoryless channels can only lead to linear scaling of the message length, \log N\sim Rn [ 9 ] as in Shannon’s communication paradigm (albeit with a higher rate R ). Despite this poorer performance, interest in deterministic codes has recently been renewed, as they have proven to be easier to implement and simulate [ 10 ] , to explicitly construct [ 11 ] , and offer reliable single-block performance [ 5 ] ; see in particular [ 12 ] for identification codes. Also, surprisingly, certain channels with continuous input alphabets have DI codes governed by a slightly superlinear scaling in the block length: \log N\sim Rn\log n (commonly referred to as linearithmic ). This was first observed for Gaussian channels [ 9 ] , Gaussian channels with both fast and slow fading [ 13 , 14 ] , and Poisson channels [ 15 , 16 ] . In our recent work [ 17 , 18 ] we have generalized all these particular DI results, proving that the linearithmic scaling observed in these special cases is actually a feature exhibited by general channels with discrete output. For the rest of the paper we will in fact assume that \mathcal{Y} is finite. It is important to emphasize the fundamental implications of different scalings beyond the value of the rate expressions. When a code achieves superlinear scaling – for example linearithmic \log N(n)\sim Rn\log n –, the number of identifiable messages grows asymptotically faster than in the linear regime \log N(n)\sim R^{\prime}n , regardless of how large the linear rate constant might be. That is, even if a linear code achieves a higher rate R^{\prime}>R , the superlinear code will eventually yield infinitely more identifiable messages as n\to\infty . This distinction justifies a careful attention to the growth regime. Specifically when calculating the capacity of a channel, it is crucial to define it in the correct scaling. Indeed, if we have a linearithmic code and calculate the maximum linear (or exponential) rate, we will trivially get \infty (or 0). A meaningful optimum rate value can only be calculated in this example through a suitably defined linearithmic capacity. In [ 17 ] slightly superlinear (in fact, linearithmic) DI capacities \dot{C}_{\text{DI}} of general channels were calculated in the pessimistic and optimistic regimes (for

Read the complete text