Through refined asymptotic analysis based on the normal approximation, we study how higher-order coding performance depends on the mean power as well as on finer statistics of the input power. We introduce a multifaceted power model in which the expectation of an arbitrary (but finite) number of arbitrary functions of the normalized average power is constrained. The framework generalizes existing models, recovering the standard maximal and expected power constraints and the recent mean and variance constraint as special cases. Under certain growth and continuity assumptions on the functions, our main theorem gives an exact characterization of the minimum average error probability for Gaussian channels as a function of the first- and second-order coding rates. The converse proof reduces the code design problem to minimization over a compact (under the Prokhorov metric) set of probability distributions, characterizes the extreme points of this set and invokes the Bauer's maximization principle. Our results for the multifaceted power model serve as more precise benchmarks for practical modulation schemes with multiple amplitude levels, probabilistic shaping and nonuniform constellation geometries.

For variable-length coding with an almost-sure distortion constraint, Zhang et al. show that for discrete sources the redundancy is upper bounded by $\log n/n$ and lower bounded (in most cases) by $\log n/(2n)$, ignoring lower order terms. For a uniform source with a distortion measure satisfying certain symmetry conditions, we show that $\log n/(2n)$ is achievable and that this cannot be improved even if one relaxes the distortion constraint to be in expectation rather than with probability one.

Through refined asymptotic analysis based on the normal approximation, we study how higher-order coding performance depends on the mean power as well as on finer statistics of the input power. We introduce a multifaceted power model in which the expectation of an arbitrary (but finite) number of arbitrary functions of the normalized average power is constrained. The framework generalizes existing models, recovering the standard maximal and expected power constraints and the recent mean and variance constraint as special cases. Under certain growth and continuity assumptions on the functions, our main theorem gives an exact characterization of the minimum average error probability for Gaussian channels as a function of the first- and second-order coding rates. The converse proof reduces the code design problem to minimization over a compact (under the Prokhorov metric) set of probability distributions, characterizes the extreme points of this set and invokes the Bauer’s maximization principle. Our results for the multifaceted power model serve as more precise benchmarks for practical modulation schemes with multiple amplitude levels, probabilistic shaping and nonuniform constellation geometries.

We consider channel coding for Gaussian channels with the recently introduced mean and variance cost constraint. Through matching converse and achievability bounds, we charac-terize the optimal first- and second-order performance. The main technical contribution of this paper is an achievability scheme which uses random codewords drawn from a mixture of three uniform distributions on$(n-1)$-spheres of radii$R_{1}, R_{2}$and$R_{3}$, where$R_{i}=O(\sqrt{n})$and$\vert R_{i}-R_{j}\vert =O(1)$. To analyze such a mixture distribution, we prove a lemma giving a uniform$O(\log n)$bound, which holds with high probability, on the$\log$ratio of the output distributions$Q_{i}^{cc}$and$Q_{j}^{cc}$, where$Q_{i}^{cc}$is induced by a random channel input uniformly distributed on an$(n - 1)$-sphere of radius$R_{i}$. To facilitate the application of the usual central limit theorem, we also give a uniform$O(\log n)$bound, which holds with high probability, on the log ratio of the output distributions$Q_{i}^{cc}$and$Q_{i}^{\ast}$, where$Q_{i}^{\ast}$is induced by a random channel input with i.i.d. components.

Channel coding for discrete memoryless channels (DMCs) with mean and variance cost constraints has been recently introduced. We show that there is an improvement in coding performance due to cost variability, both with and without feedback. We demonstrate this improvement over the traditional almost-sure (per-codeword) cost constraint that prohibits any cost variation above a fixed threshold. Our result simultaneously shows that feedback does not improve the second-order coding rate of simple-dispersion DMCs under the almost-sure cost constraint. This finding parallels similar results for unconstrained simple-dispersion DMCs, additive white Gaussian noise (AWGN) channels and parallel Gaussian channels.

We consider channel coding for discrete memoryless channels (DMCs) with a novel cost constraint that constrains both the mean and the variance of the cost of the codewords. We show that the maximum (asymptotically) achievable rate under the new cost formulation is equal to the capacity-cost function; in particular, the strong converse holds. We further characterize the optimal second-order coding rate of these cost-constrained codes; in particular, the optimal second-order coding rate is finite. We then show that the second-order coding performance is strictly improved with feedback using a new variation of timid/bold coding, significantly broadening the applicability of timid/bold coding schemes from unconstrained compound-dispersion channels to all cost-constrained channels. Equivalent results on the minimum average probability of error are also given.

Presents corrections to the paper, (Errata to “Channel Coding With Mean and Variance Cost Constraints”).

We consider channel coding for Gaussian channels with the recently introduced mean and variance cost constraints. Through matching converse and achievability bounds, we characterize the optimal first- and second-order performance. The main technical contribution of this paper is an achievability scheme which uses random codewords drawn from a mixture of three uniform distributions on (n−1)-spheres of radiiR1,R2andR3, whereRi=O( √n) and |Ri−Rj| = O(1). To analyze such a mixture distribution, we prove a lemma giving a uniformO(logn) bound, which holds with high probability, on the log ratio of the output distributionsQcciandQccj, whereQcciis induced by a random channel input uniformly distributed on an (n− 1)-sphere of radiusRi. To facilitate the application of the usual central limit theorem, we also give a uniformO(logn) bound, which holds with high probability, on the log ratio of the output distributionsQcciandQ∗i, whereQ∗iis induced by a random channel input with i.i.d. components.

In image compression, with recent advances in generative modeling, the existence of a trade-off between the rate and the perceptual quality (realism) has been brought to light, where the realism is measured by the closeness of the output distribution to the source. It has been shown that randomized codes can be strictly better under a number of formulations. In particular, the role of common randomness has been well studied. We elucidate the role of private randomness in the compression of a memoryless source$X^{n}=(X_{1},\ \ldots,\ X_{n})$under two kinds of realism constraints. The near-perfect realism constraint requires the joint distribution of output symbols$(Y_{1},\ \ldots,\ Y_{n})$to be ar-bitrarily close the distribution of the source in total variation distance (TVD). The per-symbol near-perfect realism constraint requires that the TVD between the distribution of output symbol$Y_{t}$and the source distribution be arbitrarily small, uniformly in the index$t$. We characterize the corresponding asymptotic rate-distortion trade-off and show that encoder private randomness is not useful if the compression rate is lower than the entropy of the source, however limited the resources in terms of common randomness and decoder private randomness may be.

