Motivated by iterative decoding techniques for the binary erasure channel Hollmann and Tolhuizen introduced and studied the notion of generic erasure correcting sets for linear codes. A generic (r,s)-erasure correcting set generates for all codes of codimensionra parity check matrix that allows iterative decoding of all correctable erasure patterns of sizesor less. The problem is to derive bounds on the minimum sizeF(r,s) of generic erasure correcting sets and to find constructions for such sets. In this paper, we continue the study of these sets. We derive better lower and upper bounds. Hollmann and Tolhuizen also introduced the stronger notion of (r,s)-sets and derived bounds for their minimum sizeG(r,s) . Here also we improve these bounds. We observe that these two conceps are closely related to so calleds-wise intersecting codes, an area, in whichG(r,s) has been studied primarily with respect to ratewise performance. We derive connections. Finally, we observed that hypergraph covering can be used for both problems to derive good upper bounds.

We consider two generalizations of group testing: threshold group testing (introduced by Damaschke [8]) and majority group testing (a further generalization, including threshold group testing and a model introduced by Lebedev [15]). We show that each separating code gives a nonadaptive strategy for threshold group testing for some parameters. This is a generalization of a results on "guessing secrets", introduce. We introduce threshold codes and show that each threshold code gives a nonadaptive strategy for threshold group testing. We show that there exist threshold codes such that we can improve the lower bound for the rate of threshold group testing. We consider majority group testing if the number of defective elements is unknown (otherwise it reduces to threshold group testing). We show that cover-free codes and separating codes give strategies for majority group testing. We give a lower bound for the rate of majority group testing.

We consider a generalization of group testing, which gets together majority group testing and group testing with density tests. In contrast to the classical goal of group testing we want to find m defective elements of D defective elements. We examine four different test functions. We give adaptive strategies and lower bounds for the number of tests. We treat the cases if the number of defectives are known and if the number of defectives are bounded or unknown.

A statistical database (SDB) is a database that is used to return statistical information derived from the records to user queries for statistical data analysis. Sometimes, by correlating enough statistics, confidential data (stored in an SDB) about an individual can be inferred. Examples of confidential information stored in an SDB might be salaries or data concerning the medical history of individuals. An important problem is to provide security to SDBs against the disclosure of confidential information. An SDB is said to be secure if no protected data can be inferred from the available queries. One of the security-control methods suggested in the literature consists of query restriction: the security problem is to limit the use of the SDB, introducing a control mechanism, such that no protected data can be obtained from the available queries. Chin and Ozsoyoglu [IEEE Trans. Software Engrg., 8 (1982), pp. 574–582] introduced a control mechanism, called AUDIT EXPERT, where only SUM queries, that is, only certain sums of individual records, are available for the users. This SUM query model leads to several challenging optimization problems. Assume there are n numeric records $\{z_1,\ldots,z_n\}$ stored in database. A natural problem is to maximize the number of answerable SUM queries, that is, the number of subset sums of $\{z_1,\ldots,z_n\}$ (possibly with some additional constraints), that can be returned, such that none of numbers $z_i$ (or sums of subsets of size not exceeding a specified number) can be inferred from these queries. In this paper we give tight bounds for this number under constraints on size and dimension of query subsets.

