pith. sign in

arxiv: 2605.05168 · v1 · submitted 2026-05-06 · 💻 cs.IT · math.IT

Deterministic identification for Bernoulli channels and related channels with continuous input

Pau Colomer , Christian Deppe , Holger Boche , Andreas Winter This is my paper

Pith reviewed 2026-05-08 15:54 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords deterministic identificationBernoulli channelcontinuous inputidentification capacitygalaxy codesreliability functionerror exponents
0
0 comments X

The pith

The deterministic identification capacity for Bernoulli channels and related continuous-input channels equals exactly 1/2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves that the deterministic identification capacity Ċ_DI(W) equals 1/2 for the Bernoulli channel and any memoryless channel whose output distributions form a continuous curve. It achieves this by adapting galaxy code constructions to these channels and showing the converse bound is tight. A reader would care because it settles the exact asymptotic growth rate of identifiable messages, which follows the linearithmic n log n scaling with a precise leading coefficient of 1/2. The analysis also tightens bounds on the reliability function for the rate-error tradeoff when errors are small.

Core claim

For memoryless channels with continuous input alphabets, we extend the galaxy code construction to the Bernoulli channel and to any channel W whose image contains a continuous curve of output probability distributions, thereby admitting a reduction to the Bernoulli channel on a subinterval of inputs; this proves the converse bound is tight and establishes Ċ_DI(W) = 1/2, while also deriving improved lower bounds on the reliability function that approach the converse at leading order for small error exponents.

What carries the argument

Optimized galaxy codes for deterministic identification, which achieve the tight bound when combined with reduction of the general channel to the Bernoulli channel restricted to a subinterval of inputs.

If this is right

  • The exact DI capacity is settled at 1/2 for this broad class of channels.
  • Improved lower bounds on the reliability function are obtained that match the converse at leading order for small exponents.
  • The rate-reliability tradeoff gap is narrowed for the small-error regime.
  • The linearithmic message growth is now characterized with the precise constant 1/2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The earlier AWGN result is a special case of the same reduction-plus-galaxy-code argument.
  • The approach extends immediately to any other continuous-input channel whose output image includes a continuous curve.
  • This supplies a concrete target rate for practical identification schemes over continuous signals such as optical or wireless channels.
  • It raises the question of capacity for channels that lack a continuous curve in their output image.

Load-bearing premise

The channel has an image containing a continuous curve of output probability distributions, which permits reduction to the Bernoulli channel on a suitable input subinterval.

What would settle it

An explicit computation for the Bernoulli channel at moderate blocklengths showing that the largest code size with vanishing error grows strictly slower or faster than required for Ċ_DI = 1/2.

Figures

Figures reproduced from arXiv: 2605.05168 by Andreas Winter, Christian Deppe, Holger Boche, Pau Colomer.

Figure 1
Figure 1. Figure 1: Schematic structure of a d-angle-dense arrangement at layer ℓ around the point ⃗osℓ−1 (which, at the same time, is a point in the ℓ − 1-layer). Observe that the orthogonal projection of the ℓ layer point ⃗os˜ℓ onto the vector ⃗vsℓ−1→sℓ is at least d. The two red lines, respectively orthogonal to the vectors ⃗vsℓ−1→sℓ and ⃗vsℓ−1→s˜ℓ represent the regions where the ℓ+ 1 layer will be arranged. Notice that an… view at source ↗
Figure 2
Figure 2. Figure 2: In high dimensions, a cube is better pictured not as a solid box but view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript extends the galaxy-code construction from AWGN channels to Bernoulli channels and, more generally, to any memoryless channel W whose image contains a continuous curve of output distributions. This permits a reduction to a Bernoulli channel on a subinterval of inputs. The authors exhibit an explicit code achieving the previously known converse bound of 1/2, thereby proving that the deterministic identification capacity Ċ_DI(W) equals 1/2 for this class. They further derive improved lower bounds on the rate-reliability function that approach the converse at leading order for small error exponents.

Significance. If the central construction and reduction hold, the work closes the long-standing gap between achievability and converse for deterministic identification capacity on a broad family of continuous-input channels, generalizing the recent AWGN resolution. The explicit galaxy-code optimization and the matching to the converse bound constitute a concrete advance; the reliability-function analysis supplies an additional quantitative contribution. No machine-checked proofs or fully parameter-free derivations are claimed, but the reduction argument and code construction are presented as the key technical steps.