We consider channel coding for discrete memoryless channels (DMCs) with a novel cost constraint that constrains both the mean and the variance of the cost of the codewords. We show that the maximum (asymptotically) achievable rate under the new cost formulation is equal to the capacity-cost function; in particular, the strong converse holds. We further characterize the optimal second-order coding rate of these cost-constrained codes; in particular, the optimal second-order coding rate is finite. We then show that the second -order coding performance is strictly improved with feedback using a new variation of timid/bold coding, significantly broadening the applicability of timid/bold coding schemes from unconstrained compound-dispersion chan-nels to all cost-constrained channels. Equivalent results on the minimum average probability of error are also given.

Wasserstein distortion is a one-parameter family of distortion measures that was recently proposed to unify fidelity and realism constraints. After establishing continuity results for Wasserstein distortion in the extreme cases of pure fidelity and pure realism, we prove the first coding theorems for compression under Wasserstein distortion focusing on the regime in which both the rate and the distortion are small.

We consider the redundancy of the exact channel synthesis problem under an i.i.d. assumption. Existing results provide an upper bound on the unnormalized redundancy that is logarithmic in the block length. We show, via an improved scheme, that the logarithmic term can be halved for most channels and eliminated for all others. For full-support discrete memory less channels, we show that this is the best possible.

We consider the design of practically-implementable schemes for the task of channel simulation. Existing methods do not scale with the number of simultaneous uses of the channel and are therefore unable to harness the amortization gains associated with simulating many uses of the channel at once. We show how techniques from the theory of error-correcting codes can be applied to achieve scalability and hence improved performance. As an exemplar, we focus on how polar codes can be used to efficiently simulate i.i.d. copies of a class of binary-output channels.

We characterize the growth of the Sibson and Arimoto mutual informations and$\alpha $-maximal leakage, of any order that is at least unity, between a random variable and a growing set of noisy, conditionally independent and identically-distributed observations of the random variable. Each of these measures increases exponentially fast to a limit that is order- and measure-dependent, with an exponent that is order- and measure-independent.

We show that a variation of the timid/bold coding scheme for feedback communication can be used to improve the second-order coding rate for most discrete memoryless channels with a cost constraint, even in the simple-dispersion case for which the optimal input distribution is unique.

We study the quadratic Gaussian one-help-two source-coding problem with Markovity, in which three encoders separately encode the components of a memoryless vector-Gaussian source that form a Markov chain and the central decoder aims to reproduce the first and the second components in the chain subject to individual mean-squared distortion constraints. We determine the rate region under a high-resolution assumption for the middle source.

We consider a novel variant of$d$-semifaithful lossy coding in which the distortion measure is revealed only to the encoder and only at run-time, as well as an extension of it in which the distortion constraint$d$is also revealed at run-time. Two forms of rate redundancy are used to analyze the performance, and achievability results of both a pointwise and minimax nature are demonstrated. The first coding scheme uses ideas from VC dimension and growth functions, the second uses appropriate quantization of the space of distortion measures, and the third relies on a random coding argument.

We show the existence of variable-rate rate-distortion codes that meet the distortion constraint almost surely and are minimax, i.e., strongly, universal with respect to an unknown source distribution and a distortion measure that is revealed only to the encoder and only at runtime. If we only require minimax universality with respect to the source distribution and not the distortion measure, then we provide an achievable$\tilde {O}(1/\sqrt {n})$redundancy rate, which we show is optimal. This is in contrast to prior work on universal lossy compression, which provides$O(\log n/n)$redundancy guarantees for weakly universal codes under various regularity conditions. We show that either eliminating the regularity conditions or upgrading to strong universality while keeping these regularity conditions entails an inevitable increase in the redundancy to$\tilde {O}(1/\sqrt {n})$. Our construction involves random coding with non-i.i.d. codewords and a zero-rate uncoded transmission scheme. The proof uses exact asymptotics from large deviations, acceptance-rejection sampling, and the VC dimension of distortion measures.

This paper presents a method for computing a finite-blocklength converse for the rate of fixed-length codes with feedback used on discrete memoryless channels (DMCs). The new converse is expressed in terms of a stochastic control problem whose solution can be efficiently computed using dynamic programming and Fourier methods. For channels such as the binary symmetric channel (BSC) and binary erasure channel (BEC), the accuracy of the proposed converse is similar to that of existing special-purpose converse bounds, but the new converse technique can be applied to arbitrary DMCs. We provide example applications of the new converse technique to the binary asymmetric channel (BAC) and the quantized amplitude-constrained AWGN channel.

We consider the one-bit quantizer that minimizes the mean squared error for a source living in a real Hilbert space. The optimal quantizer is a projection followed by a thresholding operation, and we provide methods for identifying the optimal direction along which to project. As an application of our methods, we characterize the optimal one-bit quantizer for a continuous-time random process that exhibits low-dimensional structure. We numerically show that this optimal quantizer is found by a neural-network-based compressor trained via stochastic gradient descent.

Given a binary random variable X representing sensitive information and n noisy observations Y1, Y2, … , Ynavailable to an adversary, we analyze the maximal leakage $\mathcal{L}\left( {X \to {Y^n}} \right)$ in the following setting modeling adaptive attacks. At each stage i, the adversary may choose an action to interact with the system containing X to obtain Yi. The action may depend on previous realizations of the observations, but the leakage at each stage is limited. We derive an adaptive composition theorem wherein $\mathcal{L}\left( {X \to {Y^n}} \right)$ is bounded in terms of the leakage of each stage. Furthermore, we show that the bound is achieved for $\mathcal{L}\left( {X \to {Z^n}} \right)$ where (Z1, Z2, … , Zn) are conditionally independent given X and each Zicorresponds to the output of a binary erasure channel with the appropriate parameter; moreover, X −Zn−Yncan be coupled as a Markov chain for any feasible Yn. As a corollary of this result and the asymptotic analysis of composition by Wu et al., we show that the binary erasure channel maximizes the Chernoff information between the "rows" of binary-input channels given a maximal leakage constraint. On the other hand, we show that the binary symmetric channel minimizes the Chernoff information for a given maximal leakage constraint.

We consider a novel variant of lossy coding in which the distortion measure is revealed only to the encoder and only at run-time, as well as an extension of it in which the distortion constraint is also revealed at run-time. Two forms of rate redundancy are used to analyze the performance, and achievability results of both a pointwise and minimax nature are demonstrated. One proof uses appropriate quantization of the space of distortion measures while another uses ideas from VC dimension and growth functions.

We show the existence of universal, variable-rate rate-distortion codes that meet the distortion constraint almost surely and approach the rate-distortion function uniformly with respect to an unknown source distribution and a distortion measure that is only revealed to the encoder and only at runtime. If the convergence only needs to be uniform with respect to the source distribution and not the distortion measure, then we provide an explicit bound on the minimax rate of convergence. Our construction combines conventional random coding with a zero-rate uncoded transmission scheme. The proof uses exact asymptotics from large deviations, acceptance-rejection sampling, the VC dimension of distortion measures, and the identification of an explicit, code-independent, finite-blocklength quantity, which converges to the rate-distortion function, that controls the performance of the best codes.

