Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2107.06061 · IEEE Globecom Workshops (GC Wkshps)

Deterministic Identification Over Poisson Channels

Mohammad J. Salariseddigh, Uzi Pereg, Holger Boche, Christian Deppe, Robert Schober

Published Dec 1, 2021• 16 citations
arXivHTMLPDF

Abstract

Deterministic identification (DI) for the discrete-time Poisson channel, subject to an average and a peak power constraint, is considered. It is established that the code size scales as 2(nlogn)R, where n and R are the block length and coding rate, respectively. The authors have recently shown a similar property for Gaussian channels [1]. Lower and upper bounds on the DI capacity of the Poisson channel are developed in this scale. Those imply that the DI capacity is infinite in the exponential scale, regardless of the dark current, i.e., the channel noise parameter.

DOI
10.1109/gcwkshps52748.2021.9682110

Related papers

Deterministic Identification Over Channels With Power Constraints

Mohammad J. Salariseddigh, Uzi Pereg, Holger Boche +1 more

Identification capacity is developed without randomization at neither the encoder nor the decoder. In particular, full characterization is established for the deterministic identification (DI) capacity for the Gaussian channel and for the general discrete memoryless channel (DMC) with and without constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness given at the encoder, resulting in a double exponential number of messages. In the deterministic setup, the number of messages scales exponentially, as in Shannon’s transmission paradigm, but the achievable identification rates can be significantly higher than those of transmission. Ahlswede and Dueck further stated a capacity result for the deterministic setting of a DMC, but did not provide an explicit proof. In this paper, a detailed proof is given for both the Gaussian channel and the general DMC. The DI capacity of a Gaussian channel is infinite regardless of the noise.

arXiv:2010.04239•International Conference on Communications•Jun 1, 2021•18 citations

Improved Capacity Upper Bounds for the Discrete-Time Poisson Channel

Mahdi Cheraghchi, João Ribeiro

We present new capacity upper bounds for the discrete-time Poisson channel with no dark current and an average-power constraint. These bounds are a simple consequence of techniques developed by one of the authors for the seemingly unrelated problem of upper bounding the capacity of binary deletion and repetition channels. Previously, the best known capacity upper bound in the regime where the average-power constraint does not approach zero was due to Martinez (JOSA B, 2007), which we re-derive as a special case of our framework. Furthermore, we instantiate our framework to obtain a closed-form bound that noticeably improves the result of Martinez everywhere.

arXiv:1801.02745•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•8 citations

Deterministic Identification Over Channels With Finite Output: A Dimensional Perspective on Superlinear Rates

Pau Colomer, Christian Deppe, Holger Boche +1 more

Following initial work by JaJa, Ahlswede and Cai, and inspired by a recent renewed surge in interest in deterministic identification (DI) via noisy channels, we consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Such a channel is essentially given by its output distributions as a subset in the probability simplex. Our main findings are that the maximum length of messages thus identifiable scales superlinearly as$R\,n\log n$with the block length n, and that the optimal rate R is bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimension d of a certain algebraic transformation of the output set:$\frac {1}{4} d \leq R \leq \frac {1}{2} d$. Remarkably, both the lower and upper Minkowski dimensions play a role in this result. Along the way, we present a Hypothesis Testing Lemma showing that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code. Although we do not know the exact capacity formula, we can conclude that the DI capacity exhibits superactivation: there exist channels whose capacities individually are zero, but whose product has positive capacity. We also generalise these results to classical-quantum channels with finite-dimensional output quantum system, in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.

arXiv:2402.09117•IEEE Transactions on Information Theory•Jan 17, 2025•13 citations

Deterministic Identification Over Channels with Finite Output: A Dimensional Perspective on Superlinear Rates

Pau Colomer, Christian Deppe, Holger Boche +1 more

Following initial work by JaJa, and Ahlswede and Cai, and inspired by a recent renewed surge in interest in deterministic identification (DI) via noisy channels, we consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Such a channel is essentially given by (the closure of) the subset of its output distributions in the probability simplex. Our main findings are that the maximum number of messages thus identifiable scales super-exponentially as$2^{Rn\log n}$with the block length$n$, and that the optimal rate$R$is upper and lower bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimension$d$of a certain algebraic transformation of the output set:$\frac{1}{4}d\leq R\leq\frac{1}{2}d$, Along the way, we present a Hypothesis Testing Lemma that shows it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code. Although we do not know the exact capacity formula, we can conclude that the DI capacity exhibits super-activation: there exist channels whose capacity is zero, but whose product has positive capacity. These results are then generalised to classical-quantum channels with finite-dimensional output quantum system (but arbitrary input alphabet), and in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.

IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•12 citations

Rate-reliability tradeoff for deterministic identification