major comments (2)
  1. [§4] §4 (reduction argument): the claim that the error probability of the galaxy code on the restricted Bernoulli channel carries over unchanged to the original W relies on the continuous curve lying entirely in the image of W; the manuscript must supply the explicit Lipschitz or continuity modulus used to bound the total-variation distance between the induced output distributions, as this controls whether the rate-1/2 achievability survives the reduction without an extra o(1) term.
  2. [Theorem 2] Theorem 2 (reliability lower bound): the leading-order term in the exponent is stated to approach the converse, yet the proof sketch omits the precise optimization of the galaxy-code radius and the resulting Chernoff bound; without these constants the claimed improvement over prior lower bounds cannot be verified numerically for moderate block lengths.
minor comments (2)
  1. [Introduction] Notation: the symbol Ċ_DI is introduced without an explicit definition in the introduction; a one-line reminder that it denotes the deterministic identification capacity (in bits per channel use) would aid readability.
  2. [Figure 1] Figure 1: the caption does not indicate whether the plotted curves are for the Bernoulli or the general-W case; adding this clarification would prevent misinterpretation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. We address the two major comments point by point below. Both points can be resolved by adding explicit details and bounds to the manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (reduction argument): the claim that the error probability of the galaxy code on the restricted Bernoulli channel carries over unchanged to the original W relies on the continuous curve lying entirely in the image of W; the manuscript must supply the explicit Lipschitz or continuity modulus used to bound the total-variation distance between the induced output distributions, as this controls whether the rate-1/2 achievability survives the reduction without an extra o(1) term.

    Authors: We thank the referee for highlighting this technical point. The reduction in Section 4 is based on the assumption that the output distributions form a continuous curve in total variation distance. Because the input set is compact and the channel map x ↦ P_x is continuous (by the problem setup), the restriction to the subinterval yields a uniformly continuous curve. In the revision we will insert an explicit lemma stating the modulus: for every ε > 0 there exists δ > 0 such that |x − x′| < δ implies TV(P_x, P_{x′}) < ε. This bound is independent of n and ensures that the total-variation discrepancy between the original channel and the Bernoulli approximation contributes only an o(1) term to the error probability, preserving the exact rate-1/2 achievability. The revised text will contain the lemma together with the resulting error-probability comparison. revision: yes

  2. Referee: [Theorem 2] Theorem 2 (reliability lower bound): the leading-order term in the exponent is stated to approach the converse, yet the proof sketch omits the precise optimization of the galaxy-code radius and the resulting Chernoff bound; without these constants the claimed improvement over prior lower bounds cannot be verified numerically for moderate block lengths.

    Authors: We agree that the current sketch of the proof of Theorem 2 is too brief for numerical verification. In the revised manuscript we will expand the argument to include (i) the explicit optimization of the galaxy-code radius r_n as a function of the target error exponent E and block length n, and (ii) the resulting closed-form Chernoff bound on the pairwise error probability. With these constants supplied, the improvement over earlier lower bounds can be evaluated directly for moderate n. The leading-order term remains unchanged and continues to match the converse at the first order in E. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central result establishes tightness of the converse bound Ċ_DI(W) = 1/2 by exhibiting an explicit achievability construction (galaxy codes) that meets a previously known independent converse after reducing qualifying channels to a Bernoulli channel on a subinterval via a continuous curve in the image of W. This reduction and the subsequent matching are constructive and do not rely on self-definitional equivalences, fitted parameters renamed as predictions, or load-bearing self-citations whose validity is internal to the present work. The derivation remains self-contained against external benchmarks and prior bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the existence of an optimizable galaxy code for the Bernoulli channel and on the domain assumption that the channel image contains a continuous curve permitting reduction to a Bernoulli subchannel. No explicit free parameters or new entities are described in the abstract.

axioms (2)
  • standard math Standard properties of memoryless channels and output probability distributions
    Used to define the channel model and the image of output distributions.
  • domain assumption The channel image contains a continuous curve of output distributions
    This is the explicit condition stated for the reduction to the Bernoulli channel on a subinterval.