Artifical Neural-Network-based (ANN-based) lossy compressors have recently obtained striking results on several sources. Their success may be ascribed to an ability to identify the structure of low-dimensional manifolds in high-dimensional ambient spaces. Indeed, prior work has shown that ANN-based compressors can achieve the optimal entropy-distortion curve for some such sources. In contrast, we determine the optimal entropy-distortion tradeoffs for two low-dimensional manifolds with circular structure and show that state-of-the-art ANN-based compressors fail to optimally compress them.

Neural-network-based compressors have proven to be remarkably effective at compressing sources, such as images, that are nominally high-dimensional but presumed to be concentrated on a low-dimensional manifold. We consider a continuous-time random process that models an extreme version of such a source, wherein the realizations fall along a one-dimensional “curve” in function space that has infinite-dimensional linear span. We precisely characterize the optimal entropy-distortion tradeoff for this source and show numerically that it is achieved by neural-network-based compressors trained via stochastic gradient descent. In contrast, we show both analytically and experimentally that compressors based on the classical Karhunen-Loeve transform are highly suboptimal at high rates.

We consider a linear autoencoder in which the latent variables are quantized, or corrupted by noise, and the constraint is Schur-concave in the set of latent variances. Although finding the optimal encoder/decoder pair for this setup is a nonconvex optimization problem, we show that decomposing the source into its principal components is optimal. If the constraint is strictly Schur-concave and the empirical covariance matrix has only simple eigenvalues, then any optimal encoder/decoder must decompose the source in this way. As one application, we consider a strictly Schur-concave constraint that estimates the number of bits needed to represent the latent variables under fixed-rate encoding, a setup that we call \emph{Principal Bit Analysis (PBA)}. This yields a practical, general-purpose, fixed-rate compressor that outperforms existing algorithms. As a second application, we show that a prototypical autoencoder-based variable-rate compressor is guaranteed to decompose the source into its principal components.

We provide a practical implementation of the rubber method of Ahlswede et al. for binary channels. The idea is to create the “skeleton” sequence therein via an arithmetic decoder designed for a particular k-th order Markov chain. For the stochastic binary symmetric channel, we show that the scheme is nearly optimal in a strong sense for certain parameters. A byproduct of the analysis is a strict enlargement of the rates for which the sphere-packing bound is known to be achievable with feedback for this channel.

The exact order of the optimal sub-exponentially decaying factor in the classical bounds on the error probability of fixed-length codes over a Gallager-symmetric discrete memoryless channel with and without ideal feedback is determined for rates above the critical rate. Regardless of the availability of feedback, it is shown that the order of the optimal sub-exponential factor exhibits a dichotomy. Moreover, the proof technique is used to establish the third-order term in the normal approximation for symmetric channels, where a similar dichotomy is shown to exist.

We characterize the growth of the Sibson mutual information, of any order that is at least unity, between a random variable and an increasing set of noisy, conditionally independent observations of the random variable. The Sibson mutual information increases to an order-dependent limit exponentially fast, with an exponent that is order-independent. The result is contrasted with composition theorems in differential privacy.

Recent studies have suggested that the stability of peer-to-peer networks may rely on persistent peers, who dwell on the network after they obtain the entire file. In the absence of such peers, one piece becomes extremely rare in the network, which leads to instability. Technological developments, however, are poised to reduce the incidence of persistent peers, giving rise to a need for a protocol that guarantees stability with non-persistent peers. We propose a novel peer-to-peer protocol, the group suppression protocol, to ensure the stability of peer-to-peer networks under the scenario that all the peers adopt non-persistent behavior. Using a suitable Lyapunov potential function, the group suppression protocol is proven to be stable when the file is broken into two pieces, and detailed experiments demonstrate the stability of the protocol for arbitrary number of pieces. We define and simulate a decentralized version of this protocol for practical applications. Straightforward incorporation of the group suppression protocol into BitTorrent while retaining most of BitTorrent's core mechanisms is also presented. Subsequent simulations show that under certain assumptions, BitTorrent with the official protocol cannot escape from the missing piece syndrome, but BitTorrent with group suppression does.

Given two random variables X and Y, an operational approach is undertaken to quantify the “leakage” of information from X to Y. The resulting measure L (X→Y ) is called maximal leakage, and is defined as the multiplicative increase, upon observing Y , of the probability of correctly guessing a randomized function of X, maximized over all such randomized functions. A closed-form expression for L (X→Y) is given for discrete X and Y, and it is subsequently generalized to handle a large class of random variables. The resulting properties are shown to be consistent with an axiomatic view of a leakage measure, and the definition is shown to be robust to variations in the setup. Moreover, a variant of the Shannon cipher system is studied, in which performance of an encryption scheme is measured using maximal leakage. A single-letter characterization of the optimal limit of (normalized) maximal leakage is derived and asymptotically-optimal encryption schemes are demonstrated. Furthermore, the sample complexity of estimating maximal leakage from data is characterized up to subpolynomial factors. Finally, the guessing framework used to define maximal leakage is used to give operational interpretations of commonly used leakage measures, such as Shannon capacity, maximal correlation, and local differential privacy.

We introduce a novel mechanism, called timid/bold coding, by which feedback can be used to improve coding performance. For a certain class of DMCs, called compound-dispersion channels, we show that timid/bold coding allows for an improved second-order coding rate compared with coding without feedback. For DMCs that are not compound dispersion, we show that feedback does not improve the second-order coding rate. Thus we completely determine the class of DMCs for which feedback improves the second-order coding rate. An upper bound on the second-order coding rate is provided for compound-dispersion DMCs. We also show that feedback does not improve the second-order coding rate for very noisy DMCs. The main results are obtained by relating feedback codes to certain controlled diffusions.

The entropy of a quantum system is a measure of its randomness and is useful in quantifying entanglement. We study the problem of measuring the von Neumann and Rényi entropies of an unknown mixed quantum state given access to independent copies of the state. For Rényi entropy of integral order exceeding one, we determine the order-optimal copy complexity and show that it is strictly lower than the number of copies required to learn the underlying state. The main technical innovation is a concentration result for certain polynomials that arise in the Kerov algebra of Young diagrams, which is proven using the cycle structure of compositions of certain types of permutations. For von Neumann entropy and Rényi entropy of non-integral orders, we provide upper and lower bounds on the sample complexity of the Empirical Young Diagram (EYD) algorithm, which is the analogue of the empirical plug-in estimator in classical estimation.

