Exponential error bounds achievable by universal coding and decoding are derived for frame-asynchronous discrete memoryless multiple access channels with two senders, via the method of subtypes, a refinement of the method of types. An empirical entropy decoder is employed. A key tool is an improved packing lemma, that overcomes the technical difficulty caused by codeword repetitions via an induction based new argument. The asymptotic form of the bounds admits numerical evaluation. This demonstrates that error exponents achievable by synchronous transmission can be superseded via controlled asynchronism, i.e. a deliberate shift of the codewords.

Minimization of the expectation EP(X) of a random variable X over a family Γ of plausible prior distributions P is addressed, when Γ is a level set of some convex integral functional. As typical cases, Γ may be an I-divergence ball or some other f-divergence ball or Bregman distance ball. Regarding localization of the infimum, we show that whether or not the minimum of Ep(X) subject to P ∈ Γ is attained, the densities of the almost minimizing distributions cluster around an explicitly specified function that may have integral less than 1 if the minimum is not attained. If Γ is an f-divergence ball of radius k, the minimum is either attained for any choice of k or it is not attained when k is less/larger than a critical value. A conjecture is formulated about extending this result beyond f-divergence balls.

Communication over a discrete memoryless channel is addressed when codewords are transmitted in certain time intervals of arbitrary locations, at other times the channel outputs pure noise. The receiver has to locate and decode the codewords. Exponential error bounds are derived, jointly achievable via a semi-universal or universal decoder. Implications are discussed for the familiar model of communication under strong asynchronism when in exponentially long time only one codeword is transmitted.

Integral functionals based on convex normal integrands are minimized over convex constraint sets. Generalized minimizers exist under a boundedness condition. Sequences of the minimization problems are studied when the constraint sets are nested. The corresponding sequences of generalized minimizers are related to the minimization over limit convex sets. Martingale theorems and moment problems are discussed.

The mathematical problem addressed is minimising the expectation of a random variable over a set of feasible distributions P ϵ Γ, given as a level set of a convex integral functional. As special cases, Γ may be an f-divergence or f-divergence ball or a Bregman ball around a default distribution. Our approach is motivated by geometric intuition and relies upon the theory of minimising convex integral functionals subject to moment constraints. One main result is that all “almost minimisers” P ϵ Γ belong to a small Bregman ball around a specified distribution or defective distribution P, equal to the strict minimiser if that exists but well defined also otherwise.

Shannon theoretic secret key generation by several parties is considered for models in which a secure noisy channel with multiple input and output terminals and a public noiseless channel of unlimited capacity are available for accomplishing this goal. The secret key is generated for a setAof terminals of the noisy channel, with the remaining terminals (if any) cooperating in this task through their public communication. Single-letter lower and upper bounds for secrecy capacities are obtained when secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint fromA. These bounds coincide in special cases, but not in general. We also consider models in which different sets of terminals share multiple keys, one for the terminals in each set with secrecy required from the eavesdropper as well as from the terminals not in this set. Partial results include showing links among the associated secrecy capacity region for multiple keys, the transmission capacity region of the multiple access channel defined by the secure noisy channel, and achievable rates for a single secret key for all the terminals.

Integral functionals based on convex normal integrands are minimized subject to finitely many moment constraints. The integrands are assumed to be strictly convex but not autonomous or differentiable. The effective domain of the value function is described by a modification of the concept of convex core. The minimization is viewed as a primal problem and studied together with a dual one in the framework of convex duality. Main results assume a dual constraint qualification but dispense with the primal constraint qualification. Minimizers and generalized minimizers are explicitly described whenever the primal value is finite. Existence of a generalized dual solution is established whenever the dual value is finite. A generalized Pythagorean identity is presented using Bregman distance and a correction term. Results are applied to minimization of Bregman distances.

Shannon theoretic shared secret key generation by multiple terminals is considered for a source model in which the components of a discrete memoryless multiple source and a noiseless public channel of unlimited capacity are available for accomplishing this goal. A shared secret key is generated for distinct coalitions of terminals, with all the terminals cooperating in this task through their public communication. A communication from a terminal can be a function of its observed source component and of all previous communication. Member terminals of a coalition unite in recovering the key. Secrecy is required from an eavesdropper that observes the public interterminal communication. A single-letter characterization of the shared secret key capacity is obtained. When the key must be concealed additionally from subsets of coalition members, we provide an upper bound for the strict shared secret key capacity.

