We derive universal classical-quantum superposition coding and universal classical-quantum multiple access channel code by using generalized packing lemmas for the type method. Using our classical-quantum universal superposition code, we establish the capacity region of a classical-quantum compound broadcast channel with degraded message sets. Our universal classical-quantum multiple access channel codes have two types of codes. One is a code with joint decoding and the other is a code with separate decoding. The former universally achieves corner points of the capacity region and the latter universally achieves general points of the capacity region. Combining the latter universal code with the existing result by Quantum Inf Process. 18, 246 (2019), we establish a single-letterized formula for the capacity region of a classical-quantum compound multiple access channel.

We derive universal classical-quantum superposition coding and universal classical-quantum multiple access channel code by using generalized packing lemmas for the type method. Using our classical-quantum universal superposition code, we establish the capacity region of a classical-quantum compound broadcast channel with degraded message sets. Our universal classical-quantum multiple access channel codes have two types of codes. One is a code with joint decoding and the other is a code with separate decoding. It is not so easy to construct a former code that universally achieves general points of the capacity region beyond corner points. First, we construct the latter code that universally achieves general points of the capacity region. Then, converting the latter code to the former code, we construct the above desired code with the former type. A full version of this paper is accessible at http://arxiv.org/abs/2011.00410

When there exists a malicious attacker in the network, we need to be careful of eavesdropping and contamination. This problem is crucial for network communication when the network is realized by a partially trusted relay of quantum key distribution. We discuss the asymptotic rate in a linear network with the secrecy and robustness conditions when the above type of attacker exists. Also, under the same setting, we discuss the asymptotic rate in a linear network when we impose the secrecy condition alone.

In secure network coding, there is a possibility that the eavesdropper can improve her performance when she changes (contaminates) the information on the attacked edges (active attack) and chooses the attacked edges adaptively (adaptive attack). We analyze the security for network code over such types of attacks. We show that active and adaptive attacks cannot improve the performance of the eavesdropper when the code is linear. Further, we give a non-linear example, in which an adaptive attack improves the performance of the eavesdropper. We derive the capacity for the unicast case and the capacity region for the multicast case or the multiple multicast case in several examples of relay networks, beyond the minimum cut theorem, when no additional random number is allowed as scramble variables in the intermediate nodes. No prior study compared the difference of the capacity and the capacity region between the existence and the non-existence of randomness in the intermediate nodes under these network models even with non-adaptive and non-active attacks.

In the proof of Theorem 5, we stated that Eq. (47) follows fromEq. (59)ofLemma 4. However, the derivation ofEq. (59)is incorrect, and the inequality used in the derivation of Eq. (47) is notEq. (59). Eq. (47) follows from another inequality. This correction fixes the error of our derivation of Eq. (47).

In this paper we analyze the capacity of a special model for arbitrarily varying classical-quantum channels when the sender and the receiver use a weak resource. In this model a jammer has side information about the channel input. We determine the correlation assisted capacity. As an application, we determine the correlation assisted common randomness capacity with informed jammer. We also analyze these both capacities when only a small amount of correlation is available.

Based on Arimoto's work in 1978 [1], we propose an iterative algorithm for computing the capacity of a discrete memoryless classical-quantum channel with a finite input alphabet and a finite dimensional output, which we call the Blahut-Arimoto algorithm for classical-quantum channel, and an input cost constraint is considered. We show that to reach ε accuracy, the iteration complexity of the algorithm is up bounded by log n log ε ε where n is the size of the input alphabet. In particular, when the output state {ρx}x∈Xis linearly independent in complex matrix space, the algorithm has a geometric convergence. We also show that the algorithm reaches an ε accurate solution with a complexity of O(m3log n log ε/ε), and O(m3log ε log(1-δ)D(ε/p*||pN(0))) in the special case, where m is the output dimension and D(p*||pN(0)) is the relative entropy of two distributions and δ is a positive number.

We consider a unicast network with an adversary who is able to attack a proportion of edges, which is no more than p for some 0 <; p <; 1. Based on the knowledge of the adversary, three cases of attacks are considered: 1) the adversary knows nothing about the source message; 2) the adversary knows the source message but does not know the transmitted codeword; and 3) the adversary knows the transmitted codeword. Two classes of code schemes, deterministic code and stochastic code, are designed to assure reliable transmission against the adversarial attack. It is concluded that stochastic code does not provide any more benefit than the deterministic code does against the attacking cases 1 and 3. However, when the attacking case 2 is considered, stochastic code would achieve a higher capacity than the deterministic code does.