This paper revisits the quadratic Gaussian two-encoder source-coding problem, for which a Gaussian quantize-and-bin scheme, also known as the Berger-Tung scheme, is known to achieve the entire rate region. We present a new proof of the impossibility half of the rate-region optimality result that is arguably more direct.

We introduce a new distortion measure for point processes called functional-covering distortion. It is inspired by intensity theory and is related to both the covering of point processes and the logarithmic-loss distortion. We obtain the distortion-rate function with feedforward under this distortion measure for a large class of point processes. For Poisson processes, we characterize the rate-distortion region for a two-encoder CEO problem and show that feedforward does not improve this region.

We study two-receiver Poisson channels using tools derived from stochastic calculus. We obtain a general formula for the mutual information over the Poisson channel that allows for conditioning and the use of auxiliary random variables. We then use this formula to compute necessary and sufficient conditions under which one Poisson channel is less noisy and/or more capable than another, which turn out to be distinct from the conditions under which this ordering holds for the discretized versions of the channels. We also use a general formula to determine the capacity region of the more capable Poisson broadcast channel with independent message sets, the more capable Poisson wiretap channel, and the general two-decoder Poisson broadcast channel with degraded message sets.

We consider a rate-distortion problem with side information at multiple decoders. Several upper and lower bounds have been proposed for this general problem or special cases of it. We provide an upper bound for general instances of this problem, which takes the form of a linear program, by utilizing random binning and simultaneous decoding techniques [1] and compare it with the existing bounds. We also provide a lower bound for the general problem, which was inspired by a linear-programming lower bound for index coding, and show that it subsumes most of the lower bounds in literature. Using these upper and lower bounds, we explicitly characterize the rate-distortion function of a problem that can be seen as a Gaussian analogue of the “odd-cycle” index coding problem.

We study exponential-server timing channels, in which the transmitter encodes a message using a sequence of packet inter-arrival times and the receiver observes the corresponding inter-departure times from an exponential-server queue. We show that if the service rate of one such queue is faster than that of another, then the latter channel is stochastically degraded with respect to the former. This combined with Burke's theorem implies that the slower queue is more entropy increasing than the first. These facts put together provide a converse for the secrecy capacity of the wiretapped version of the channel, matching an earlier achievability result in the literature.

We consider the quadratic Gaussian one-help-two source-coding problem with Markovity, in which three encoders separately encode the components of a memoryless vector-Gaussian source that form a Markov chain and the central decoder aims to reproduce the first and the second components in the chain subject to individual distortion constraints. For this problem, we determine the minimum sum rate of the first and the second encoder given the distortion constraints and the rate of the third encoder. In particular, a simple scheme consisting of vector quantization followed by Slepian-Wolf binning achieves this minimum sum-rate. The proof of the converse draws from the quadratic Gaussian two-encoder source-coding problem, the Gaussian scalar-help-vector source-coding problem, and the Gaussian many-help-one source-coding problem.

We consider a communication system with one encoder, one decoder, and an omniscient adversary that can potentially alter the message received by the decoder in a way that maximizes the realized distortion. We are interested in the tradeoff between the rate of the message, the distortion when the packet is not altered, and the distortion when it is. We present an achievable scheme, which illustrates a particular mechanism for designing the codebook so as to limit the harm that can be done by the adversary, and an impossibility result. A binary example is solved exactly over a certain range of rates.

It is shown that feedback does not improve the second-order coding rate for a class of discrete memoryless channels which complements the class of channels for which feedback is known to improve the second-order coding rate. A refined achievability scheme is presented for the second-order rate when feedback helps. Moreover, for such channels an upper bound is derived on the achievable rate with feedback utilizing a novel proof technique.

We consider a problem in which a source is encoded into N packets, an unknown number of which are subject to adversarial errors en route to the decoder. We seek code designs for which the decoder is guaranteed to be able to reproduce the source subject to a certain distortion constraint when there are no packets errors, subject to a less stringent distortion constraint when there is one error, and so on. Focusing on the special case of the erasure distortion measure, we introduce a code design based on the polytope codes of Kosut et al.. The resulting designs are also applied to a separate problem in distributed storage.

We provide a novel upper bound on the rate-distortion function with multiple decoders with side information, which takes the form of a linear program. This complements a recently-obtained lower bound that also takes the form of a linear program. We show that the upper bound is optimal in several instances of the problem1.

Recent studies have suggested that the stability of peer-to-peer networks may rely on persistent peers, who dwell on the network after they obtain the entire file. In the absence of such peers, one piece becomes extremely rare in the network, which leads to instability. Technological developments, however, are poised to reduce the incidence of persistent peers, giving rise to a need for a protocol that guarantees stability with nonpersistent peers. We propose a novel peer-to-peer protocol, the group suppression protocol, to ensure the stability of peer-to-peer networks under the scenario that all the peers adopt non-persistent behavior. Using a suitable Lyapunov potential function, the group suppression protocol is proven to be stable when the file is broken into two pieces, and detailed experiments demonstrate the stability of the protocol for arbitrary number of pieces. Straightforward incorporation of the group suppression protocol into BitTorrent while retaining most of BitTorrent's core mechanisms is also presented. Subsequent simulations show that under certain assumptions, BitTorrent with the official protocol cannot escape from the missing piece syndrome, but BitTorrent with group suppression does.

Maximal leakage from a random variable X to a random variable Y is defined as the multiplicative increase, upon observing Y, of the probability of correctly guessing a randomized function of X, maximized over all such functions [1]. Herein, this guessing framework is used to give operational definitions to common information leakage metrics, including Shannon capacity, maximal correlation, and local differential privacy. Shannon capacity is shown to capture the multiplicative increase of the probability of correct guessing over the restricted set of functions of X that can be reliably reconstructed from Y, hence underestimating leakage. Maximal correlation is shown to capture the multiplicative change in the variance of functions of X, rather than the guessing probability. Local differential privacy is shown to capture the multiplicative increase of the guessing probability of functions of X, maximized over realizations of Y and over distributions Px. Moreover, maximizing over realizations of Y for a fixed Pxis shown to yield a valid leakage measure, which is equal to the maximum information rate.

We consider the problem of encoding an i.i.d. source into a set of symbols or messages that may be altered by an adversary while en route to the decoder. We focus in particular on the regime in which the number of messages is fixed while the blocklength of the source and the size of each message tend to infinity. For this fixed-blocklength, “large alphabet” channel, we show that combining an optimal rate-distortion code with an optimal error-correction code yields an optimal overall code for Gaussian sources with quadratic distortion and binary uniform sources with Hamming distortion but that it can be suboptimal by an arbitrarily large factor in general. We also consider the scenario in which the distortion constraint that the decoder must satisfy depends on the number of errors that occur. We show that the problem can be reduced operationally to one with erasures instead of errors in two special cases: one involving lossless reproduction of functions of the source and one in which the encoder and decoder share common randomness.