Pau Colomer, Christian Deppe, Holger Boche +1 more

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 $\mathbf{Θ(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 $\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.

arXiv:2502.02389•Feb 4, 2025•0 citations

Commitment over Gaussian channels with deterministic identification codes

Pau Colomer, Christian Deppe, Holge Boche +1 more

We establish a previously unnoticed connection between commitment (BC), a fundamental cryptographic primitive, and deterministic identification (DI), a post-Shannon communication setting. Specifically, for additive white Gaussian noise channels $\mathcal{G}$ we show that a reliable commitment protocol can be obtained from deterministic identification codes in both the honest but curious and fully dishonest security settings. This viewpoint allows BC schemes to inherit the asymptotic performance of DI codes. Indeed, we show that commitment is naturally achievable in the linearithmic regime, i.e., with message sets of size $N_n=\exp [Θ(n\log n)]$, and we establish a lower bound on the linearithmic-scale BC capacity of $\dot C_{\text{hBC}}(\mathcal G)\geq\frac12$ in the honest but curious case and $\dot C_{\text{BC}}(\mathcal G)\geq\frac14$ in the fully dishonest picture. This refines the best previously known characterisation of the commitment capacity over $\mathcal{G}$, which established only an infinite linear-scale capacity.

arXiv:2610.12413•Oct 8, 2026•0 citations
Deterministic identification (DI) for the discrete-time Poisson channel, subject to an average and a peak power constraint, is considered. It is established that the code size scales as 2(nlogn)R, where n and R are the block length and coding rate, respectively. The authors have recently shown a similar property for Gaussian channels [1]. Lower and upper bounds on the DI capacity of the Poisson channel are developed in this scale. Those imply that the DI capacity is infinite in the exponential scale, regardless of the dark current, i.e., the channel noise parameter.
Identification capacity is developed without randomization at neither the encoder nor the decoder. In particular, full characterization is established for the deterministic identification (DI) capacity for the Gaussian channel and for the general discrete memoryless channel (DMC) with and without constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness given at the encoder, resulting in a double exponential number of messages. In the deterministic setup, the number of messages scales exponentially, as in Shannon’s transmission paradigm, but the achievable identification rates can be significantly higher than those of transmission. Ahlswede and Dueck further stated a capacity result for the deterministic setting of a DMC, but did not provide an explicit proof. In this paper, a detailed proof is given for both the Gaussian channel and the general DMC. The DI capacity of a Gaussian channel is infinite regardless of the noise.
We present new capacity upper bounds for the discrete-time Poisson channel with no dark current and an average-power constraint. These bounds are a simple consequence of techniques developed by one of the authors for the seemingly unrelated problem of upper bounding the capacity of binary deletion and repetition channels. Previously, the best known capacity upper bound in the regime where the average-power constraint does not approach zero was due to Martinez (JOSA B, 2007), which we re-derive as a special case of our framework. Furthermore, we instantiate our framework to obtain a closed-form bound that noticeably improves the result of Martinez everywhere.
Following initial work by JaJa, Ahlswede and Cai, and inspired by a recent renewed surge in interest in deterministic identification (DI) via noisy channels, we consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Such a channel is essentially given by its output distributions as a subset in the probability simplex. Our main findings are that the maximum length of messages thus identifiable scales superlinearly asR nlog⁡nR\,n\log nRnlognwith the block length n, and that the optimal rate R is bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimension d of a certain algebraic transformation of the output set:14d≤R≤12d\frac {1}{4} d \leq R \leq \frac {1}{2} d41​d≤R≤21​d. Remarkably, both the lower and upper Minkowski dimensions play a role in this result. Along the way, we present a Hypothesis Testing Lemma showing that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code. Although we do not know the exact capacity formula, we can conclude that the DI capacity exhibits superactivation: there exist channels whose capacities individually are zero, but whose product has positive capacity. We also generalise these results to classical-quantum channels with finite-dimensional output quantum system, in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.
Following initial work by JaJa, and Ahlswede and Cai, and inspired by a recent renewed surge in interest in deterministic identification (DI) via noisy channels, we consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Such a channel is essentially given by (the closure of) the subset of its output distributions in the probability simplex. Our main findings are that the maximum number of messages thus identifiable scales super-exponentially as2Rnlog⁡n2^{Rn\log n}2Rnlognwith the block lengthnnn, and that the optimal rateRRRis upper and lower bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimensiondddof a certain algebraic transformation of the output set:14d≤R≤12d\frac{1}{4}d\leq R\leq\frac{1}{2}d41​d≤R≤21​d, Along the way, we present a Hypothesis Testing Lemma that shows it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code. Although we do not know the exact capacity formula, we can conclude that the DI capacity exhibits super-activation: there exist channels whose capacity is zero, but whose product has positive capacity. These results are then generalised to classical-quantum channels with finite-dimensional output quantum system (but arbitrary input alphabet), and in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.
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 n\mathbf{n}n, controlled by reliability exponents E1,E2≥0\mathbf{E_1,E_2 \geq 0}E1​,E2​≥0. In contrast to the regime of slowly vanishing errors, where the identifiable message length scales linearithmically as Θ(nlog⁡n)\mathbf{Θ(n\log n)}Θ(nlogn), 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 E1,E2>0\mathbf{E_1,E_2>0}E1​,E2​>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⁡{E1,E2}\mathbf{\log\min\{E_1,E_2\}}logmin{E1​,E2​}. 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.
We establish a previously unnoticed connection between commitment (BC), a fundamental cryptographic primitive, and deterministic identification (DI), a post-Shannon communication setting. Specifically, for additive white Gaussian noise channels G\mathcal{G}G we show that a reliable commitment protocol can be obtained from deterministic identification codes in both the honest but curious and fully dishonest security settings. This viewpoint allows BC schemes to inherit the asymptotic performance of DI codes. Indeed, we show that commitment is naturally achievable in the linearithmic regime, i.e., with message sets of size Nn=exp⁡[Θ(nlog⁡n)]N_n=\exp [Θ(n\log n)]Nn​=exp[Θ(nlogn)], and we establish a lower bound on the linearithmic-scale BC capacity of C˙hBC(G)≥12\dot C_{\text{hBC}}(\mathcal G)\geq\frac12C˙hBC​(G)≥21​ in the honest but curious case and C˙BC(G)≥14\dot C_{\text{BC}}(\mathcal G)\geq\frac14C˙BC​(G)≥41​ in the fully dishonest picture. This refines the best previously known characterisation of the commitment capacity over G\mathcal{G}G, which established only an infinite linear-scale capacity.