In this paper, a new model for arbitrarily varying classical-quantum channels is proposed. In this model, a jammer has side information. The communication scenario in which a jammer can select only classical inputs as a jamming sequence is considered in the first part of the paper. This situation corresponds to the standard model of arbitrarily varying classical-quantum channels. Two scenarios are considered. In the first scenario, the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. The capacity for both average and maximum error criteria for both scenarios is determined in this paper. A strong converse is also proved. It is shown that all these corresponding capacities are equal, which means that additionally revealing the message to the jammer does not change the capacity. The communication scenario with a fully quantum jammer is considered in the second part of the paper. A single letter characterization for the capacity with secret random key as assistance for both average and maximum error criteria is derived in the paper.

In this paper we propose a new model for arbitrarily varying classical-quantum channels. In this model a jammer has side information. We consider two scenarios. In the first scenario the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. We determine the capacity for both average and maximum error criteria. We prove that additionally revealing the message to the jammer does not change the capacity.

We consider a unicast network with an adversary who is able to attack a proportion of edges, which is no more than p for 0 <; p <; 1. Based on the knowledge of the adversary, three cases of attacks are considered: 1) the adversary knows nothing about the source message; 2) the adversary knows the source message but does not know the transmitted codeword; 3) the adversary knows the transmitted codeword. Two classes of code schemes, deterministic code and stochastic code, are designed to assure reliable transmission against the adversarial attack. It is concluded that stochastic code does not provide any more benefit than the deterministic code against the attacking cases 1 and 3. However, when the attacking case 2 is considered, stochastic code would achieve a higher capacity than the deterministic code.

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory.

In the network coding, we discuss the effect by sequential error injection to information leakage. We show that there is no improvement when the network is composed of linear operations. However, when the network contains non-linear operations, we find a counterexample to improve Eve's obtained information. Further, we discuss the asymptotic rate in the linear network under the secrecy and robustness conditions.

We study an analog of the well-known Gel'fand Pinsker Channel which uses quantum states for transmission of data. We consider the case where both the sender's inputs to the channel and the channel states are elements of a finite set (cq-channel with state information at the sender). While the receiver has no information about the channel states, we distinguish between two cases at the sender: he either gets causal or non-causal channel state information. We give a single-letter description of the capacity in the first case and present two different regularized expressions of the capacity for the second. It turns out that the change from causal to non-causal channel state information at the encoder causes the complexity of numerical computation of the capacity formula to change from simple to seemingly difficult. Still, even in the difficult non-causal case we draw nontrivial conclusions, for example regarding continuity of the capacity with respect to changes in the system parameters.

This paper considers an extension of wiretap channel II, where the source message W is transmitted to the legitimate receiver via a discrete memoryless main channel (DMC). Receiving YN, the receiver needs to recover W with small error probability. Meanwhile, an eavesdropper is able to observe arbitrary subsequence of YNwith size μ = Nα, where 0 <; α <; 1 is a constant real number. The encoding-decoding scheme is designed to satisfy a strong secrecy criterion, i.e. the information of each block (instead of each bit) exposed to the eavesdropper is negligible or arbitrarily close to 0 when N is sufficiently large. We focus on the secrecy capacity of this model.

In a recent work, S. Nitinawarat obtained a lower bound and an upper bound for the minimum list size in list decoding for an arbitrarily varying multiple access channel (AVMAC), for which the interior of the capacity region of deterministic list codes is nonempty. In the same paper, he proved that for a binary AVMAC, the minimum list size is finite, if and only if the interior of the capacity region of random correlated codes is nonempty. The goal of this paper is to close the gap between the two bounds for the minimum list size. We find a necessary and sufficient condition for the list codes for an AVMAC to have a capacity region with a nonempty interior in terms of bipartite graphs. Therefore, we determine the minimum list size. Moreover, we prove that for any AVMAC, the minimum list size is finite, if and only if the interior of the capacity region of random correlated codes is nonempty.

The zero error capacity of a channel is defined as the least upper bound of rates at which it is possible to transmit information with zero probability of error. Unsolved cases are addressed in this paper to complement the table of the zero error capacity of noisy binary channels with 1-memory. All cases are classified according to the isomorphic property of their confusability graphs, and then we determine the zero error capacity of the rest binary channels with 1-memory one by one.