The secrecy of a communication system in which both the legitimate receiver and an eavesdropper are allowed some distortion is investigated. The secrecy metric considered is the exponent of the probability that the eavesdropper estimates the source sequence successfully within an acceptable distortion level. The problem is first studied when the transmitter and the legitimate receiver do not share any key and the transmitter is not subject to a rate constraint, which corresponds to a stylized model of a side channel and reveals connections to source coding with side information. The setting is then generalized to include a shared secret key between the transmitter and the legitimate receiver and a rate constraint on the transmitter, which corresponds to the Shannon cipher system. A single-letter characterization of the highest achievable exponent is provided, and asymptotically optimal strategies for both the primary user and the eavesdropper are demonstrated.

We consider rate-distortion with two decoders, each with distinct side information. This problem is well understood when the side information at the decoders satisfies a certain degradedness condition. We consider cases in which this degradedness condition is violated but the source and the side information consist of jointly Gaussian vectors. We provide a hierarchy of four lower bounds on the optimal rate. These bounds are then used to determine the optimal rate for several classes of instances.

A variation of the Shannon cipher system, in which lossy communication is allowed and performance of an encryption scheme is measured in terms of maximal leakage (recently proposed by the authors [1]), is investigated. The asymptotic behavior of normalized maximal leakage is studied, and a single-letter characterization of the optimal limit is derived. Moreover, asymptotically-optimal encryption schemes are demonstrated.

We study two-receiver Poisson channels using tools derived from stochastic calculus. We compute necessary and sufficient conditions under which the continuous-time, continuous-space Poisson channel is less noisy and more capable, which turn out to be distinct from the conditions under which the “sampled” channel is less noisy and more capable. We also determine the capacity region of the more capable Poisson broadcast channel with independent message sets, the more capable Poisson wiretap channel, and the general two-decoder Poisson broadcast channel with degraded message sets.

We consider a rate distortion problem with side information at multiple decoders. Several lower bounds have been proposed for this general problem or special cases of it. We provide a lower bound for general instances of this problem, which was inspired by a linear-programming lower bound for index coding, and show that it subsumes most of the lower bounds in literature. Using this bound, we explicitly characterize the rate distortion function of a problem which can be seen as a Gaussian analogue of the “odd-cycle” index coding problem.

We approach index coding as a special case of rate–distortion with multiple receivers, each with some side information about the source. Specifically, using techniques developed for the rate–distortion problem, we provide two upper bounds and one lower bound on the optimal index coding rate. The upper bounds involve specific choices of the auxiliary random variables in the best existing scheme for the rate–distortion problem. The lower bound is based on a new lower bound for the general rate–distortion problem. The bounds are shown to coincide for a number of (groupcast) index coding instances, including all instances for which the number of decoders does not exceed three.

We consider a video delivery problem in which a server multicasts a video to several users over a wireless broadcast channel. Users arrive and depart asynchronously, and when a user arrives, he/she wishes to watch the video from the beginning. Existing approaches for this problem assume that the server is either completely aware of the state of the users or is completely oblivious to their states, the former being most useful for small numbers of users and the latter being most useful for large networks. We propose a dynamic-programming-based scheduler that can operate in both of these regimes, as well as the intermediate regime in which feedback is available but incomplete. The scheduler is validated both numerically and experimentally.

We consider the problem of information embedding where the encoder modifies a white Gaussian host signal in a power-constrained manner to encode a message, and the decoder recovers both the embedded message and the modified host signal. This partially extends the recent work of Sumszyk and Steinberg to the continuous-alphabet Gaussian setting. Through a control-theoretic lens, we observe that the problem is a minimalist example of what is called the triple role of control actions. We show that a dirty-paper-coding strategy achieves the optimal rate for perfect recovery of the modified host and the message for any message rate. For imperfect recovery of the modified host, by deriving bounds on the minimum mean-square error (MMSE) in recovering the modified host signal, we show that Dirty-Paper Coding-based strategies are guaranteed to attain within a uniform constant factor of 16 of the optimal weighted sum of power required in host signal modification and the MMSE in the modified host signal reconstruction for all weights and all message rates. When specialized to the zero-rate case, our results provide the tightest known lower bounds on the asymptotic costs for the vector version of a famous open problem in decentralized control: the Witsenhausen counterexample. Numerically, this tighter bound helps us characterize the asymptotically optimal costs for the vector Witsenhausen problem to within a factor of 1.3 for all problem parameters, improving on the earlier best known bound of 2.

We determine the rate region of the vector Gaussian one-helper source-coding problem under a covariance matrix distortion constraint. The rate region is achieved by a simple scheme that separates the lossy vector quantization from the lossless spatial compression. The converse is established by extending and combining three analysis techniques that have been employed in the past to obtain partial results for the problem.

For a singular and symmetric discrete memoryless channel with positive dispersion, the third-order term in the normal approximation is shown to be upper bounded by a constant. This finding completes the characterization of the third-order term for symmetric discrete memoryless channels. The proof method is extended to asymmetric and singular channels with constant composition codes, and its connection to existing results, as well as its limitation in the error exponents regime, are discussed.

For a class of discrete memoryless channels, a simple feedback scheme is shown to improve the second-order term in the normal approximation compared with coding without feedback. Conversely, we provide a new, second-moment-based condition for when feedback does not improve the second-order term.

We investigate the rate-distortion region of a vector Gaussian source and two decoders with side information. We determine the rate-distortion region when both decoders have an error covariance distortion constraint that are scaled identity matrices.

We provide a refinement of the sphere-packing bound for constant composition codes over asymmetric discrete memoryless channels that improves the subexponential factor in front of the exponent. The order of our subexponential factor is Ω(N-0.5(1+ε+ρR*)) for any ϵ > 0, where ρR* is the left derivative of the sphere-packing exponent at rate R and N is the blocklength.

We consider block codes whose rate converges to the channel capacity with increasing blocklength at a certain speed and examine the best possible decay of the probability of error. For discrete memoryless channels, we prove that a moderate deviation principle holds for all convergence rates between the large deviation and the central limit theorem regimes.