Stationary ergodic processes with finite alphabets are approximated by finite memory processes based on an n-length realization of the process. Under the assumptions of summable continuity rate and non-nullness, a rate of convergence ind̅-distance is obtained, with explicit constants. Asymptotically, asn→ ∞, the result is near the optimum.

Shannon theoretic secret key generation by several parties is considered for models in which a secure noisy channel with multiple input and output terminals and a public noiseless channel of unlimited capacity are available for accomplishing this goal. The secret key is generated for a set A of terminals of the noisy channel, with the remaining terminals (if any) cooperating in this task through their public communication. Single-letter lower and upper bounds for secrecy capacities are obtained when secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from A. These bounds coincide in special cases, and the lower bounds are not tight in general. We also consider models in which different sets of terminals share multiple keys, one for terminals in each set with secrecy required from the eavesdropper as well as the remaining terminals in the other sets. Partial results include showing links among the associated secrecy capacity region for multiple keys, the transmission capacity region of the multiple access channel defined by the secure noisy channel, and achievable rates for a single secret key for all the terminals.

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.

The problem of minimizing convex integral functionals subject to moment-like constraints is treated in a general setting when the underlying convex function may be multivariate, perhaps not strictly convex or differentiable. The results are applied to the minimization of f-divergences simultaneously in both variables.

In this survey presentation, we consider Shannon-theoretic secret key generation by multiple parties for two categories of models. In the first category, termed source models, multiple terminals are provided prior and privileged access to correlated signals. In the second category, called channel models, these terminals are connected by a secure noisy channel with multiple input and outputs. In both categories, a public noiseless channel of unlimited capacity is available additionally for accomplishing the goal of secrecy generation. The secret key is generated for a subset of the terminals, with the cooperation of remaining terminals (if any) through their public communication. We ask for single-letter characterizations of secrecy capacities for these models when secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from the secrecy seeking set. Complete results have been obtained for secret key capacity for the source model and the channel model with a single input, while partial results are available for the channel model with multiple inputs. These will be surveyed, and some open problems will be discussed.

This is an updated and extended version of the author's 2002 book A First Course in Information Theory. The current book consists of two parts. Part I contains 16 chapters, 14 of them basically identical with those of the first version, not addressing networks. The two new chapters cover differential entropy and continuous alphabet (mainly Gaussian) channels. The second part is of main interest; it provides a comprehensive, state-of-the-art presentation of the theory of network coding. Much of the material is new compared with the 2002 book, and did not even exist in 2002; the rest has also been substantially updated. The book is well written. A commendable new feature is that each chapter ends with a short and clear summary. As before, each chapter is complemented with problems. This is a valuable book that many scientists will use as a reference. It can also be used as a textbook and looks particularly suitable for special purpose courses.

Minimization problems for entropy-like integrals and Bregman distances subject to a finite number of moment constraints are addressed in a general setting. Analogues of the authors’ previous results on information projections to families determined by linear constraints, and reverse information projections to exponential families, are established. No constraint qualification is assumed.

Shannon-theoretic secret key generation by several parties is considered for models in which a secure noisy channel with one input terminal and multiple output terminals and a public noiseless channel of unlimited capacity are available for accomplishing this goal. The secret key is generated for a set$A$of terminals of the noisy channel, with the remaining terminals (if any) cooperating in this task through their public communication. Single-letter characterizations of secrecy capacities are obtained for models in which secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from$A$. These capacities are shown to be achievable with noninteractive public communication, the channel input terminal sending no public message and each output terminal sending at most one public message, not using randomization. Moreover, when the input terminal belongs to the set$A$, it can generate the secret key at the outset and transmit it over the noisy channel, suitably encoded, whereupon the output terminals in$A$securely recover this key using public communication as above. For models in which the eavesdropper also possesses side information that is not available to any of the terminals cooperating in secrecy generation, an upper bound for the secrecy capacity and a sufficient condition for its tightness are given.

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.