This paper studies the problem of secret-message transmission over a wiretap channel with correlated sources in the presence of an eavesdropper who has no source observation. A coding scheme is proposed based on a careful combination of 1) Wyner-Ziv's source coding to generate secret key from correlated sources based on a certain cost on the channel, 2) one-time pad to secure messages without additional cost, and 3) Wyner's secrecy coding to achieve secrecy based on the advantage of legitimate receiver's channel over the eavesdropper's. The work sheds light on optimal strategies for practical code design for secure communication/storage systems.

This paper studies amplify‐and‐forward (AF) relaying schemes for layered relay networks. The design of the network‐wide optimal AF scheme in terms of maximum end‐to‐end transmission rate is mathematically formulated as a non‐convex optimisation problem which is computationally intractable in general. Therefore, the authors restrict it to a localised optimisation problem and develop a second‐order cone programming‐based approach to efficiently solve it, which yields localised optimal AF schemes for the relays at a specific layer. To improve the performance of a given network‐wide AF scheme, a low‐complexity alternating algorithm is proposed based on the localised optimisation technique. To reduce the computational complexity, they also derive localised suboptimal schemes in closed form. With relays at one layer applying this scheme and the other relays transmitting with the maximum allowable powers, a simple network‐wide AF scheme is derived, which is proved to be asymptotically optimal in the generalised high‐SNR regime. Finally, simulations are used to illustrate the validity of the proposed schemes.

We consider an Adaptive Random Convolutional Network Coding (ARCNC) algorithm to address the issue of field size in random network coding for multicast, and study its memory and decoding delay performances through both analysis and numerical simulations. ARCNC operates as a convolutional code, with the coefficients of local encoding kernels chosen randomly over a small finite field. The cardinality of local encoding kernels increases with time until the global encoding kernel matrices at the related sink nodes have full rank. ARCNC adapts to unknown network topologies without prior knowledge, by locally incrementing the dimensionality of the convolutional code. Because convolutional codes of different constraint lengths can coexist in different portions of the network, reductions in decoding delay and memory overheads can be achieved. We show that this method performs no worse than block linear network codes in terms of decodability, and can provide significant gains in terms of average decoding delay or memory in combination, shuttle and random geometric networks.

We determine the capacity of the classical compound quantum wiretapper channel with channel state information at the transmitter. Moreover we derive a lower bound on the capacity of this channel without channel state information and determine the capacity of the classical quantum compound wiretap channel with channel state information at the transmitter.

We propose an efficient Adaptive Random Convolutional Network Coding (ARCNC) algorithm to address the issue of field size in random network coding. ARCNC operates as a convolutional code, with the coefficients of local encoding kernels chosen randomly over a small finite field. The lengths of local encoding kernels increase with time until the global encoding kernel matrices at related sink nodes all have full rank. Instead of estimating the necessary field size a priori, ARCNC operates in a small finite field. It adapts to unknown network topologies without prior knowledge, by locally incrementing the dimensionality of the convolutional code. Because convolutional codes of different constraint lengths can coexist in different portions of the network, reductions in decoding delay and memory overheads can be achieved with ARCNC.We show through analysis that this method performs no worse than random linear network codes in general networks, and can provide significant gains in terms of average decoding delay in combination networks.

In a recent paper [4], Maríc et al. analyzed the performance of the analog network coding (ANC) in a layered relay network for the high-SNR regime. They have proved that under the ANC scheme, if each relay transmits the received signals at the upper bound of the power constraint, the transmission rate will approach the network capacity. In this paper, we consider a more general scenario defined as the generalized high-SNR regime, where the relays at layer l in a layered relay network with L layers do not satisfy the high-SNR conditions, and then determine an ANC relay scheme in such network. By relating the received SNR at the nodes with the propagated noise, we derive the rate achievable by the ANC scheme proposed in this paper. The result shows that the achievable ANC rate approaches the upper bound of the ANC capacity as the received powers at relays in high SNR increase. A comparison of the two ANC schemes implies that the scheme proposed in [4] may not always be the optimal one in the generalized high-SNR regime. The result also demonstrates that the upper and lower bounds of the ANC rate coincide in the limit as the number of relays at layer L-1 dissatisfying the high-SNR conditions tends to infinity (to be infinite), yielding an asymptotic capacity result.

In this tutorial paper, we focus on the basic theory of linear secure network coding. Our goal is to present fundamental results and provide preliminary knowledge for anyone interested in the area. We first present a model for secure network coding and then a necessary and sufficient condition for a linear network code to be secure. Optimal methods to construct linear secure network codes are also provided. For further investigation of the secure properties of linear network codes, we illuminate different secure criteria and requirements, with a few alternative models.