The problem of deriving refined bounds on the sub-exponential factor in the random coding bound for discrete memoryless channels is considered. In particular, for independent identically distributed random code ensembles and for rates above the critical rate, we prove that if a regularity condition is satisfied (respectively, not satisfied), then for any ε > 0 a sub-exponential factor of O(N-0.5(1-ε+ρ̅*R(respectively, O(N-0.5)) is achievable, where N and R are the blocklength and rate, respectively. The term ρ̅*Ris related to the slope of the random coding exponent at rate R.

For the problem of lossless compression of a memoryless source, we give a detailed, precise characterization of the best achievable error probability, in the “moderate error probability” regime. This is the asymptotic setting where the probability of error decays to zero while at the same time the rate converges to the entropy at a speed no faster than 1/√N. These results combine some of the essential benefits of earlier analyses in terms of error exponents and of Gaussian approximation. Analogous results for the problem of hypothesis testing are also established.

It is observed that some communication situations fall into the large alphabet setting, in which the number of channel parameters and the number of channel uses are both large. To model such situations, we consider Discrete Memoryless Channels (DMCs) in which the input and output alphabet sizes increase along with the block length n. For known channels, we show that reliable communication at the sequence of channel capacities is possible if and only if the minimum between the square logarithms of the input and the output alphabet sizes grows sublinearly with n. For unknown channels with feedback, we show that universal channel coding can be supported if the input-output product alphabet size grows sublinearly with n.

The problem of general index coding with side information is investigated for the case of three receivers. We view the problem as a special case of lossy source coding with side information at the decoders, and we find the optimal rate.

Given training sequences generated by two distinct, but unknown, distributions on a common alphabet, we study the problem of determining whether a third sequence was generated according to the first or second distribution. To model sources such as natural language, for which the underlying distributions are difficult to learn from realistic amounts of data, we allow the alphabet size to grow and therefore the probability distributions to change with the block length. Our primary focus is the situation in which the underlying probabilities are all of the same order, and in this regime, we show that consistent classification is possible if and only if the alphabet grows subquadratically with the block length. We also show that some commonly used statistical tests are suboptimal in that they are consistent only if the alphabet grows sublinearly.

We provide a refinement of the sphere-packing bound for constant composition codes over discrete memoryless channels that improves the pre-factor in front of the exponential term. The order of our pre-factor is O(N-1/2(1+ρ*R)), where ρ*Ris related to the slope of the sphere-packing exponent and N is the blocklength.

A binary erasure version of -channel multiple descriptions (MD) with symmetric descriptions (i.e., the rates of the descriptions are equal and the distortion constraint depends only on the number of messages received) is considered. No excess rate for every out of descriptions, i.e., any messages have sum rate , where is Shannon's rate-distortion function for erasure distortion and is the distortion constraint to be met, is investigated. The goal is to characterize the achievable distortions . Reconstruction fidelity is measured using two criteria: a worst-case criterion which computes distortion by maximizing the per-letter distortion over all source sequences, and an average-case criterion which computes distortion by averaging the per-letter distortion over all source sequences. Achievability schemes are presented, based on systematic maximum distance separable codes for worst-case distortion and random binning for average-case distortion, and optimality results are proved for the corresponding distortion regions. The erasure MD setup is then used to propose a layered coding framework for multiple descriptions, which is then applied to vector Gaussian MD and shown to be optimal for symmetric scalar Gaussian MD with two levels of receivers and no excess rate at the central receiver.

Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case of a deterministic channel input, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability. The results are illustrated with several nonergodic examples.

We study error exponents for source coding with side information. Both achievable exponents and converse bounds are obtained for the following two cases: lossless source coding with coded information and lossy source coding with full side information (Wyner-Ziv). These results recover and extend several existing results on source-coding error exponents and are tight in some circumstances. Our bounds have a natural interpretation as a two-player game between nature and the code designer, with nature seeking to minimize the exponent and the code designer seeking to maximize it. In the Wyner-Ziv problem, our analysis exposes a tension in the choice of test channel with the optimal test channel balancing two competing error events. The Gaussian and binary-erasure cases are examined in detail.

Optical and near-optical band communication systems are known to be intrinsically more secure than comparable RF channels, due to their narrow beamwidths and, in some cases, their high atmospheric absorption. The use of coding against wiretapping for such channels is investigated. For the degraded Poisson wiretap channel model, the secrecy capacity is determined exactly. Moreover, a complete characterization of the rate-equivocation region is presented. For achievability, an optimal code is constructed explicitly by using a code designed by Wyner for the Poisson channel. The converse is proved in two ways: the first method leverages the low-SNR nature of the channel and relies only on simple properties of conditional expectation and classical information inequalities. The second method uses a link recently established between minimum mean square error estimation and mutual information over Poisson channels.

We determine the rate region of the Gaussian one-helper source-coding problem in which the helper observes a scalar, the main encoder observes a vector, and the distortion constraint is a positive semidefinite upper bound on the error covariance matrix of the main source. The rate region is achieved by a Gaussian achievable scheme. We introduce a novel outer bounding technique to establish the converse. Our approach is to create a reduced dimensional problem by projecting the main source and the distortion constraint in certain directions determined by the optimal Gaussian scheme. We also provide an outer bound to the rate region of the more general problem in which there are distortion constraints on both sources. This outer bound is partially tight in general and completely tight in some nontrivial cases.

We study a hypothesis testing problem in which data are compressed distributively and sent to a detector that seeks to decide between two possible distributions for the data. The aim is to characterize all achievable encoding rates and exponents of the type 2 error probability when the type 1 error probability is at most a fixed value. For related problems in distributed source coding, schemes based on random binning perform well and are often optimal. For distributed hypothesis testing, however, the use of binning is hindered by the fact that the overall error probability may be dominated by errors in the binning process. We show that despite this complication, binning is optimal for a class of problems in which the goal is to “test against conditional independence.” We then use this optimality result to give an outer bound for a more general class of instances of the problem.

The vacationing chief executive officer (CEO) problem combines the salient features of the so-called CEO problem and the multiple-description (MD) problem. In this setting, noisy versions of a source are observed by two encoders, as in the CEO problem. In addition, we require that each encoder generate MDs of the source, as in the MD problem. The vacationing-CEO problem arises in asynchronous multicast networks, and solving it is an essential step in developing a general theory for multiencoder and multidecoder lossy compression. In this paper, an achievable sum rate and two sum rate lower bounds are presented for the quadratic Gaussian vacationing-CEO problem. These bounds exactly determine the optimal sum rate over a wide range of parameters.

We study a problem in which a source is encoded into n packets, any t of which may be altered in an arbitrary way by Byzantine adversaries. The decoder receives the n packets and, without knowing which packets were altered, seeks to reconstruct the original source to meet a distortion constraint. We examine a layered architecture for this problem that separates the lossy compression from the coding for adversarial errors. We show that this architecture is optimal in the binary-Hamming and quadratic-Gaussian cases yet suboptimal in general. Our optimality proofs use characterizations of the size of a maximal set with a given diameter in Hamming and Euclidean spaces.

We study the tradeoff between delay and partial reconstruction in peer-to-peer networks, i.e., the number of messages a peer must obtain to reconstruct a given fraction of the file. We present a coding scheme based on erasure compression and Slepian-Wolf binning, in which peers generate coded messages based on their current knowledge of the file. Assuming symmetric peers, we show that the coding scheme provides a Pareto optimal tradeoff between delay and reconstruction, which we characterize. In the process of proving the result, we establish an improved outer bound on the rate region of the general multi-terminal source coding problem. We further show that in the case of asymmetric peers, the coding scheme is not optimal.

We provide a novel upper-bound on Witsenhausen's rate, the rate required in the zero-error analogue of the Slepian-Wolf problem. Our bound is given in terms of a new information-theoretic functional defined on a certain graph and is derived by upper bounding complementary graph entropy. We use the functional, along with graph entropy, to give a single letter lower-bound on the error exponent for the Slepian-Wolf problem under the vanishing error probability criterion, where the decoder has full (i.e., unencoded) side information. We demonstrate that our error exponent can beat the “expurgated” source-coding exponent of Csiszár and Körner for some sources that have zeroes in the “channel” matrix connecting the source with the side information. An extension of our scheme to the lossy case (i.e., Wyner-Ziv) is given. For the case in which the side information is a deterministic function of the source, the exponent of our improved scheme agrees with the sphere-packing bound exactly (thus determining the reliability function). An application of our functional to zero-error channel capacity is also given.

Distributed compression of a pair of Gaussian sources in which the goal is to reproduce a linear function of the sources at the decoder is considered. It has recently been noted that lattice codes can provide improved compression rates for this problem compared to conventional, unstructured codes. It is first shown that the state-of-the-art lattice scheme can be improved by including an additional linear binning stage. An outer bound on the rate-distortion region and a separate lower bound on the optimal sum rate are then established. The outer bound implies that for the special case of communicating the difference of two positively correlated Gaussian sources, the unimproved lattice scheme achieves within one bit of the rate region at any distortion level. The sum rate lower bound implies that unstructured codes achieve within one bit of the optimal sum rate whenever the weights of the two sources in the linear combination differ by more than a factor of two.

We describe a scheme for rate-distortion with distributed encoding in which the sources to be compressed contain a common component. We show that this scheme is optimal in some situations and that it strictly improves upon existing schemes, which do not make full use of common components. This establishes that independent quantization followed by independent binning is not optimal for the two-encoder problem with a distortion constraint on one source. We also show that independent quantization and binning is suboptimal for the three-encoder problem in which the goal is to reproduce one of the sources losslessly. This provides a counterexample that is fundamentally different from one provided earlier by Körner and Marton. The proofs rely on the binary analogue of the entropy power inequality and the existence of a rate loss for the binary symmetric Wyner-Ziv problem.

We address the problem of estimating the probability of an observed string that is drawn i.i.d. from an unknown distribution. Motivated by models of natural language, we consider the regime in which the length of the observed string and the size of the underlying alphabet are comparably large. In this regime, the maximum likelihood distribution tends to overestimate the probability of the observed letters, so the Good–Turing probability estimator is typically used instead. We show that when used to estimate the sequence probability, the Good–Turing estimator is not consistent in this regime. We then introduce a novel sequence probability estimator that is consistent. This estimator also yields consistent estimators for other quantities of interest and a consistent universal classifier.

Moderate deviation behavior of coding for discrete-memoryless channels is investigated. That is, we consider block codes whose rate converges to the channel capacity from below with increasing block length with a certain rate and examine the best ‘sub-exponential’ decay in the maximal probability of error. We prove that a moderate deviation principle (M.D.P.) holds for all convergence rates between the large deviation and the central limit theorem regimes, under some mild assumptions on the channel. The rate function of the M.D.P. is explicitly characterized.

Given training sequences generated by two distinct, but unknown distributions sharing a common alphabet, we seek a classifier that can correctly decide whether a third test sequence is generated by the first or second distribution using only the training data. To model `limited learning' we allow the alphabet size to grow and therefore probability distributions to change with the blocklength. We prove that a natural choice, namely a generalized likelihood ratio test, is universally consistent (has a probability of error tending to zero with the blocklength for all underlying distributions) when the alphabet size is sub-linear in the blocklength, but inconsistent for linear alphabet growth. For up-to quadratic alphabet growth, in a regime where all probabilities are of the same order, we prove the universally consistency of a new test and show there are no such tests when the alphabet grows quadratically or faster.

Providing security guarantees for the information “traveling” through the air is of critical importance for today's applications. Previous research concentrated on studying this problem when the medium used for communication is radio frequency (RF) channels. However, providing security guarantees on RF channels is a complicated task as RF channels' conditions are prone to rapid variations due small scale fading and at a given moment it is difficult to predict which of the main or wiretapper's channel has a better quality. Wireless optical communication is inherently more secure than regular RF communication. Despite this fact, optical communication is not completely immune against wiretapping and signal interception. The purpose of this paper is to study the secrecy capacity of a direct detection optical communication system. For the degraded Poisson wiretap channel, we give a complete characterization of the secrecy capacity in terms of the system parameters.

We determine the rate region of the Gaussian scalar-help-vector source-coding problem under a covariance matrix distortion constraint. The rate region is achieved by a Gaussian achievable scheme. We introduce a novel lower bounding technique to establish the converse of the main result. Our approach is based on lower bounding the problem with a potentially reduced dimensional problem by projecting the main source and imposing the distortion constraint in certain directions determined by the optimal Gaussian scheme. We also provide several properties that the optimal solution to the point-to-point rate-distortion problem for a vector Gaussian source under a covariance matrix distortion constraint satisfies. These properties play an important role in our converse proof.

This paper studies a class of source coding problems that combines elements of the CEO problem with the multiple description problem. In this setting, noisy versions of one remote source are observed by two nodes with encoders (which is similar to the CEO problem). However, it differs from the CEO problem in that each node must generate multiple descriptions of the source. This problem is of interest in multiple scenarios in efficient communication over networks. In this paper, an achievable region and an outer bound are presented for this problem, which is shown to be sum rate optimal for a class of distortion constraints.

Jointly Gaussian memoryless sources are observed atNdistinct terminals. The goal is to efficiently encode the observations in a distributed fashion so as to enable reconstruction of any one of the observations, say the first one, at the decoder subject to a quadratic fidelity criterion. Our main result is aprecisecharacterization of the rate-distortion region when the covariance matrix of the sources satisfies a ¿tree-structure¿ condition. In this situation, a natural analog-digital separation scheme optimally trades off the distributed quantization rate tuples and the distortion in the reconstruction: each encoder consists of a point-to-point Gaussian vector quantizer followed by a Slepian-Wolf binning encoder. We also provide a partial converse that suggests that the tree-structure condition is fundamental.

We consider a binary erasure version of the n-channel multiple descriptions problem with no excess rate and no distortion for every k out of n descriptions, i.e., any subset of k messages has a total rate of one and allows for perfect reconstruction of the source. Using a worst-case distortion criterion, we present an explicit coding scheme based on Reed-Solomon codes and, for any n and k, characterize its achievable distortion region when m < k messages are received at the decoder. We prove that this scheme is Pareto optimal in the achievable distortions for all n and k for any number of received messages at the decoder, and is optimal for all n and k when a single message is received. We also provide optimality results for a certain range of values of n and k.

We provide new achievable error exponents for the problem of source coding with full side information at the decoder. In some instances our exponent strictly improves upon the previous applicable results of Csiszar; Oohama and Han; and the ldquoexpurgatedrdquo exponent of Csiszar and Korner. Our improvement follows from studying the growth rate of the chromatic number of strong (and) product graphs via a new information-theoretic functional on a graph. We also give an upper bound on Witsenhausen's rate, i.e. the zero error rate for the problem of source coding with full side information at the decoder. An application of our functional to zero-error channel capacity is also given.

We study the vector Gaussian versions of two problems: hypothesis testing under a communication constraint and the lossy one-helper problem. In the hypothesis testing problem, a test against independence is considered when a vector Gaussian source is available at the detector which receives a message about another vector Gaussian source at a specified rate. Two equivalent characterizations of the optimal type 2 error exponent are given when the type 1 error is at most a fixed constant. The first characterization is based on enhancement technique introduced by Weingarten et. al. and the other is transform-based. The transform-based characterization directly yields a water pouring interpretation, and establishes successive refinability. For the lossy one-helper problem, we determine a portion of the boundary of the rate region.

We consider a binary erasure version of the n-channel multiple descriptions problem with no excess rate and no distortion for every k out of n descriptions, i.e., any subset of k messages has a total rate of one and allows for perfect reconstruction of the source. We present an achievability scheme and characterize its distortion when mkles 1/2 and a single message is received. For the case where k = 2, n > 3 and a single message is received, we provide a lower bound that differs by exactly 1/n from the minimum distortion achieved by the scheme.

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.

For a general class of Gaussian network source coding problems for which no single-letter characterization of the rate-distortion region is known, it is shown that the rate- distortion region is inner semicontinuous with respect to the source distribution. This semicontinuity theorem is used to obtain two new results, one for the Gaussian many-help-one problem and one for the Gaussian robust distributed source coding problem.

We consider the quadratic Gaussian Wyner-Ziv problem, i.e., the problem of lossy compression of a Gaussian source with Gaussian side information at the decoder and a quadratic distortion measure. Motivated by applications in video coding, we study how to minimize the probability that the distortion exceeds a given threshold, as opposed to the conventional approach of minimizing the average distortion. We obtain an achievable exponent for this problem, which is positive above the rate distortion function, and expose a tension in the choice of the test channel; the optimal test channel balances two competing error events.

We prove a new outer bound on the rate–distortion region for the multiterminal source-coding problem. This bound subsumes the best outer bound in the literature and improves upon it strictly in some cases. The improved bound enables us to obtain a new, conclusive result for the binary erasure version of the “CEO problem.” The bound recovers many of the converse results that have been established for special cases of the problem, including the recent one for the Gaussian two-encoder problem.

We determine the rate region of the quadratic Gaussian two-encoder source-coding problem. This rate region is achieved by a simple architecture that separates the analog and digital aspects of the compression. Furthermore, this architecture requires higher rates to send a Gaussian source than it does to send any other source with the same covariance. Our techniques can also be used to determine the sum-rate of some generalizations of this classical problem. Our approach involves coupling the problem to a quadratic Gaussian ldquoCEO problem.rdquo

We consider the problem of estimating the probability of an observed string drawn i.i.d. from an unknown distribution. The key feature of our study is that the length of the observed string is assumed to be of the same order as the size of the underlying alphabet. In this setting, many letters are unseen and the empirical distribution tends to overestimate the probability of the observed letters. To overcome this problem, the traditional approach to probability estimation is to use the classical Good-Turing estimator. We introduce a natural scaling model and use it to show that the Good-Turing sequence probability estimator is not consistent. We then introduce a novel sequence probability estimator that is indeed consistent under the natural scaling model.

We determine the rate region of the quadratic Gaussian two-encoder source-coding problem with separate distortion constraints. This region is achieved by a simple architecture that separates the analog and digital aspects of the compression. Furthermore, this architecture requires higher rates to send a Gaussian source than it does to send any other source with the same covariance. The proof technique can be used to partially solve problems with more than two encoders or more general distortion constraints

We consider the problem of estimating the total probability of all symbols that appear with a given frequency in a string of i.i.d. random variables with unknown distribution. We focus on the regime in which the block length is large yet no symbol appears frequently in the string. This is accomplished by allowing the distribution to change with the block length. Under a natural convergence assumption on the sequence of underlying distributions, we show that the total probabilities converge to a deterministic limit, which we characterize. We then show that the good-turing total probability estimator is strongly consistent

We prove a new outer bound on the rate-distortion region for the multiterminal source-coding problem. This bound subsumes the best known bound in the literature and improves upon it strictly in some cases. The improved bound enables us to obtain a new, conclusive result for the binary-erasure instance of the "CEO problem." The bound recovers many of the converse results that have been established for special cases of the problem, including the recent one for the Gaussian version of the CEO problem

We determine the reliability function of the exponential-server timing channel (ESTC) in the limit as the data rate approaches zero. The limit shows that at low rates, the ESTC is strictly more reliable than the Poisson channel without dark current, answering a question Arikan posed in these Transactions. The proof employs a distance metric over inputs to timing channels that parallels Euclidean and Hamming distance for conventional channels. A consequence of the proof is that bounded-distance decoding, with distance measured according to this metric, is exponentially optimum for the ESTC in the low-rate regime. We also prove the straight-line bound for the channel and a bound on the reliability of timing channels with general service distributions in the limit as the data rate approaches zero.

The ideal Poisson channel, the ideal Poisson channel with feedback, the exponential-server timing channel, and the exponential-server timing channel with feedback are known to have the same capacity. We show that above this capacity they have the same reliability function, which we determine. For the ideal Poisson channel without feedback, this improves upon the strong converse of Burnashev and Kutoyants.

We exhibit upper and lower bounds on the pairwise error probability of the exponential-server timing channel in terms of an appropriately-defined distance between codewords. We show that this distance plays a crucial role in determining the reliability function at low rates. In particular, by lower bounding the minimum distance of good-low rates codes, we provide an improved lower bound on the reliability function of the channel at rate zero. This improved bound proves that at low rates, the exponential-server timing channel is strictly more reliable than the related Poisson channel with zero dark current, answering an open question posed by Arikan. Some remarks are also made about using the results of this paper to prove an improved upper bound on the reliability function at rate zero.