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

IEEE International Symposium on Information Theory (ISIT)

Identification over Channels with Feedback: Discontinuity Behavior and Super-Activation

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

Published Jun 1, 2018• 6 citations
Publisher

Abstract

The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not, and the identification-feedback (IDF) capacity of channels with feedback is studied. The IDF capacity is shown to be discontinuous and super-additive for both deterministic and randomized encoding. For the deterministic IDF capacity the phenomenon of super-activation occurs, which is the strongest form of super-additivity. For the randomized IDF capacity, super-activation is not possible. These findings imply that the IDF capacity is not Turing computable.

DOI
10.1109/isit.2018.8437891

Related papers

Identification Capacity of Correlation-Assisted Discrete Memoryless Channels: Analytical Properties and Representations

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not. Identification via correlation-assisted discrete memoryless channels is studied, where the transmitter and the receiver further have access to correlated source observations. Analytical properties and representations of the corresponding identification capacity are studied. In this paper, it is shown that the identification capacity cannot be represented as a maximization of a single-letter (or multi-letter with fixed length) expression of entropic quantities. Further, it is shown that the identification capacity is not Banach-Mazur computable and therewith not Turing computable. Consequently, there is no algorithm that can simulate or compute the identification capacity, even if there are no limitations on computational complexity and computing power.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•17 citations

On identification via multiway channels with feedback

Rudolf Ahlswede, B. Verboven

For the case of complete feedback, a fairly unified theory of identification is presented. Its guiding principle is the discovery that communicators (sender and receiver) must set up a common random experiment with maximal entropy and use it as randomization for a suitable identification technique. It is shown how this can be done in a constructive manner. The proof of optimality (weak converse) is based on a novel entropy bound, which can be viewed as a substitute for Fano's lemma in the present context. The single-letter characterization of (second-order) capacity regions now rests on an entropy characterization problem, which often can be solved. This is done for the multiple-access channel with deterministic encoding strategies, and for the broadcast channel with randomized encoding strategies.>

IEEE Transactions on Information Theory•Jan 1, 1991•34 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

Secure Identification for Wiretap Channels; Robustness, Super-Additivity and Continuity

Holger Boche, Christian Deppe

We determine the identification capacity of compound channels in the presence of a wiretapper. It turns out that the secure identification capacity formula fulfills a dichotomy theorem: It is positive and equals the identification capacity of the channel if its message transmission secrecy capacity is positive. Otherwise, the secure identification capacity is zero. Thus, we show in the case that the secure identification capacity is greater than zero we do not pay a price for secure identification, i.e., the secure identification capacity is equal to the identification capacity. This is in strong contrast to the transmission capacity of the compound wiretap channel. We then use this characterization to investigate the analytic behavior of the secure identification capacity. In particular, it is practically relevant to investigate its continuity behavior as a function of the channels. We completely characterize this continuity behavior. We analyze the (dis-) continuity and (super-) additivity of the capacities. In 1998, N. Alon gave a conjecture about maximal violation for the additivity of capacity functions in graphs. We show that this maximal violation as well holds for the secure identification capacity of compound wiretap channels. This is the first example of a capacity function exhibiting this behavior.

IEEE Transactions on Information Forensics and Security•Jan 23, 2018•65 citations

Super-Activation as a Unique Feature of Secure Communication over Arbitrarily Varying Channels

Rafael F. Schaefer, Holger Boche, H. Vincent Poor

The question of whether the capacity of a channel is additive or not goes back to Shannon, who asked this for the zero-error capacity function. Despite the common sense that the capacity is usually additive, there is surprisingly little known for non-trivial channels. This chapter addresses this question for the arbitrarily varying wiretap channel (AVWC), which models secure communication in the presence of arbitrarily varying channel (AVC) conditions. For orthogonal AVWCs it has been shown that the strongest form of non-additivity occurs: the phenomenon of super-activation. That is, there are orthogonal AVWCs, each having zero secrecy capacity, which allow for transmission with positive rate if they are used together. Subsequently, the single-user AVC is studied and it is shown that in this case, super-activation for non-secure message transmission is not possible, making it a unique feature of secure communication over AVWCs. However, the capacity for message transmission of the single-user AVC is shown to be super-additive, including a complete characterization. Super-activation was known for a long time in the area of quantum communication, where it is common opinion that this is solely a phenomenon of quantum physics and that this cannot occur for classical communication. However, the results in this chapter show that super-activation is indeed a feature of secure communication and therewith occurs in classical, non-quantum, communication as well. Introduction Information theory goes back to Shannon's seminal work “A Mathematical Theory of Communication” [1]. Since then it has been proven to be an indispensable concept for analyzing complex communication systems to obtain insights and optimal design criteria. Among many things, it is used to address the important issue of medium access control: How should available resources be divided among multiple users in the best possible way? This is a crucial question, especially for wireless communication systems since they are usually composed of orthogonal sub-systems such as those that arise via time division multiplexing (TDM) or orthogonal frequency division multiplexing (OFDM). Of particular interest then is to know how the capacity of the overall system depends on the orthogonal sub-systems. Common sense tells us that for such systems it should be given by the sum of the capacities of all sub-systems. This goes along with the inherent world view of the additivity of classical resources.