Shannon-theoretic secret key generation by several parties is considered for source models in which the distinct components of a multiple source observed separately by multiple terminals, and for channel models in which a secure noisy channel with one input terminal and multiple output terminals, and, additionally in both cases, a public noiseless channel of unlimited capacity, are available for accomplishing this goal. The secret key is generated for a set A of terminals, with the remaining terminals (if any) cooperating in this task through their public communication. We show that for source models in which secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from A, secrecy capacity can be achieved with noninteractive communication, the key being generated by any chosen terminal in the secret key-seeking set A of terminals obliviously of the public communication. For models in which the eavesdropper also possesses side information that is not available to any of the terminals cooperating in secrecy generation, an upper bound for the secrecy capacity and a sufficient condition for its tightness are given. The latter partially fills a gap in the authors' previous work [6].

For a standard full exponential family on Rd, or its canonically convex subfamily, the generalized maximum likelihood estimator is an extension of the mapping that assigns to the mean a ϵ Rd of a sample for which a maximizer v* of the corresponding likelihood function exists, the member of the family parameterized by v*. This extension assigns to each a ϵ Rd with the likelihood function bounded above, a member of the closure of the family in variation distance. Its detailed description, complete characterization of domain and range, and additional results are presented, in a general setting. In addition to basic convex analysis tools, the authors' prior results on convex cores of measures and closures of exponential families are used.

The concept of context tree, usually defined for finite memory processes, is extended to arbitrary stationary ergodic processes (with finite alphabet). These context trees are not necessarily complete, and may be of infinite depth. The familiar Bayesian information criterion (BIC) and minimum description length (MDL) principles are shown to provide strongly consistent estimators of the context tree, via optimization of a criterion for hypothetical context trees of finite depth, allowed to grow with the sample size n as o(logn). Algorithms are provided to compute these estimators in O(n) time, and to compute them on-line for all i les n in o(nlogn) time

We derive single-letter characterizations of (strong) secrecy capacities for models in which a "helper" terminal is connected to an arbitrary number of "user" terminals by a discrete memoryless channel (DMC). The helper terminal governs the input of the DMC, over which it transmits to the user terminals that observe the corresponding outputs; transmissions over the DMC are secure. Additionally, following each transmission over the DMC, unrestricted and interactive public communication is permitted between all the terminals. A subset of the user terminals, and possibly the helper terminal, generate secrecy with the remaining user terminals acting as abettors. We distinguish between the cases in which the helper terminal may, or may not, randomize. Two kinds of secrecy capacity are considered, depending on the extent of an eavesdropper's knowledge: secret key (SK) and private key (PK) capacity. These secrecy capacities are shown to be achievable with noninteractive communication between the terminals and with no public transmission from the helper terminal. When the helper terminal is forbidden to randomize, the needed transmission over the DMC entails only that of a constant sequence. It is also shown that additional randomization at the user terminals does not serve to enhance the secrecy capacities

The concept of context tree, usually defined for finite memory processes, is extended to arbitrary stationary ergodic processes (with finite alphabet). These context trees are not necessarily complete, and may be of infinite depth. The familiar BIC and MDL principles are shown to provide strongly consistent estimators of the context tree, via optimization of a criterion for hypothetical context trees of finite depth, allowed to grow with the sample size n as o(log n). Algorithms are provided to compute these estimators in O(n) time, and to compute them on-line for all i les n in o(nlog n) time

The closure in variation distance of any subfamily with a convex set of canonical parameters of an exponential family has been described previously, in terms of the concept of extension of the full exponential family. This contribution describes the closure in reversed information divergence (rI-closure), via variation closures of auxiliary subfamilies. Also, variation convergence and rI-convergence in the extension are characterized.

For Markov random fields with finite set of states, a modification of the Bayesian information criterion admits strongly consistent estimation of the smallest region that determines the conditional distributions. Phase transition or nonstationarity do not affect the result.

A closure of an exponential family in reversed information divergence may be neither reverse information-closed nor log-convex.

