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:2010.04239 · IEEE Transactions on Information Theory

Deterministic Identification Over Channels With Power Constraints

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

Published Jun 1, 2021• 19 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2021.3122811

Related papers

Identification without randomization

Rudolf Ahlswede, Ning Cai

In the theory of identification via noisy channels randomization in the encoding has a dramatic effect on the optimal code size, namely, it grows double-exponentially in the blocklength, whereas in the theory of transmission it has the familiar exponential growth. We consider now instead of the discrete memoryless channel (DMC) more robust channels such as the familiar compound (CC) and arbitrarily varying channels (AVC). They can be viewed as models for jamming situations. We make the pessimistic assumption that the jammer knows the input sequence before he acts. This forces communicators to use the maximal error concept and also makes randomization in the encoding superfluous. Now, for a DMC W by a simple observation, made by Ahlswede and Dueck (1989), in the absence of randomization the identification capacity, say C/sub NRI/(W), equals the logarithm of the number of different row-vectors in W. We generalize this to compound channels. A formidable problem arises if the DMC W is replaced by the AVC W. In fact, for 0-1-matrices only in W we are-exactly as for transmission-led to the equivalent zero-error-capacity of Shannon. But for general W the identification capacity C/sub NRI/(W) is quite different from the transmission capacity C(W). An observation is that the separation codes of Ahlswede (1989) are also relevant here. We present a lower bound on C/sub NRI/(W). It implies for instance for W={(/sub 0 1//sup 1 0/), (/sub /spl delta/ (1-/spl delta/)(1 0)/)}, /spl delta//spl isin/(0, 1/2 ) that C/sub NRI/(W)=1, which is obviously tight. It exceeds C(W), which is known to exceed 1-h(/spl delta/), where h is the binary entropy function. We observe that a separation code, with worst case average list size L~ (which we call an NRA code) can be partitioned into L~2/sup ne/ transmission codes. This gives a nonsingle-letter characterization of the capacity of AVC with maximal probability of error in terms of the capacity of codes with list decoding. We also prove that randomization in the decoding does not increase C/sub I/(W) and C/sub NRI/(W). Finally, we draw attention to related work on source coding.

IEEE Transactions on Information Theory•Jan 1, 1999•37 citations

Deterministic Identification Over Poisson Channels

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

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.

arXiv:2107.06061•IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2021•20 citations

Identification over the Gaussian Channel in the Presence of Feedback

Wafa Labidi, Holger Boche, Christian Deppe +1 more

We analyze message identification via Gaussian channels with noiseless feedback, which is part of the Post Shannon theory. The consideration of communication systems beyond Shannon's approach is useful in order to increase the efficiency of information transmission for certain applications. If the noise variance is positive, we propose a coding scheme that generates infinite common randomness between the sender and the receiver. We show that any identification rate via the Gaussian channel with noiseless feedback can be achieved. The remarkable result is that this applies to both rate definitions$\frac{1}{n}\log M$(as defined by Shannon for transmission) and$\frac{1}{n}\ \log \log\ M$— (as defined by Ahlswede and Dueck for identification). We can even show that our result holds regardless of the selected scaling for the rate. A detailed version with all proofs, explanations and more discussions can be found in [1].

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•23 citations

Identification in the presence of feedback-a discovery of new capacity formulas

Rudolf Ahlswede, G. Dueck

A study is made of the identification problem in the presence of a noiseless feedback channel, and the second-order capacity C/sub f/ (resp. C/sub F/) for deterministic (resp. randomized) encoding strategies is determined. Several important phenomena are encountered. (1) Although feedback does not increase the transmission capacity of a discrete memoryless channel (DMC), it does increase the (second-order) identification capacity; (2) noise increases C/sub f/; (3) the structure of the new capacity formulas is simpler than C.E. Shannon's (1948) familiar formula. This has the effect that proofs of converses become easier than in the authors' previous work.>

IEEE Transactions on Information Theory•Jan 1, 1989•133 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•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, 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•18 citations
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.
In the theory of identification via noisy channels randomization in the encoding has a dramatic effect on the optimal code size, namely, it grows double-exponentially in the blocklength, whereas in the theory of transmission it has the familiar exponential growth. We consider now instead of the discrete memoryless channel (DMC) more robust channels such as the familiar compound (CC) and arbitrarily varying channels (AVC). They can be viewed as models for jamming situations. We make the pessimistic assumption that the jammer knows the input sequence before he acts. This forces communicators to use the maximal error concept and also makes randomization in the encoding superfluous. Now, for a DMC W by a simple observation, made by Ahlswede and Dueck (1989), in the absence of randomization the identification capacity, say C/sub NRI/(W), equals the logarithm of the number of different row-vectors in W. We generalize this to compound channels. A formidable problem arises if the DMC W is replaced by the AVC W. In fact, for 0-1-matrices only in W we are-exactly as for transmission-led to the equivalent zero-error-capacity of Shannon. But for general W the identification capacity C/sub NRI/(W) is quite different from the transmission capacity C(W). An observation is that the separation codes of Ahlswede (1989) are also relevant here. We present a lower bound on C/sub NRI/(W). It implies for instance for W={(/sub 0 1//sup 1 0/), (/sub /spl delta/ (1-/spl delta/)(1 0)/)}, /spl delta//spl isin/(0, 1/2 ) that C/sub NRI/(W)=1, which is obviously tight. It exceeds C(W), which is known to exceed 1-h(/spl delta/), where h is the binary entropy function. We observe that a separation code, with worst case average list size L~ (which we call an NRA code) can be partitioned into L~2/sup ne/ transmission codes. This gives a nonsingle-letter characterization of the capacity of AVC with maximal probability of error in terms of the capacity of codes with list decoding. We also prove that randomization in the decoding does not increase C/sub I/(W) and C/sub NRI/(W). Finally, we draw attention to related work on source coding.
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.
We analyze message identification via Gaussian channels with noiseless feedback, which is part of the Post Shannon theory. The consideration of communication systems beyond Shannon's approach is useful in order to increase the efficiency of information transmission for certain applications. If the noise variance is positive, we propose a coding scheme that generates infinite common randomness between the sender and the receiver. We show that any identification rate via the Gaussian channel with noiseless feedback can be achieved. The remarkable result is that this applies to both rate definitions1nlog⁡M\frac{1}{n}\log Mn1​logM(as defined by Shannon for transmission) and1n log⁡log⁡ M\frac{1}{n}\ \log \log\ Mn1​ loglog M— (as defined by Ahlswede and Dueck for identification). We can even show that our result holds regardless of the selected scaling for the rate. A detailed version with all proofs, explanations and more discussions can be found in [1].
A study is made of the identification problem in the presence of a noiseless feedback channel, and the second-order capacity C/sub f/ (resp. C/sub F/) for deterministic (resp. randomized) encoding strategies is determined. Several important phenomena are encountered. (1) Although feedback does not increase the transmission capacity of a discrete memoryless channel (DMC), it does increase the (second-order) identification capacity; (2) noise increases C/sub f/; (3) the structure of the new capacity formulas is simpler than C.E. Shannon's (1948) familiar formula. This has the effect that proofs of converses become easier than in the authors' previous work.>
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.
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.