We derive a regularized formula for the common randomness assisted entanglement transmission capacity of finite arbitrarily varying quantum channels (AVQC's). For finite AVQC's with positive capacity for classical message transmission we show, by derandomization through classical forward communication, that the random capacity for entanglement transmission equals the deterministic capacity for entanglement transmission. This is a quantum version of the famous Ahlswede dichotomy. In the infinite case, we derive a similar result for certain classes of AVQC's. At last, we give two possible definitions of symmetrizability of an AVQC.

This paper discusses the theorem that channels with time structure has a capacity sequence.

The concept of oblivious transfer capacity has been introduced by Nascimento and Winter, ISIT06. Its value has been determined for certain models, and bounds to it were given for other models, in the present authors' ISIT07 contribution. This talk is based on the latter work. The tools include known results on secrecy capacity of simple source and channel models.

We consider the problem of searching for an unknown number in the search space U ={0,...,M-1}. q-ary questions can be asked and some of the answers may be wrong. An arbitrary integer weighted bipartite graph Gamma is given, stipulating the cost Gamma(i,j) of each answer jnei when the correct answer is i, i.e., the cost of a wrong answer. Correct answers are supposed to be cost-less. It is assumed that a maximum cost e for the sum of the cost of all wrong answers can be afforded by the responder during the whole search. We provide tight upper and lower bounds for the largest size M = M(q,e,Gamma,n) for which it is possible to find an unknown number x*isinU with n q-ary questions and maximum lie cost e. Our results improve the bounds of Cicalese et al. (2004) and Ahlswede et al. (2008). The questions in our strategies can be asked in two batches of nonadaptive questions. Finally, we remark that our results can be further generalized to a wider class of error models including also unidirectional errors.

We consider transmission of messages encoded into binary matrices to be send over a parallel asymmetric channel. Two different channel models are introduced. They depend on the conditions on errors in the subchannels. For each channel model codes are constructed for error correction and for error detection and bounds are derived.

The concept of oblivious transfer capacity has been recently introduced by Nascimento and Winter. We give an upper bound to this capacity, both for source and channel models, and prove that it is tight for a class of channels. For other cases, lower bounds are provided. The tools include known results on secrecy capacity of simple source and channel models.

We prove that the average error classical capacity C(W) of a classicalquantum arbitrarily varying channel (cq-AVC) W equals 0 or else the random code capacity C (Ahlswede's dichotomy). We also establish a necessary and sufficient condition for C(W)>0

Summary form only given: Recently Terence Tao approached Szemeredi's regularity lemma from the perspectives of probability theory and of information theory instead of graph theory and found a stronger variant of this lemma, which involves a new parameter. To pass from an entropy formulation to an expectation formulation he found the following lemma. Let Y, and X, X' be discrete random variables taking values in y and x, respectively, where y sub [-1, 1], and with X' = f(X) for a (deterministic) function f. Then we have E(|E(Y|X') - E(Y|X)|) les 2I(X nland Y|X')1/2. We show that the constant 2 can be improved to (2ln2)1/2and that this is the best possible constant

A statistical database (SDB) is a database that is used to provide statistical information (such as average, sums etc.), derived from the records, to user queries for statistical data analysis. Sometimes, by correlating enough statistics, protected data about an individual can be inferred. The security problem is to limit the use of the SDB such that only statistical information is available and no protected individual data can be obtained from the available queries. When users are able to infer protected information in the SDB from responses to queries, the SDB is said to be compromised. The goal is to maximize the number of available queries without compromise. One of the natural restrictions for the prevention of database compromise is to allow only SUM queries, that is, only certain sums of individual records are available for the users. In this paper we discuss security problems for databases where only SUM queries with certain constraints are allowed. Assume there are n numeric records {z1,..., zn} stored in a database. The problem is to find the largest number of subset sums of {z1,..., zn} (maybe with some other constraints) that can be disclosed such that none of numbers zi(or even sums of small subsets) can be determined from these sums. Some tight bounds for this number (under certain constraints on size and dimension of query subsets) are presented

We introduce and study error correcting codes for parallel synchronous communication via Z-channels. Constructions for error detecting/correcting codes are presented. More generally, we consider array codes for Z-channels

We prove that the average error capacity Cqof a quantum arbitrarily varying channel (QAVC) equals 0 or else the random code capacity lowbarC (Ahlswede's dichotomy). We also establish a necessary and sufficient condition for Cq> 0

The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors

In the last century together with Levon Khachatrian we established a diametric theorem in Hamming space Hn=(Xn,dH). Now we contribute a diametric theorem for such spaces, if they are endowed with the group structure Gn=nΣ1G, the direct sum of a group G on X={0,1,...,q-1}, and as candidates are considered subgroups of Gn. For all finite groups G, every permitted distance d, and all n≥d subgroups of Gnwith diameter d have maximal cardinality qd. Other extremal problems can also be studied in this setting.

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 describes Nowak's model for language evolution and settle a conjecture. The human language is used to store and transmit information. Therefore there is significant interest in the mathematical models of language development. These models explains the natural selection that can lead to the gradual emergence of human language.

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.

The paper discusses Conjecture 21 formulated by Ahlswede and Winter (see ibid., vol.48, p.569-79, Mar. 2002) about finite families of self-adjoint operators A/sub i/ and B/sub i/ noting that for commuting operators equality holds. It adds that the other statements made in connection with this conjecture, though not logically disproved, should be regarded with caution.

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 present a simple proof of the strong converse for identification via discrete memoryless quantum channels, based on a novel covering lemma. The new method is a generalization to quantum communication channels of Ahlswede's (1979, 1992) approach to classical channels. It involves a development of explicit large deviation estimates to the case of random variables taking values in self-adjoint operators on a Hilbert space. This theory is presented separately in an appendix, and we illustrate it by showing its application to quantum generalizations of classical hypergraph covering problems.

We prove a data processing inequality for quantum communication channels, which states that processing a received quantum state may never increase the mutual information between input and output states.

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.

A construction of uniquely decodable codes for the two-user binary adder channel is presented. The rates of the codes obtained by this construction are greater than the rates guaranteed by the Coebergh van den Braak and van Tilborg construction and these codes can be used with simple encoding and decoding procedures.

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.

For pt.I see ibid., vol.39, p.1121, 1993. The common randomness (CR) capacity of a two-terminal model is defined as the maximum rate of common randomness that the terminals can generate using resources specified by the given model. We determine CR capacity for several models, including those whose statistics depend on unknown parameters. The CR capacity is shown to be achievable robustly, by common randomness of nearly uniform distribution no matter what the unknown parameters are. Our CR capacity results are relevant for the problem of identification capacity, and also yield a new result on the regular (transmission) capacity of arbitrarily varying channels with feedback.

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.

In this paper we study universal coding problems for the integers, in particular, establish rather tight lower and upper bounds for the Elias omega code and other codes. In these bounds, the so-called log-star function plays a central role. Furthermore, we investigate unbounded search trees induced by these codes, including the Bentley-Yao search tree. We will reveal beautiful recursion structures latent in these search trees as well as in these codes. Finally, we introduce the modified log-star function to reveal the existance of better prefix codes than the Elias omega code and other known codes.

A new coding problem is introduced for a correlated source (X/sup n/,Y/sup n/)/sub n=1//sup /spl infin//. The observer of X/sup n/ can transmit data depending on X/sup n/ at a prescribed rate R. Based on these data the observer of Y/sup n/ tries to identify whether for some distortion measure /spl rho/ (like the Hamming distance) n/sup -1/ /spl rho/(X/sup n/,Y/sup n/)/spl les/d, a prescribed fidelity criterion. We investigate as functions of R and d the exponents of two error probabilities, the probabilities for misacceptance, and the probabilities for misrejection. In the case where X/sup n/ and Y/sup n/ are independent, we completely characterize the achievable region for the rate R and the exponents of two error probabilities; in the case where X/sup n/ and Y/sup n/ are correlated, we get some interesting partial results for the achievable region. During the process, we develop a new method for proving converses, which is called "the inherently typical subset lemma". This new method goes considerably beyond the "entropy characterization" the "image size characterization," and its extensions. It is conceivable that this new method has a strong impact on multiuser information theory.

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/.

Introduces probabilistic communication models with localized errors and determines the optimal rates of codes, if a priori error patterns or actual errors or both occur at random according to uniform distributions. There are strong connections to the theory of arbitrarily varying channels.>

Studies two problems in the theory of identification via channels. The first problem concerns the identification via channels with noisy feedback. Whereas for Shannon's transmission problem the capacity of a discrete memoryless channel does not change with feedback, it is known that the identification capacity is affected by feedback. The authors study its dependence on the feedback channel. They prove both, a direct and a converse coding theorem. Although a gap exists between the upper and lower bounds provided by these two theorems, the known result for channels without feedback and the known result for channels with complete feedback, are both special cases of these two new theorems, because in these cases the bounds coincide. The second problem is the identification via wiretap channels. A secrecy identification capacity is defined for the wiretap channel. A "dichotomy theorem" is proved which says that the second-order secrecy identification capacity is the same as Shannon's capacity for the main channel as long as the secrecy transmission capacity of the wiretap channel is not zero, and zero otherwise. Equivalently, one can say that the identification capacity is not lowered by the presence of a wiretapper as long as 1 bit can be transmitted (or identified) correctly with arbitrarily small error probability. This is in strong contrast to the case of transmission.>

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.>

Continuing earlier work (Ahlswede and Zhang, 1989) on write-efficient memories (WEM), the authors introduce new models, where several persons use the same storage device. At any time instant, exactly one of a prescribed set of users has access to the memory, but there is no protocol which determines the moving order. Among the constraints analyzed, the most interesting one is a complete privacy protection. While a user stores new data, he has to guarantee that those of the others do not get distorted. This leads to fascinating new coding problems. The authors provide several code constructions, as well as abstract performance bounds.>

The capacity of an arbitrarily varying channel (AVC) for list codes of arbitrarily small list rate under the maximal error criterion has previously been determined. The authors prove that for an AVC A, any rate R below the list code capacity C/sub 1/(A) is achievable with a particular list size dependent on A, R and Y, where Y is the output alphabet.>

A recursive construction of asymptotically dense codes correcting a constant number of localized errors is examined. The codes overcome difficulties for a particular case with an asymptotic Hamming bound in which the number of errors increases linearly with the length of codes. It is shown that this method is applicable to both binary and nonbinary cases.>

As the first part of a study of problems involving common randomness at distance locations, information-theoretic models of secret sharing (generating a common random key at two terminals, without letting an eavesdropper obtain information about this key) are considered. The concept of key-capacity is defined. Single-letter formulas of key-capacity are obtained for several models, and bounds to key-capacity are derived for other models.>

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.>

Arbitrarily varying channels have been introduced as a model for transmission in cases of jamming. It is shown that this theory applies naturally to memories and yields, in a unified way, some new and old capacity theorems for write-unidirectional memories with side information. The role of cycles via outputwise varying channels is discussed. Exact conditions for memories to have positive capacity in the long run are derived.>

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.>

An attempt is made to determine whether it is true that for a fixed distortion level Delta the rate-distortion function R(P, Delta ) has in the distribution P no local maxima with values different from the global maximum. It is shown that, in general, the answer is negative. However, the answer is positive for Hamming distortion measures. Moreover their R is Schur-concave.>

The authors' main finding is that any object among doubly exponentially many objects can be identified in blocklength n with arbitrarily small error probability via a discrete memoryless channel (DMC), if randomization can be used for the encoding procedure. A novel doubly exponential coding theorem is presented which determines the optimal R, that is, the identification capacity of the DMC as a function of its transmission probability matrix. This identification capacity is a well-known quantity, namely, Shannon's transmission capacity for the DMC.>

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.>

We give optimal coding strategies for nonprobabilistic permuting (especially, "trapdoor") channels and also for a permuting relay channel. Our results open the door to a coding theory for nonprobabilistic (or deterministic) channels with memory.

Witsenhausen's hyperbola bound for the multiple description problem without excess rate in case of a binary source is not tight for exact joint reproductions. However, this bound is tight for almost-exact joint reproductions (Theorem1, conjectured by Witsenhausen). The proof is based on an {\em approximative} form of the team guessing lemma for {\em sequences} of random variables. (This result may be of interest also for team guessing). The hyperbola bound is also tight for exact joint reproductions and arbitrarily small, but positive, excess rate (Theorem2). The proof of this result uses our covering lemma.

The capacity of the arbitrarily varying channels with states sequence known to the sender is determined. The result is obtained with the help of an elimination technique and a robustification technique. It demonstrates once more the power of these techniques.

A new class of statistical problems is introduced, involving the presence of communication constraints on remotely collected data. Bivariate hypothesis testing,H_{0}: P_{XY}againstH_{1}: P_{\={XY}}, is considered when the statistician has direct access toYdata but can be informed aboutXdata only at a preseribed finite rateR. For any fixed R the smallest achievable probability of an error of type2with the probability of an error of type1being at most\epsilonis shown to go to zero with an exponential rate not depending on\epsilonas the sample size goes to infinity. A single-letter formula for the exponent is given whenP_{\={XY}} = P_{X} \times P_{Y}(test against independence), and partial results are obtained for generalP_{\={XY}}. An application to a search problem of Chernoff is also given.

During recent years there has been strong interest in a certain source coding problem, which some authors call the "problem of multiple descriptions." Old and new wringing techniques enable us to establish a single-letter characterization of the rate-distortion region in the case of no excess rate for the joint description.

Winograd's result concerning Elias' model of computation in the presence of noise can be stated without reference to computation. If a code\varphi: \{0,1\}^{k} \rightarrow \{0,1\}^{n}is min-preserving(\varphi (a \wedge b) = \varphi (a) \wedge \varphi (b)fora,b \in \{0,1\}^{k})and\epsilon n-error correcting, then the ratek/n \rightarrow 0ask \rightarrow \infty. This result is improved and extended in two directions. \begin{enumerate} \item For min-preserving codes with {\em fixed} maximal (and also average) error probability on a binary symmetric channel againk/n \rightarrow 0ask \rightarrow \infty(strong converses). \item Second, codes with lattice properties without reference to computing are studied for their own sake. Already for monotone codes( \varphi (a) \leq \varphi (b)fora \leq b)the results in direction 1) hold for maximal errors. \end{enumerate} These results provide examples of coding theorems in which entropy plays no role, and they can be reconsidered from the viewpoint of multiuser information theory.

A simple proof of the coding theorem for the multiple-access channel (MAC) with arbitrarily correlated sources (DMCS) of Cover-El Carnal-Salehi, which includes the results of Ahlswede for the MAC and of Slepian-Wolf for the DMCS and the MAC as special cases, is first given. A coding theorem is introduced and established for another type of source-channel matching problem, i.e., a system of source coding with side information via a MAC, which can be regarded as an extension of the Ahlswede-Körner-Wyner type noiseless coding system. This result is extended to a more general system with several principal sources and several side information sources subject to cross observation at the encoders in the sense of Han. The regions are shown to be optimal in special situations. Dueck's example shows that this is in general not the case for the result of Cover-El Gamal-Salehi and the present work. In another direction, the achievable rate region for the module-two sum source network found by Körner-Marton is improved. Finally, some ideas about a new approach to the source-channel matching problem in multi-user communication theory are presented. The basic concept is that of a correlated channel code. The approach leads to several new coding problems.

Our main result is that good codes, even those meeting the random coding bound, can be produced with relatively few (linear in the block length) permutations from a single codeword. This cutdown in complexity may be of practical importance. The motivation for looking at such codes came from Ahlswede's covering lemma, which makes it possible to build correlated source codes from channel codes via permutations. In Appendix I we show that the problem of finding the best error exponents for coding sources with full side information at the decoder, which has received attention in the recent literature, can easily be reduced to the familiar one for the discrete memoryless channel (DMC). Finally, in Appendices II and III we give rather precise double exponentially small bounds on the probabilities that a randomly chosen code will fail to meet the random coding or expurgated bound for the DMC. According to these results, good codes are hard to miss if selected at random. This also explains why good codes of a Iow complexity (such as those produced by

The following coding problem for correlated discrete memoryless sources is considered. The two sources can be separately block encoded, and the values of the encoding functions are available to a decoder who wants to answer a certain question concerning the source outputs. Typically, this question has only a few possible answers (even as few as two). The rates of the encoding functions must be found that enable the decoder to answer this question correctly with high probability. It is proven that these rates are often as large as those needed for a full reproduction of the outputs of both sources. Furthermore, if one source is completely known at the decoder, this phenomenon already occurs when what is asked for is the joint type (joint composition) of the two source output blocks, or some function thereof such as the Hamming distance of the two blocks or (for alphabet size at least three) just the parity of this Hamming distance.

Let\{(X_i, Y_i,)\}_{i=1}^{\infty}be a memoryless correlated source with finite alphabets, and let us imagine that one person, encoder 1, observes onlyX^n = X_1,\cdots,X_nand another person, encoder 2, observes onlyY^n = Y_1,\cdots,Y_n. The encoders can produce encoding functionsf_n(X^n)andg_n(Y^n)respectively, which are made available to the decoder. We determine the rate region in case the decoder is interested only in knowingY^n = Y_1,\cdots,Y_n(with small error probability). In Section H of the paper we give a characterization of the capacity region for degraded broadcast channels (DBC's), which was conjectured by Bergmans [11] and is somewhat sharper than the one obtained by Gallager [12].