We derive single-letter characterizations of (strong) secrecy capacities for models with an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unrestricted and interactive public communication permitted between the terminals. A subset of these terminals can serve as helpers for the remaining terminals in generating secrecy. According to the extent of an eavesdropper's knowledge, three kinds of secrecy capacity are considered: secret key (SK), private key (PK), and wiretap secret key (WSK) capacity. The characterizations of the SK and PK capacities highlight the innate connections between secrecy generation and multiterminal source coding without secrecy requirements. A general upper bound for WSK capacity is derived which is tight in the case when the eavesdropper can wiretap noisy versions of the components of the underlying multiple source, provided randomization is permitted at the terminals. These secrecy capacities are seen to be achievable with noninteractive communication between the terminals. The achievability results are also shown to be universal.

The goal of this paper is to complete results available about I-projections, reverse I-projections, and their generalized versions, with focus on linear and exponential families. Pythagorean-like identities and inequalities are revisited and generalized, and generalized maximum-likelihood (ML) estimates for exponential families are introduced. The main tool is a new concept of extension of exponential families, based on our earlier results on convex cores of measures.

We consider the problem of characterizing the secret key (SK)-capacity for an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unconstrained public communication allowed between these terminals. Our main contribution is the determination of SK-capacity for an arbitrary subset of terminals with the remaining terminals serving as "helpers," when an eavesdropper observes the communication between the terminals but does not have access to any other information. We also determine the private key (PK)-capacity when the eavesdropper additionally wiretaps some of the helper terminals from which too the key must then be concealed.

For Markov chains of arbitrary order, with finite alphabet A, almost sure sense limit theorems are proved on relative frequencies of k-blocks, and of symbols preceded by a given k-block, when k is permitted to grow as the sample size n grows. As-an application, the-consistency of two kinds of minimum description length (MDL) Markov order estimators is proved, with upper bound o(log n), respectively, /spl alpha/ log n with /spl alpha/ < 1/log |A|, on the permissible value of the estimated order. It was shown by Csiszar and Shields (see Ann. Statist., vol.28, p.1601-1619, 2000) that in the absence of any bound, or with bound /spl alpha/ log n with large /spl alpha/ consistency fails.

We consider the generation of common randomness (CR), secret or not secret, by two user terminals with aid from a "helper" terminal. Each terminal observes a different component of a discrete memoryless multiple source. The helper aids the users by transmitting information to them over a noiseless public channel subject to a rate constraint. Furthermore, one of the users is allowed to transmit to the other user over a public channel under a similar rate constraint. We study the maximum rate of CR which can be thus generated, including under additional secrecy conditions when it must be concealed from a wiretapper. Lower bounds for the corresponding capacities are provided, and single-letter capacity formulas are obtained for several special cases of interest.

In generalized moment problems (signed) measures are searched to fit given observations, or continuous functions are searched to fit given constraints. Known convex methods for solving such problems, and their stochastic interpretations via maximum entropy on the mean (MEM) and in a Bayesian sense are reviewed, with some improvements on previous results. Then the MEM and Bayesian approaches are extended to default models with a dependence structure, yielding new families of solutions. One family involves a transfer kernel, and allows using prior information such as modality, convexity, or Sobolev norms. Another family of solutions with possibly nonconvex criteria, is arrived at using default models with exchangeable random variables. The main technical tools are convex analysis and large deviations theory.

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 method of types is one of the key technical tools in Shannon theory, and this tool is valuable also in other fields. In this paper, some key applications are presented in sufficient detail enabling an interested nonspecialist to gain a working knowledge of the method, and a wide selection of further applications are surveyed. These range from hypothesis testing and large deviations theory through error exponents for discrete memoryless channels and capacity of arbitrarily varying channels to multiuser problems. While the method of types is suitable primarily for discrete memoryless models, its extensions to certain models with memory are also discussed.

Upper and lower bounds, both of order /spl radic/n, are obtained on minimax redundancy of universal lossless codes for the class of renewal processes. This is the first example of an interesting model class with strong redundancy rate o(n) but not O(log n). For the same class, the nonexistence of weak-rate bounds of smaller order than /spl radic/n is also shown. The methods extend to provide upper and lower redundancy rate bounds of order n/sup (k+1)//(k+2) for the class of processes that are Markov renewal of order k. The weak-rate methods also extend to show the nonexistence of o(n) weak-rate bounds for the class of regenerative processes.

