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.
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.
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.
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 study entanglement-assisted quantum and classical communication over a single use of a quantum channel, which itself can correspond to a finite number of uses of a channel with arbitrarily correlated noise. We obtain characterizations of the corresponding one-shot capacities by establishing upper and lower bounds on them in terms of the difference of two smoothed entropic quantities. In the case of a memoryless channel, the upper and lower bounds converge to the known single-letter formulas for the corresponding capacities, in the limit of asymptotically many uses of it. Our results imply that the difference of two smoothed entropic quantities characterizing the one-shot entanglement-assisted capacities serves as a one-shot analog of the mutual information, since it reduces to the mutual information, between the output of the channel and a system purifying its input, in the asymptotic, memoryless scenario.
The non-signaling (NS) assisted capacity of a classical discrete memoryless channel with causal channel state information at the transmitter (CSIT) is shown to be CNS,ca=maxPX∣SI(X;Y∣S), where X,Y,S correspond to the input, output and state of the channel. Remarkably, this is the same as the capacity of the channel in the NS-assisted non-causal CSIT setting, CNS,nc=maxPX∣SI(X;Y∣S), which was previously established, and also matches the (either classical or with NS assistance) capacity of the channel where the state is available not only (either causally or non-causally) to the transmitter but also to the receiver. While the capacity remains unchanged, the optimal probability of error for fixed message size and blocklength, in the NS-assisted causal CSIT setting can be further improved if channel state is made available to the receiver. This is in contrast to corresponding NS-assisted non-causal CSIT setting where it was previously noted that the optimal probability of error cannot be further improved by providing the state to the receiver. As a separate result we prove that non-signaling assistance, feedback, and strictly causal CSIT (i.e., transmitter knows only past channel states but not the current or future states), each of which is individually already known to not increase capacity, also cannot increase capacity when they are collectively made available to the transmitter.
Classical identification via a noisy channel is a communication task in which the receiver is not required to reconstruct the full transmitted message, but only to decide whether it coincides with a message of interest. This relaxation allows the number of identifiable messages to grow doubly exponentially with the blocklength. For quantum channels, the resulting (doubly exponential) identification capacity CID can strictly exceed the ordinary (exponential) transmission capacity C.
In this paper, we prove that the entanglement-assisted transmission capacity CE is a strong converse bound for this task: CID≤CE. For sufficiently low-noise channels, this bound can also be achieved via the Hayden-Winter (quantum) identification + fingerprinting codes. This yields an exact characterization CID=CE of identification capacity for such channels. However, for general channels, we prove that this upper bound can be strict. We exhibit an explicit family of transpose-depolarizing channels for which CID<CE. As a consequence, we also obtain the first example of strict superadditivity of the identification capacity CID.
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.