In the paradigm of network coding, the nodes in a network are allowed to encode the information received from the input links. With network coding, the full capacity of the network can be utilized. In this paper, we propose a model, call the wiretap network, that incorporates information security with network coding. In this model, a collection of subsets of the channels in the network is given, and a wiretapper is allowed to access any one (but not more than one) of these subsets without being able to obtain any information about the message transmitted. Our model includes secret sharing in classical cryptography as a special case. We present a construction of secure linear network codes that can be used provided a certain graph-theoretic condition is satisfied. We also prove the necessity of this condition for the special case that the wiretapper may choose to access any subset of channels of a fixed size. The optimality of our code construction is established for this special case. Finally, we extend our results to the scenario when the wiretapper is allowed to obtain a controlled amount of information about the message.

A condition governing the possibility and impossibility of linear independence among the global encoding kernels of a linear network code is found. Based on this condition, we propose several alternative definitions of generic network codes, which give interpretations of such codes from different perspectives. We also present a unified framework for specifying and constructing different classes of linear network codes. Finally, using the insight obtained from the unified framework, we show that the proofs of some existing results regarding generic network codes can be greatly simplified.

The arbitrarily varying channel can be modeled as communication in the presence of a jammer. In this paper we propose a new model: a jammer who knows the channel input, and where the transmitter and receiver share a secret random key. Shared randomness differentiates this scenario from the case where the jammer knows the message. For sufficiently large key rate, we determine the capacity of this channel (which may be strictly smaller than the case where the jammer knows only the message). We also provide an upper bound on the minimum key rate required to achieve capacity. We prove that additionally revealing the message to the jammer does not change the capacity, provided the key rate is sufficiently large. This new capacity result differs from existing results for the AVC, and in fact coincides with a well-known upper bound on the deterministic coding capacity of the AVC with maximum error. Without secret keys, our problem degenerates to deterministic coding for the AVC with maximum probability of error, a well-known hard problem. Our results demonstrate that knowledge of the channel input is better than knowledge of the message for the jammer.

This paper considers a key agreement problem in which two parties aim to agree on a key by exchanging messages in the presence of adversarial tampering. The aim of the adversary is to disrupt the key agreement process, but there are no secrecy constraints (i.e. we do not insist that the key is kept secret from the adversary). The main results of the paper are coding schemes and bounds on maximum key generation rates for this problem.

We introduce the continuous time asynchronous channel as a model for time jitter in a communication system with no common clock between the transmitter and the receiver. We have obtained a simple characterization for an optimal zero-error self-synchronizable code for the asynchronous channel. The capacity of this channel is determined by both a combinatorial approach and a probabilistic approach. Our results unveil the somewhat surprising fact that it is not necessary for the receiver clock to resynchronize with the transmitter clock within a fixed maximum time in order to achieve reliable communication. This means that no upper limit should be imposed on the run lengths of the self-synchronization code as in the case of run-length limited (RLL) codes which are commonly used in magnetic recording.

In this paper, we prove the optimality of a secure network code we have previously constructed when the wiretapper can choose to access any subset of the channels of a fixed size. Specifically, we prove that the network code we constructed multicasts the maximum possible amount of information to the user nodes securely and uses the minimum amount of randomness to achieve the required security.

We obtain a necessary and sufficient condition for the security of multi-source linear network codes by studying the algebraic structure of such codes. This condition is useful for analyzing the security of such linear network codes, and it applies in cases when the random keys do not necessarily have uniform distributions. This condition also shows that the security of a linear network code does not depend on the source distribution.

After Ahlswede introduced identification for source coding he discovered identification entropy and demonstrated that it plays a role analogously to classical entropy in Shannon's noiseless source coding. We give now even more insight into this functional interpreting its two factors.

This paper extends the part of the theory on linear network coding (S.-Y.R. Li et al., 2003) over an acyclic network. The extension also applies to "static linear network code" that is introduced by R. Koetter and M. Medard, (2003). Another objective is the rigorous clarification of fundamental concepts in linear network coding

After K. Bostro/spl uml/m and T. Felbinger observed that lossless quantum data compression does not exist unless decoders know the lengths of codewords, they introduced a classical noiseless channel to inform the decoder of a quantum source about the lengths of codewords. In this paper we analyze their codes and present: 1) a sufficient and necessary condition for the existence of such codes for given lists of lengths of codes; 2) a characterization of the optimal compression rate for their codes. However our main contribution is a more efficient way to use the classical channel. We propose a more general coding scheme. It turned out that the optimal compression can always be achieved by a code obtained by this scheme. A von Neumann entropy lower bound to rates of our codes and a necessary and sufficient condition to achieve the bound are obtained. The gap between this lower bound and the compression rates is also well analyzed. For a special family of quantum sources we provide a sharper lower bound in terms of Shannon entropy. Finally, we propose some problems for further research.

Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.