Renyi's (1961) entropy and divergence of order a are given operational characterizations in terms of block coding and hypothesis testing, as so-called /spl beta/-cutoff rates, with /spl alpha/=(1+/spl beta/)/sup -1/ for entropy and /spl alpha/=(1-/spl beta/)/sup -1/ for divergence. Out of several possible definitions of mutual information and channel capacity of order /spl alpha/, our approach distinguishes one that admits an operational characterization as /spl beta/-cutoff rate for channel coding, with /spl alpha/=(1-/spl beta/)/sup -1/. The ordinary cutoff rate of a DMC corresponds to /spl beta/=-1.>

For discrete memoryless channels {W: X/spl rarr/Y} we consider decoders, possibly suboptimal, which minimize a metric defined additively by a given function d(x, y)/spl ges/0. The largest rate achievable by codes with such a decoder is called the d-capacity C/sub d/(W). The choice d(x, y)=0 if and only if (iff) W(y|x)>0 makes C/sub d/(W) equal to the "zero undetected error" or "erasures-only" capacity C/sub eo/(W). The graph-theoretic concepts of Shannon capacity (1956, 1974) and Sperner capacity are also special cases of d-capacity, viz. for a noiseless channel with a suitable {0, 1}-valued function d. We show that the lower bound on d-capacity given previously by Csiszar and Korner (1980), and Hui (1983), is not tight in general, but C/sub d/(W)>0 iff this bound is positive. The "product space" improvement of the lower bound is considered,and a "product space characterization" of C/sub eo/(W) is obtained. We also determine the erasures-only (e.o.) capacity of a deterministic arbitrarily varying channel defined by a bipartite graph, and show that it equals capacity. We conclude with a list of challenging open problems.>

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

Previous results of Csiszar and Narayan (1988, 1989, 1991) on the capacity of discrete arbitrarily varying channels with input and state constraints are extended to the case of arbitrary alphabets and state sets. For channels with scalar or vector inputs and additive interference consisting of a deterministic part and noise, both arbitrarily varying subject to power constraints, the capacity for deterministic codes is shown to be equal to the random coding capacity if the input power exceeds the power of the deterministic interference, and zero otherwise. Explicit capacity formulas are also given.>

The Gaussian arbitrarily varying channel with input constraint Gamma and state constraint Lambda admits input sequences x=(x/sub 1/,---,X/sub n/) of real numbers with Sigma x/sub i//sup 2/>

The capacity of an arbitrarily varying channel (AVC) is considered for deterministic codes with the average probability of error criterion and, typically, subject to at state constraint. First, sufficient conditions are provided that enable relatively simple decoding rules such as typicality, maximum mutual information, and minimum distance, to attain capacity. Then the (possibly noisy) OR channels and group adder channels are studied in detail. For the former the capacity is explicitly determined and shown to be attainable by minimum-distance decoding. Next, for a large class of addictive AVCs, in addition to providing an intuitively suggestive simplification of the general AVC capacity formula, it is proven that capacity can be attained by a universal decoding rule. Finally, the effect of random state selections on capacity is studied. The merits and limitations of a previous mutual information game approach are also discussed.>

Random coding theorems are proved for discrete memoryless arbitrarily varying channels (AVCs) with constraints on the transmitted codewords and channel state sequences. Two types of constraints are considered: peak (i.e. required for each n-length sequence almost surely) and average (over the message set or over an ensemble). For peak constraints on the codewords and on the channel state sequences, the AVC is shown to have a (strong) random coding capacity. If the codewords and/or the channel state sequences are constrained in the average sense, the AVCs do not possess (strong) capacities; only epsilon -capacities are shown to exist.>

