Deterministic identification for Bernoulli channels and related channels with continuous input
Pau Colomer ⋆ \,\star ,, Christian Deppe † \,\dagger ,, Holger Boche ‡ \,\ddagger ,, Andreas Winter § \,\lx@sectionsign , · 2026
Read Deterministic identification for Bernoulli channels and related channels with continuous input by Pau Colomer ⋆ \,\star ,, Christian Deppe † \,\dagger ,, Holger Boche ‡ \,\ddagger ,, Andreas Winter § \,\lx@sectionsign , (2026) 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-2605-05168.txt.
Introduction
Pau Colomer and three co-authors close a long-standing gap in deterministic identification. That is a communication task where the receiver only needs to know which of a set of messages was sent, not decode data. For channels with continuous inputs, the best achievable and provable limits had never quite met. A recent galaxy code construction closed that gap for Gaussian noise channels.
The authors extend that approach to the Bernoulli channel. From there they handle any channel whose outputs trace a continuous curve, by reducing it to a Bernoulli subproblem. They prove the converse bound is tight for this broad class, settling its identification capacity. They also analyse the rate-reliability trade-off, improving lower bounds on the reliability function toward the converse.
Catalog record
| CREATOR | Pau Colomer ⋆ \,\star ,, Christian Deppe † \,\dagger ,, Holger Boche ‡ \,\ddagger ,, Andreas Winter § \,\lx@sectionsign , |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05168
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deterministic identification for Bernoulli channels and related channels with continuous input Pau Colomer ⋆ \,\star ,, Christian Deppe † \,\dagger ,, Holger Boche ‡ \,\ddagger ,, Andreas Winter § \,\lx@sectionsign , Abstract For memoryless channels with continuous input alphabets, deterministic identification (DI) typically exhibits a linearithmic ( n log n 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 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 C ˙ DI ( W ) = 1 2 \dot{C}_{\text{DI}}(W)=\frac{1}{2} 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. † † \star [email protected], \dagger [email protected], \ddagger [email protected], \lx@sectionsign [email protected]. I Introduction Identification is a post-Shannon communication paradigm in which a sender wishes to convey a message i\in[N] , while the receiver, rather than attempting to fully decode i as in Shannon’s classical transmission setting [ 31 ] , only tests whether the transmitted message coincides with a particular message j\in[N] of its choice. In other words, the decoding task is reduced to a binary decision problem: determine reliably whether i=j or i\neq j . This protocol was first proposed by Ahlswede and Dueck in [ 2 ] . They showed that the length of the identifiable messages scaled exponentially faster with the block length n than the length of the transmittable messages in Shannon’s paradigm. Indeed, while the M decodable messages satisfy \log M\sim Rn , with R the communication rate, the N identifiable messages satisfy \log N\sim 2^{Rn} [ 2 , 20 ] . This surprising exponential improvement motivates the relevance of identification for future large-scale network systems [ 4 ] , specially in the field of event-driven or goal-oriented communications [ 19 ] . It was already observed in [ 2 , 1 ] that the exponential improvement described above is intrinsically linked to the use of randomness at the encoder. In many applications, however, randomness may be costly, difficult to generate reliably, or undesirable due to implementation constraints. This motivates the study of identification schemes without randomization, i.e., deterministic identification (DI) . DI was first investigated for discrete memoryless channels (DMCs) [ 1 , 29 ] . In that setting, the exponential identification advantage disappears: DI codes can only support a linear growth of the message set, i.e., \log N_{\text{DMC}}\sim nR^{\prime} , although the achievable DI rates R^{\prime} may exceed the corresponding transmission capacity [ 29 ] . Surprisingly, the situation changes fundamentally when the channel input alphabet is continuous. Indeed, for the Gaussian channel G and the Poisson channel P (under peak/average power constraints), it was shown that the size of the message set under DI can grow as \log N_{G,P}\sim R^{\prime}n\log n, see [ 29 , 28 , 12 , 27 ] . Following terminology from computer science, we refer to this n\log n scaling as linearithmic . The linearithmic scaling is not limited to the specific channels above, but is rather a prevalent feature of channels with continuous input. Indeed, in [ 8 , 10 ] , it was shown that for the family of channels with continuous input and discrete output alphabets linearithmic DI codes also exist. Definition 1 . An (n,N,\lambda_{1},\lambda_{2}) DI code over n uses of a channel W is a family of pairs \{(u_{i},\mathcal{D}_{i}):i\in[N]\} with u_{i}\in\mathcal{X}^{n} input sequences and \mathcal{D}_{i}\subset\mathcal{Y}^{n} output regions such that, for all distinct i,j\in[N] , and \lambda_{1},\lambda_{2}>0 : W^{n}(\mathcal{D}_{i}|u_{i})\geq 1-\lambda_{1}\quad\text{and}\quad W^{n}(\mathcal{D}_{j}|u_{i})\leq\lambda_{2}. The definition highlights another fundamental distinction between Shannon-style message transmission and identification. While in transmission the receiver produces an estimate \hat{i} of the transmitted message i , and an error occurs whenever \hat{i}\neq i , in identification we have two different types of errors, analogous to the two error events in binary hypothesis testing. The first type is a missed identification and it happens when the messages sent and tested are the same but the test rejects the true message. The second type is a false identification and it occurs when the messages sent and tested are different but the test incorrectly accepts the wrong message. The parameters \lambda_{1} and \lambda_{2} bound respectively the two errors. A good (n,N,\lambda_{1},\lambda_{2}) DI code must control both types of errors simultaneously. A number \dot{R}>0 is said to be an achievable linearithmic rate if there exists a sequence of reliable (n,N^{(n)},\lambda_{1}^{(n)},\lambda_{2}^{(n)}) DI codes such that \lambda_{1}^{(n)},\lambda_{2}^{(n)}\rightarrow 0,\,\,\,\text{and}\,\,\,\dot{R}(n):=\frac{\log N^{(n)}}{n\log n}\rightarrow\dot{R}, (1) as n\to\infty . The (linearithmic) DI capacity of a channel is its largest achievable rate: \dot{C}_{\mathrm{DI}}(W)=\max\bigl\{\dot{R}\,:\,\dot{R}\text{ is achievable}\bigr\}. (2) We use the dot on top of rates and capacities to indicate that they are calculated in the linearithmic scale. A central open problem in DI has been the persistent gap between the best known lower and upper bounds on \dot{C}_{\text{DI}} for channels with continuous input alphabets. In particular, for additive white Gaussian noise (AWGN) channels G [ 29 , 28 ] , the Poisson channel P [ 27 ] , and the Bernoulli channel B [ 8 ] , the capacity was bounded by \frac{1}{4}\leq\dot{C}_{\text{DI}}(G),\dot{C}_{\text{DI}}(P),\dot{C}_{\text{DI}}(B)\leq\frac{1}{2}. (3) Furthermore, a similar gap was found for the general family of arbitrary channels W with discrete output. To be precise, let W:\mathcal{X}\to\mathcal{Y} be a channel with input alphabet \mathcal{X} and output \mathcal{Y} , and denote its channel image by W(\mathcal{X}):=\{W(\cdot|x):x\in\mathcal{X}\}\subseteq\mathcal{P}(\mathcal{Y}), (4) where \mathcal{P}(\mathcal{Y}) is the space of probability measures on \mathcal{Y} . Also, let d_{M} denote the Minkowski dimension [ 17 , 25 ] of this output set W(\mathcal{X}) . Then, it is shown in [ 8 ] , that \frac{d_{M}}{4}\leq\dot{C}_{\text{DI}}(W)\leq\frac{d_{M}}{2}. (5) Only in a few special cases, where the structure of optimal decoders is explicit, the capacity was known [ 8 , 9 ] . Recently, an optimised DI code construction, inspired by [ 5 ] , was shown to achieve the upper bound for the additive white Gaussian noise (AWGN) channel G , thereby establishing \dot{C}_{\text{DI}}(G)=\frac{1}{2} and closing the Gaussian capacity gap [ 11 ] . This naturally raises the question of whether the upper bound in Equation ( 3 ) is also achievable for the Poisson channel, the Bernoulli channel, and broader classes of continuous-input discrete-output channels. In this paper, we answer this question in the affirmative. Building on the underlying geometric ideas of the Gaussian construction in [ 11 ] (in a non-trivial and somewhat counter-intuitive way), we propose a new DI coding scheme for the Bernoulli channel B (see the channel model in Section II ) and prove that it achieves the converse bound in Equation ( 3 ), thereby establishing that \dot{C}_{\text{DI}}(B)=\frac{1}{2} (see Section IV-C ). Then, in