We introduce network error-correcting codes for error correction when a source message is transmitted to a set of receiving nodes on a network. The usual approach in existing networks, namely link-by-link error correction, is a special case of network error correction. The network generalizations of the Hamming bound and the Gilbert-Varshamov bound are derived.

We introduce the concept of "parallel error correcting" codes, the error correcting codes for parallel channels. Here, a parallel channel is a set of channels such that the additive error over a finite field occurs in one of its members at time T if the same error occurs in all members at the same time. The set of codewords of a parallel error correcting code has to be a product set, if the messages transmitted are from independent information sources. We present a simple construction of optimal parallel error correcting codes based on ordinary optimal error correcting codes and a construction of optimal linear parallel codes for independent sources based on optimal ordinary linear error correcting codes. The decoding algorithms for these codes are provided as well.

Whereas the average error capacity region R/sub a/ for the multiple-access channel (MAC) W: X /spl times/ Y /spl rarr/ Z has been known for a long time, very little is known about the capacity region R/sub m/ for the maximal error concept (as predicted by Ahlswede in 1971). In spite of great efforts during the past three decades even for some special examples of deterministic MAC, for which the maximal error concept coincides with the concept of unique decodability, the progress has been slow. It is known that the permission of list codes can be of great help, even if list sizes are of negligible rates (cf. the arbitrarily varying channel (AVC) and, especially, Shannon's (1948) zero-error capacity problem for the one-way channels). Therefore, it is theoretically appealing to look at their regions R/sub m,l/ for the MAC. For a nice class of deterministic MAC, which we call "seminoisy," we completely characterized R/sub m,l/. For these channels, the Y-input is determined uniquely by the output. Dueck's (1978) example with R/sub a/ /spl ne/ R/sub m/ and Vanroose's (1988) "noiseless binary switching MAC" with R/sub a/ = R/sub m/ fall into this class. Finally, for this class, the capacity region R/sub m,f/, which concerns complete feedback, equals R/sub m,l/.

We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. We study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the max-flow min-cut theorem for network information flow. Contrary to one's intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a "fluid" which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems.

In 1981 Jahn used the elimination technique of the first author to determine the average errors capacity region of an arbitrarily varying multiple-access channel (AVMAC), when this region has a nonempty interior. Here we remove this restriction. In his thesis (1990), Gubner (1990) missed this result because he used the first author's first approach to the MAC, which is based on conditional decoding, and not the first author's second approach, which is based on maximum likelihood decoding. This second approach was originally needed for a kind of compound MAC. For the AVMBC the difference between the approaches is naturally even more essential.

For pt.I see ibid., vol.45, no.2, p.742-9 (1999). We consider an arbitrarily varying multiple-access channel (AVMAC) W which the two senders x and y observe, respectively, the components K/sup m/ and L/sup m/ of a memoryless correlated source (MCS) {(K/sup m/, L/sup m/)}/sub m//sup /spl infin//=1 with generic rv's (K, L). In part I of this work, it has been shown for the AVMAC without the MCS that in order for the achievable rate region for deterministic codes and the average probability of error criterion to be nonempty, it was sufficient if the AVC were x nonsymmetrizable, y nonsymmetrizable, and xy nonsymmetrizable. (The necessity of these conditions had been shown earlier by Gubner (1990).) Let R/sub R/(W) denote the random code achievable rate region of the AVMAC W. In the present paper, the authors, in effect, trade the loss in achievable rates due to symmetrizability off the gains provided by the MCS. Let R(W, (K, L)) represent the achievable rate region of the AVC W with MCS, for deterministic codes and the average probability of error criterion. There are two main results: (1) if I(K/spl and/L)>0, then R(W, (K, L)) has a nonempty interior iff R/sub R/(W) does too and W is xy nonsymmetrizable; and (2) if I(K/spl and/L)>0, H(K|L)>0,H(L|K)>0 then the MCS can be transmitted over the AVMAC iff R/sub R/(W) has a nonempty interior and W is xy nonsymmetrizable.

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.

The transmission problem for noisy channels is usually studied under the condition that the decoding error probability /spl lambda/ is small and is sometimes studied under the condition that /spl lambda/=0. Here we just require that /spl lambda/<1 and obtain a problem which is equivalent to a coding problem with small /spl lambda/ for the "deterministic matching channel." In this new model, a cooperative person knows the codeword to be sent and can choose (match) the state sequence of the channel. There are interesting connections to combinatorial matching theory and extensions to the theory of identification as well as to multi-way channels. In particular, there is a surprising connection to Pinsker's (1978) coding theorem for the deterministic broadcast channel.

We present a general class of zero-error capacity problems with memory covering known cases such as coding for error correction and many new cases. This class can be incorporated into a model of channels with memory, which thus are shown to give a unification of a multitude of seemingly very different coding problems. We analyze a seemingly basic channel in this class.

It is well known that the deterministic code capacity (for the average error probability criterion) of an arbitrarily varying channel (AVC) either equals its random code capacity or zero. Here it is shown that if two components of a correlated source are additionally available to the sender and receiver, respectively, the capacity always equals its random code capacity.

Ahlswede has previously introduced an abstract correlated source (/spl Vscr//spl times//spl Wscr/,S) with outputs (/spl upsi/, /spl omega/)/spl isin/S/spl sub//spl Vscr//spl times//spl Wscr/, where persons P/sub /spl Vscr// and P/sub /spl Wscr// observe /spl upsi/ and /spl omega/, respectively. More recently, Orlitsky considered the minimal number C/sub m/ of bits to be transmitted in m rounds to "inform P/sub /spl Wscr// about /spl upsi/ over one channel." He showed that C/sub 2//spl les/4C/sub /spl infin//+3 and that in general C/sub 2/NOT/spl sim/C/sub /spl infin//. We give a simple example for C/sub 3/NOT/spl sim/C/sub /spl infin//. However, for the new model "inform P/sub /spl Wscr// over two channels", four rounds are optimal for this example-a result we conjecture in general. If both P/sub /spl Vscr// and P/sub /spl Wscr// are to be informed over two channels about the other outcome, we determine asymptotically the complexities for all sources. In our last model "inform P/sub /spl Vscr// and P/sub /spl Wscr// over one channel" for all sources the total number T/sub 2/ of required bits is known asymptotically and T/sub /spl infin// is bounded from below in terms of average degrees. There are exact results for several classes of regular sources. An attempt is made to discuss the methods of the subject systematically.

For the discrete memoryless channel (/spl chi/, y, W) we give characterizations of the zero-error erasure capacity C/sub er/ and the zero-error average list size capacity C/sub al/ in terms of limits of suitable information (respectively, divergence) quantities (Theorem 1). However, they do not "single-letterize." Next we assume that /spl chi//spl sub/y and W(x|x)>0 for all x/spl isin//spl chi/, and we associate with W the low-noise channel W/sub /spl epsiv//, where for y/sup +/(x)={y:W(y|x)>0} W/sub /spl epsiv//(y|x)={1, if y=x and |y/sup +/(x)|=1 1-/spl epsiv/, if y=x and |y/sup +/(x)|>1 e/|y/sup +/(x)|-1, if y/spl ne/x. Our Theorem-2 says that as /spl epsi/ tends to zero the capacities C/sub er/(W/sub /spl epsi//) and C/sub al/(W/sub /spl epsi//) relate to the zero-error detection capacity C/sub de/(W). Our third result is a seemingly basic contribution to the theory of identification via channels. We introduce the (second-order) identification capacity C/sub oid/ for identification codes with zero misrejection probability and misacceptance probability tending to zero. Our Theorem 3 says that C/sub oid/ equals the zero-error erasure capacity for transmission C/sub er/.

New upper and lower bounds on the two-way communication complexity of abstract functions g:/spl Hscr//spl times//spl Yscr//spl rarr//spl Zscr/ give tight bounds, when applied to vector-valued functions f/sup n/(f/sub 1/,...,f/sub n/):/spl Hscr//sup u//spl times//spl Yscr//sup n//spl rarr//spl Zscr//sup n/, if the alphabets are small. For the set-intersection function, an optimal protocol is presented. It is based on a simple new idea applicable also to abstract functions. The two-way communication complexities of all other Boolean functions are also determined. The results are extended to meets in abstract lattices and to a probabilistic model.>

M.S. Pinsker (1990) conjectured the following theorem: for an arbitrary varying channel (AVC), every rate below the random code capacity is achievable with deterministic list codes of constant list size, if the average error criterion is used. Two proofs of this theorem are given.>