A well-known result of R. Ahlswede (1970) asserts that the deterministic code capacity of an arbitrarily varying channel (AVC), under the average-error-probability criterion, either equals its random code capacity or else is zero. A necessary and sufficient condition is identified for deciding between these alternative, namely, the capacity is zero if and only if the AVC is symmetrizable. The capacity of the AVC is determined with constraints on the transmitted codewords as well as on the channel state sequences, and it is demonstrated that it may be positive but less than the corresponding random code capacity. A special case of the results resolves a weakened version of a fundamental problem of coding theory.>

LetX_{1},X_{2},\cdotsbe independent identically distributed random variables taking values in a finite setXand consider the conditional joint distribution of the first m elements of the sampleX_{1},\cdots , X_{n}on the condition thatX_{1}=x_{1}and the sliding block sample average of a functionh(\cdot , \cdot)defined onX^{2}exceeds a threshold\alpha > Eh(X_{1}, X_{2}). Formfixed andn \rightarrow \infty, this conditional joint distribution is shown to converge m them-step joint distribution of a Markov chain started inx_{1}which is closest toX_{l}, X_{2}, \cdotsin Kullback-Leibler information divergence among all Markov chains whose two-dimensional stationary distributionP(\cdot , \cdot)satisfies\sum P(x, y)h(x, y)\geq \alpha, provided some distributionPonX_{2}having equal marginals does satisfy this constraint with strict inequality. Similar conditional limit theorems are obtained whenX_{1}, X_{2},\cdotsis an arbitrary finite-order Markov chain and more general conditioning is allowed.

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.

For Slepian-Wolf source networks, the error exponents obtained by Körner,Marton, and the author are shown to be universally attainable by linear codes also. Improved exponents are derived for linear codes with "large rates." Specializing the results to simple discrete memoryless sources reveals their relationship to the random coding and expurgated bounds for channels with additive noise. One corollary is that there are universal linear codes for this class of channels which attain the random coding error exponent for each channel in the class. The combinatorial approach of Csiszár-Körner-Marton is used. In particular, all results are derived from a lemma specifying good encoders in terms of purely combinatorial properties.

The author's previous results on the exponent of probability of error for joint source-channel codes are improved and extended to distortion threshold fidelity criteria. The maximum error version of the problem is also considered.

Asymptotically coincident upper and lower bounds on the exponent of the largest possible probability of correct decoding for block codes of any given rate above capacity have been given by Dueck and Körner. Their method is extended to show that the same bounds also hold in the presence of noiseless feedback.

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.

A new and simple method is proposed for finding good encoders both for channels and for sources with side information. This method relies on the continuous version of a graph decomposition result of Lovász. The presently known best exponential error bounds for both problems follow in a unified manner with an improvement on the source coding bound. The previous bounds for universal codes of the authors and Marton are also improved.

A unified approach to multiterminal source coding problems not involving rate-distortion theory is presented. It is shown that, for determining file achievable rate region, attention may be restricted to source networks of a relatively simple structure. A product space characterizafion of the achievable rate region pinpoints the mathematical problem to be solved for getting a single letter characterization. The complexity of this problem depends on a structural condition, viz., the number of encoders of a certain kind in the source network. This approach yields all the known single-letter characterizations of achievable rate regions and a number of new ones for more complex networks. As a digression, for a class of source networks including that of Slepian and Wolf, exponential error bounds are derived which are attainable by universal codes. These bounds are tight in a neighborhood of the boundary of the achievable rate region.

Given two discrete memoryless channels (DMC's) with a common input, it is desired to transmit private messages to receiver1rateR_{1}and common messages to both receivers at rateR_{o}, while keeping receiver2as ignorant of the private messages as possible. Measuring ignorance by equivocation, a single-letter characterization is given of the achievable triples(R_{1},R_{e},R_{o})whereR_{e}is the equivocation rate. Based on this channel coding result, the related source-channel matching problem is also settled. These results generalize those of Wyner on the wiretap channel and of Körner-Marton on the broadcast Channel.

In a recent paper [1], Blahut suggested an efficient algorithm for computing rate-distortion functions. In this correspondence we show that the sequence of distributions used in that algorithm has a limit yielding a point on theR(d)curve if the reproducing alphabet is finite, and we obtain a similar but weaker result for countable reproducing alphabets.