pith-pipeline@v0.9.0 · 5494 in / 1330 out tokens · 44525 ms · 2026-05-08T15:54:07.048354+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 4 canonical work pages

  1. [1]

    A mathematical theory of communication,

    C. E. Shannon, “A mathematical theory of communication,”The Bell System Technical Journal, vol. 27, no. 3&4, pp. 379–423 & 623–656, 1948

    1948

  2. [2]

    Identification via channels,

    R. Ahlswede and G. Dueck, “Identification via channels,”IEEE Trans- actions on Information Theory, vol. 35, no. 1, pp. 15–29, 1989

    1989

  3. [3]

    New results in the theory of identification via channels,

    T. S. Han and S. Verd ´u, “New results in the theory of identification via channels,”IEEE Transactions on Information Theory, vol. 38, pp. 14– 25, 1 1992

    1992

  4. [4]

    Novel information theoretical approaches,

    H. Boche, J. Cabrera, C. Deppe, P. Kutsevol, S. Wang, F. Fitzek, S. Hirche, W. Kellerer, W. Labidi, J. Rosenberger, R. Schaefer, C. von Lengerke, M. Wiese, S. Rezwan, P. Sheshagiri, and R. Ezzine, “Novel information theoretical approaches,” in6G-life: Unveiling the Future of Technological Sovereignty, Sustainability and Trustworthiness(F. Fitzek, H. Boche...

    2026

  5. [5]

    A theory of goal-oriented communication,

    O. Goldreich, B. Juba, and M. Sudan, “A theory of goal-oriented communication,”J. ACM, vol. 59, May 2012

    2012

  6. [6]

    Identification without randomization,

    R. Ahlswede and N. Cai, “Identification without randomization,”IEEE Transactions on Information Theory, vol. 45, pp. 2636–2642, 11 1999

    1999

  7. [7]

    Deterministic Identification Over Channels With Power Constraints,

    M. J. Salariseddigh, U. Pereg, H. Boche, and C. Deppe, “Deterministic Identification Over Channels With Power Constraints,”IEEE Transac- tions on Information Theory, vol. 68, pp. 1–24, 1 2022

    2022

  8. [8]

    Deterministic Identification Over Fading Channels,

    M. J. Salariseddigh, U. Pereg, H. Boche, and C. Deppe, “Deterministic Identification Over Fading Channels,” inProc. 2020 IEEE Information Theory Workshop (ITW), pp. 1–5, 2021

    2020

  9. [9]

    Rate-Reliability Tradeoff for Deterministic Identification over Gaussian Channels,

    P. Colomer, C. Deppe, H. Boche, and A. Winter, “Rate-reliability tradeoff for deterministic identification over Gaussian channels.” ArXiv[cs.IT]:2602.12182, 2 2026

    work page arXiv 2026

  10. [10]

    Deterministic Identification for Molecular Communications Over the Poisson Channel,

    M. J. Salariseddigh, V . Jamali, U. Pereg, H. Boche, C. Deppe, and R. Schober, “Deterministic Identification for Molecular Communications Over the Poisson Channel,”IEEE Transactions on Molecular, Biological and Multi-Scale Communications, vol. 9, pp. 408–424, 4 2023

    2023

  11. [11]

    Deterministic identi- fication over channels with finite output: a dimensional perspective on superlinear rates,

    P. Colomer, C. Deppe, H. Boche, and A. Winter, “Deterministic identi- fication over channels with finite output: a dimensional perspective on superlinear rates,”IEEE Transactions on Information Theory, vol. 71, no. 5, pp. 3373–3396, 2025

    2025

  12. [12]

    Rate-Reliability Tradeoff for Deterministic Identification,

    P. Colomer, C. Deppe, H. Boche, and A. Winter, “Rate-Reliability Tradeoff for Deterministic Identification,”IEEE Transactions on Com- munications, 2025. ArXiv:2502.02389

    work page arXiv 2025

  13. [13]

    J. M. Fraser,Assouad Dimension and Fractal Geometry. Cambridge University Press, 2020

    2020

  14. [14]

    J. C. Robinson,Dimensions, Embeddings, and Attractors. Cambridge University Press, 2010

    2010

  15. [15]

    Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Chan- nels

    P. Colomer, C. Deppe, H. Boche, and A. Winter, “Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Chan- nels.” ArXiv[cs.IT]:2504.20991, 4 2025

    work page arXiv 2025

  16. [16]

    Galaxy Codes: Advancing Achievability for Deterministic Identification via Gaussian Channels,

    H. Boche, C. Deppe, S. Mahmoodi, and G. Omidi, “Galaxy codes: Advancing achievability for deterministic identification via gaussian channels,” in2025 IEEE International Symposium on Information The- ory (ISIT), 2025. ArXiv[cs.IT]:2501.12548

    work page arXiv 2025

  17. [17]

    Optimal codes for deterministic identification over gaussian channels: Closing the capacity gap,

    P. Colomer, C. Deppe, H. Boche, and A. Winter, “Optimal codes for deterministic identification over gaussian channels: Closing the capacity gap,” 2026

    2026

  18. [18]

    Csisz ´ar and J

    I. Csisz ´ar and J. K ¨orner,Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2 ed., 2011

    2011

  19. [19]

    Probability inequalities for sums of bounded random variables,

    W. Hoeffding, “Probability inequalities for sums of bounded random variables,”Journal of the American Statistical Association, vol. 58, no. 301, pp. 13–30, 1963

    1963

  20. [20]

    J. H. Conway and N. J. A. Sloane,Sphere Packings, Lattices and Groups, vol. 290 ofGrundlehren der mathematischen Wissenschaften. Springer, 3 ed., 1999

    1999

  21. [21]

    Vershynin,High-Dimensional Probability: An Introduction with Applications in Data Science

    R. Vershynin,High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2018

    2018

  22. [22]

    Capacity and cutoff rate for poisson-type channels,

    M. Davis, “Capacity and cutoff rate for poisson-type channels,”IEEE Transactions on Information Theory, vol. 26, no. 6, pp. 710–715, 1980

    1980

  23. [23]

    Receiver design for digital fiber optic communication systems, i,

    S. D. Personick, “Receiver design for digital fiber optic communication systems, i,”The Bell System Technical Journal, vol. 52, no. 6, pp. 843– 874, 1973

    1973

  24. [24]

    On optical data communication via direct detection of light pulses,

    J. E. Mazo and J. Salz, “On optical data communication via direct detection of light pulses,”The Bell System Technical Journal, vol. 55, no. 3, pp. 347–369, 1976

    1976

  25. [25]

    A com- prehensive survey of recent advancements in molecular communication,

    N. Farsad, H. B. Yilmaz, A. Eckford, C.-B. Chae, and W. Guo, “A com- prehensive survey of recent advancements in molecular communication,” IEEE Communications Surveys & Tutorials, vol. 18, no. 3, pp. 1887– 1919, 2016

    1919

  26. [26]

    Channel modeling for diffusive molecular communication—a tutorial review,

    V . Jamali, A. Ahmadzadeh, W. Wicke, A. Noel, and R. Schober, “Channel modeling for diffusive molecular communication—a tutorial review,”Proceedings of the IEEE, vol. 107, no. 7, pp. 1256–1301, 2019

    2019

  27. [27]

    Bits through queues,

    V . Anantharam and S. Verdu, “Bits through queues,”IEEE Transactions on Information Theory, vol. 42, no. 1, pp. 4–18, 1996

    1996

  28. [28]

    Capacity of a pulse amplitude modulated direct detection photon channel,

    S. Shamai, “Capacity of a pulse amplitude modulated direct detection photon channel,”IEE Proceedings I (Communications, Speech and Vision), vol. 137, pp. 424–430, 1990

    1990

  29. [29]

    Deterministic identification for mc isi-poisson channel,

    M. J. Salariseddigh, V . Jamali, U. Pereg, H. Boche, C. Deppe, and R. Schober, “Deterministic identification for mc isi-poisson channel,” inICC 2023 - IEEE International Conference on Communications, pp. 6108–6113, 2023

    2023

  30. [30]

    Identification over pois- son isi channels: Feedback and molecular applications,

    Y . Zhao, P. Colomer, H. Boche, and C. Deppe, “Identification over pois- son isi channels: Feedback and molecular applications,” inGLOBECOM 2025 - 2025 IEEE Global Communications Conference, pp. 1208–1213, 2025

    2025

  31. [31]

    A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations,

    H. Chernoff, “A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations,”The Annals of Mathe- matical Statistics, vol. 23, no. 4, pp. 493 – 507, 1952

    1952

  32. [32]

    R. G. Gallager,Information Theory and Reliable Communication, vol. 30 ofCIMS – International Centre for Mechanical Sciences, Courses and Lectures. Vienna: Springer Verlag, 1 ed., 1972

    1972

  33. [33]

    Deterministic iden- tification in maximally asymmetric error regimes,

    P. Colomer, C. Deppe, H. Boche, and A. Winter, “Deterministic iden- tification in maximally asymmetric error regimes,” inProc. 2025 IEEE European Wireless, 2025. 13

    2025