Cambridge University Press eBooks•Jun 16, 2017•0 citations
The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not, and the identification-feedback (IDF) capacity of channels with feedback is studied. The IDF capacity is shown to be discontinuous and super-additive for both deterministic and randomized encoding. For the deterministic IDF capacity the phenomenon of super-activation occurs, which is the strongest form of super-additivity. For the randomized IDF capacity, super-activation is not possible. These findings imply that the IDF capacity is not Turing computable.
The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not. Identification via correlation-assisted discrete memoryless channels is studied, where the transmitter and the receiver further have access to correlated source observations. Analytical properties and representations of the corresponding identification capacity are studied. In this paper, it is shown that the identification capacity cannot be represented as a maximization of a single-letter (or multi-letter with fixed length) expression of entropic quantities. Further, it is shown that the identification capacity is not Banach-Mazur computable and therewith not Turing computable. Consequently, there is no algorithm that can simulate or compute the identification capacity, even if there are no limitations on computational complexity and computing power.
For the case of complete feedback, a fairly unified theory of identification is presented. Its guiding principle is the discovery that communicators (sender and receiver) must set up a common random experiment with maximal entropy and use it as randomization for a suitable identification technique. It is shown how this can be done in a constructive manner. The proof of optimality (weak converse) is based on a novel entropy bound, which can be viewed as a substitute for Fano's lemma in the present context. The single-letter characterization of (second-order) capacity regions now rests on an entropy characterization problem, which often can be solved. This is done for the multiple-access channel with deterministic encoding strategies, and for the broadcast channel with randomized encoding strategies.>
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.
We determine the identification capacity of compound channels in the presence of a wiretapper. It turns out that the secure identification capacity formula fulfills a dichotomy theorem: It is positive and equals the identification capacity of the channel if its message transmission secrecy capacity is positive. Otherwise, the secure identification capacity is zero. Thus, we show in the case that the secure identification capacity is greater than zero we do not pay a price for secure identification, i.e., the secure identification capacity is equal to the identification capacity. This is in strong contrast to the transmission capacity of the compound wiretap channel. We then use this characterization to investigate the analytic behavior of the secure identification capacity. In particular, it is practically relevant to investigate its continuity behavior as a function of the channels. We completely characterize this continuity behavior. We analyze the (dis-) continuity and (super-) additivity of the capacities. In 1998, N. Alon gave a conjecture about maximal violation for the additivity of capacity functions in graphs. We show that this maximal violation as well holds for the secure identification capacity of compound wiretap channels. This is the first example of a capacity function exhibiting this behavior.
The question of whether the capacity of a channel is additive or not goes back to Shannon, who asked this for the zero-error capacity function. Despite the common sense that the capacity is usually additive, there is surprisingly little known for non-trivial channels. This chapter addresses this question for the arbitrarily varying wiretap channel (AVWC), which models secure communication in the presence of arbitrarily varying channel (AVC) conditions. For orthogonal AVWCs it has been shown that the strongest form of non-additivity occurs: the phenomenon of super-activation. That is, there are orthogonal AVWCs, each having zero secrecy capacity, which allow for transmission with positive rate if they are used together. Subsequently, the single-user AVC is studied and it is shown that in this case, super-activation for non-secure message transmission is not possible, making it a unique feature of secure communication over AVWCs. However, the capacity for message transmission of the single-user AVC is shown to be super-additive, including a complete characterization. Super-activation was known for a long time in the area of quantum communication, where it is common opinion that this is solely a phenomenon of quantum physics and that this cannot occur for classical communication. However, the results in this chapter show that super-activation is indeed a feature of secure communication and therewith occurs in classical, non-quantum, communication as well. Introduction Information theory goes back to Shannon's seminal work “A Mathematical Theory of Communication” [1]. Since then it has been proven to be an indispensable concept for analyzing complex communication systems to obtain insights and optimal design criteria. Among many things, it is used to address the important issue of medium access control: How should available resources be divided among multiple users in the best possible way? This is a crucial question, especially for wireless communication systems since they are usually composed of orthogonal sub-systems such as those that arise via time division multiplexing (TDM) or orthogonal frequency division multiplexing (OFDM). Of particular interest then is to know how the capacity of the overall system depends on the orthogonal sub-systems. Common sense tells us that for such systems it should be given by the sum of the capacities of all sub-systems. This goes along with the inherent world view of the additivity of classical resources.