This work explores properties of Strong Data-Processing constants for Rényi Divergences. Parallels are made with the well-studied $φ$-Divergences, and it is shown that the order $α$ of Rényi Divergences dictates whether certain properties of the contraction of $φ$-Divergences are mirrored or not. In particular, we demonstrate that when $α>1$, the contraction properties can deviate quite strikingly from those of $φ$-Divergences. We also uncover specific characteristics of contraction for the $\infty$-Rényi Divergence and relate it to $\varepsilon$-Local Differential Privacy. The results are then applied to bound the speed of convergence of Markov chains, where we argue that the contraction of Rényi Divergences offers a new perspective on the contraction of $L^α$-norms commonly studied in the literature.

Information measures can be constructed from Rényi divergences much like mutual information from Kullback-Leibler divergence. One such information measure is known as Sibson α-mutual information and has received renewed attention recently in several contexts: concentration of measure under dependence, statistical learning, hypothesis testing, and estimation theory. In this paper, we survey and extend the state of the art. In particular, we introduce variational representations for Sibson α-mutual information and employ them in each described context to derive novel results. Namely, we produce generalized Transportation-Cost inequalities and Fano-type inequalities. We also present an overview of known applications, spanning from learning theory and Bayesian risk to universal prediction.

Learning discrete distributions from i.i.d. samples is a well-understood problem. However, advances in generative machine learning prompt an interesting new, non-i.i.d. setting: after receiving a certain number of samples, an estimated distribution is fixed, and samples from this estimate are drawn and introduced into the sample corpus, undifferentiated from real samples. Subsequent generations of estimators now face contaminated environments, a scenario referred to in the machine learning literature as self-consumption. Empirically, it has been observed that models in fully synthetic self-consuming loops collapse—their performance deteriorates with each batch of training—but accumulating data has been shown to prevent complete degeneration. This, in turn, begs the question: What happens when fresh real samplesareadded at every stage? In this paper, we study the minimax loss of self-consuming discrete distribution estimation in such loops. We show that even when model collapse is consciously averted, the ratios between the minimax losses with and without source information can grow unbounded as the batch size increases. In the data accumulation setting, where all batches of samples are available for estimation, we provide minimax lower bounds and upper bounds that are order-optimal under mild conditions for the expected ℓ22and ℓ1losses at every stage. We provide conditions for regimes where there is a strict gap in the convergence rates compared to the corresponding oracle-assisted minimax loss where real and synthetic samples are differentiated, and provide examples where this gap is easily observed. We also provide a lower bound on the minimax loss in the data replacement setting, where only the latest batch of samples is available, and use it to find a lower bound for the worst-case loss for bounded estimate trajectories.

Attention-based transformers have achieved tremendous success across a variety of disciplines including natural languages. To deepen our understanding of their sequential modeling capabilities, there is a growing interest in using Markov input processes to study them. A key finding is that when trained on first-order Markov chains, transformers with two or more layers consistently develop an induction head mechanism to estimate the in-context bigram conditional distribution. In contrast, single-layer transformers, unable to form an induction head, directly learn the Markov kernel but often face a surprising challenge: they become trapped in local minima representing the unigram distribution, whereas deeper models reliably converge to the ground-truth bigram. While single-layer transformers can theoretically model first-order Markov chains, their empirical failure to learn this simple kernel in practice remains a curious phenomenon. To explain this contrasting behavior of single-layer models, in this paper we introduce a new framework for a principled analysis of transformers via Markov chains. Leveraging our framework, we theoretically characterize the loss landscape of single-layer transformers and show the existence of global minima (bigram) and bad local minima (unigram) contingent on data properties and model architecture. We precisely delineate the regimes under which these local optima occur. Backed by experiments, we demonstrate that our theoretical findings are in congruence with the empirical results. Finally, we outline several open problems in this arena.

This paper considers the sample-efficiency of preference learning, which models and predicts human choices based on comparative judgments. The minimax optimal estimation error rate $\Theta(d/n)$ in classical estimation theory requires that the number of samples $n$ scales linearly with the dimensionality of the feature space $d$. However, the high dimensionality of the feature space and the high cost of collecting human-annotated data challenge the efficiency of traditional estimation methods. To remedy this, we leverage sparsity in the preference model and establish sharp error rates. We show that under the sparse random utility model, where the parameter of the reward function is $k$-sparse, the minimax optimal rate can be reduced to $\Theta(k/n \log(d/k))$. Furthermore, we analyze the $\ell_{1}$-regularized estimator and show that it achieves near-optimal rate under mild assumptions on the Gram matrix. Experiments on synthetic data and LLM alignment data validate our theoretical findings, showing that sparsity-aware methods significantly reduce sample complexity and improve prediction accuracy.

Learning discrete distributions from i.i.d. samples is a well-understood problem. However, advances in generative machine learning prompt an interesting new, non-i.i.d. setting: after receiving a certain number of samples, an estimated distribution is fixed, and samples from this estimate are drawn and introduced into the sample corpus, undifferentiated from real samples. Subsequent generations of estimators now face contaminated environments, a scenario referred to in the machine learning literature as self-consumption. Empirically, it has been observed that models in fully synthetic self-consuming loops collapse-their performance deteriorates with each batch of training-but accumulating data has been shown to prevent complete degeneration. This, in turn, begs the question: What happens when fresh real samples are added at every stage? In this paper, we study the minimax loss of self-consuming discrete distribution estimation in such loops. We show that even when model collapse is consciously averted, the ratios between the minimax losses with and without source information can grow unbounded as the batch size increases. In the data accumulation setting, where all batches of samples are available for estimation, we provide minimax lower bounds and upper bounds that are order-optimal under mild conditions for the expected$\ell_{2}^{2}$and$\ell_{1}$losses at every stage. We provide conditions and examples for regimes where there is a strict gap in the convergence rates compared to the corresponding oracle-assisted minimax loss where real and synthetic samples are differentiated. We also provide a lower bound on the minimax loss in the data replacement setting, where only the latest batch of samples is available, and use it to find a lower bound for the worst-case loss for bounded estimate trajectories.

We derive a conditional version of the classical regret-capacity theorem. This result can be used in universal prediction to find lower bounds on the minimal batch regret, which is a recently introduced generalization of the average regret, when batches of training data are available to the predictor. As an example, we apply this result to the class of binary memoryless sources. Finally, we generalize the theorem to Rényi information measures, revealing a deep connection between the conditional Rényi divergence and the conditional Sibson’s mutual information.

In-context learning (ICL) is a hallmark capability of transformers, through which trained models learn to adapt to new tasks by leveraging information from the input context. Prior work has shown that ICL emerges in transformers due to the presence of special circuits called induction heads. Given the equivalence between induction heads and conditional $k$-grams, a recent line of work modeling sequential inputs as Markov processes has revealed the fundamental impact of model depth on its ICL capabilities: while a two-layer transformer can efficiently represent a conditional $1$-gram model, its single-layer counterpart cannot solve the task unless it is exponentially large. However, for higher order Markov sources, the best known constructions require at least three layers (each with a single attention head) - leaving open the question: *can a two-layer single-head transformer represent any $k^{\text{th}}$-order Markov process?* In this paper, we precisely address this and theoretically show that a two-layer transformer with one head per layer can indeed represent any conditional $k$-gram. Thus, our result provides the tightest known characterization of the interplay between transformer depth and Markov order for ICL. Building on this, we further analyze the learning dynamics of our two-layer construction, focusing on a simplified variant for first-order Markov chains, illustrating how effective in-context representations emerge during training. Together, these results deepen our current understanding of transformer-based ICL and illustrate how even shallow architectures can surprisingly exhibit strong ICL capabilities on structured sequence modeling tasks.

We study which machine learning algorithms have tight generalization bounds with respect to a given collection of population distributions. Our results build on and extend the recent work of Gastpar et al. (2023). First, we present conditions that preclude the existence of tight generalization bounds. Specifically, we show that algorithms that have certain inductive biases that cause them to be unstable do not admit tight generalization bounds. Next, we show that algorithms that are sufficiently loss-stable do have tight generalization bounds. We conclude with a simple characterization that relates the existence of tight generalization bounds to the conditional variance of the algorithm's loss.

Tokenization efficiency plays a critical role in the performance and cost of large language models (LLMs), yet most models rely on static tokenizers optimized on general-purpose corpora. These tokenizers’ fixed vocabularies often fail to adapt to domain- or language-specific inputs, leading to longer token sequences and higher computational costs. We introduce zip2zip, a novel method for achieving context-adaptive tokenization in LLMs at inference time. Leveraging an online data compression algorithm (Lempel–Ziv–Welch), zip2zip dynamically expands its active vocabulary at inference time by continuously replacing fragmented token sequences with more compact hypertokens, which it can immediately output during generation. In doing so, the model refines its internal tokenization scheme to match the token distribution of the current context, reducing redundancy and improving representational efficiency. zip2zip consists of three key components: (1) a tokenizer based on Lempel–Ziv–Welch compression that incrementally merges co-occurring tokens into reusable hypertokens on the fly; (2) a dynamic embedding (and unembedding) layer that computes embeddings for newly formed hypertokens at runtime; and (3) a variant of autoregressive language modeling that pretrains the model to handle hypertokenized, compressed text sequences as inputs and outputs. We show that an existing LLM can be uptrained for zip2zip in 10 GPU-hours via parameter-efficient finetuning. The resulting LLM performs test-time adaptation, learning to use hypertokens in unseen contexts and reducing input and output tokens by 15–40%. Code and models are released at https://github.com/epfl-dlab/zip2zip.

Inspired by the connection between classical regret measures employed in universal prediction and Rényi divergence, we introduce a new class of universal predictors that depend on a real parameter$\alpha \geq 1$. This class interpolates two well-known predictors, the mixture estimators, that include the Laplace and the Krichevsky-Trofimov predictors, and the Normalized Maximum Likelihood (NML) estimator. We point out some advantages of this new class of predictors and study its benefits from two complementary viewpoints: 1) we prove its optimality when the maximal Rényi divergence is considered as a regret measure, which can be interpreted operationally as a middle ground between the standard average and worst-case regret measures; 2) we discuss how it can be employed when NML is not a viable option, as an alternative to other predictors such as Luckiness NML. Finally, we apply the$\alpha $-NML predictor to the class of discrete memoryless sources (DMS), where we derive simple formulas to compute the predictor and analyze its asymptotic performance in terms of worst-case regret.

We study communication over a Gaussian multiple-access channel (MAC) with two types of transmitters: Digital transmitters hold a message from a discrete set that needs to be communicated to the receiver with vanishing error probability. Analog transmitters hold sequences of analog values. Some functions of these distributed values (but not the values themselves) need to be conveyed to the receiver, subject to a fidelity criterion such as mean squared error (MSE) or a certain maximum error with given confidence. For the case in which the computed function for the analog transmitters is a sum of values in$[-1,1]$, we derive inner and outer bounds for the tradeoff of digital and analog rates of communication under peak and average power constraints for digital transmitters and a peak power constraint for analog transmitters. We then extend the achievability result to a class of functions that includes all linear and some non-linear functions. This extended scheme works over fading channels as long as full channel state information is available at the transmitter. The practicality of our proposed communication scheme is shown in channel simulations that use a version of the scheme based on low density parity check (LDPC) coding. We evaluate the system performance for different block lengths and Gaussian as well as non-Gaussian noise distributions.

We study the notion of a generalization bound being _uniformly tight_, meaning that the difference between the bound and the population loss is small for all learning algorithms and all population distributions. Numerous generalization bounds have been proposed in the literature as potential explanations for the ability of neural networks to generalize in the overparameterized setting. However, in their paper "Fantastic Generalization Measures and Where to Find Them," Jiang et al. (2020) examine more than a dozen generalization bounds, and show empirically that none of them are uniformly tight. This raises the question of whether uniformly-tight generalization bounds are at all possible in the overparameterized setting. We consider two types of generalization bounds: (1) bounds that may depend on the training set and the learned hypothesis (e.g., margin bounds). We prove mathematically that no such bound can be uniformly tight in the overparameterized setting; (2) bounds that may in addition also depend on the learning algorithm (e.g., stability bounds). For these bounds, we show a trade-off between the algorithm's performance and the bound's tightness. Namely, if the algorithm achieves good accuracy on certain distributions, then no generalization bound can be uniformly tight for it in the overparameterized setting. We explain how these formal results can, in our view, inform research on generalization bounds for neural networks, while stressing that other interpretations of these results are also possible.

Data-parallel SGD is the de facto algorithm for distributed optimization, especially for large scale machine learning. Despite its merits, communication bottleneck is one of its persistent issues. Most compression schemes to alleviate this either assume noiseless communication links, or fail to achieve good performance on practical tasks. In this paper, we close this gap and introduce **LASER**: **L**ine**A**r Compre**S**sion in Wir**E**less Dist**R**ibuted Optimization. LASER capitalizes on the inherent low-rank structure of gradients and transmits them efficiently over the noisy channels. Whilst enjoying theoretical guarantees similar to those of the classical SGD, LASER shows consistent gains over baselines on a variety of practical benchmarks. In particular, it outperforms the state-of-the-art compression schemes on challenging computer vision and GPT language modeling tasks. On the latter, we obtain 50-64% improvement in perplexity over our baselines for noisy channels.

The promise of least-privilege learning – to find feature representations that are useful for a learning task but prevent inference of any sensitive information unrelated to this task – is highly appealing. However, so far this concept has only been stated informally. It thus remains an open question whether and how we can achieve this goal. In this work, we provide the first formalisation of the least-privilege principle for machine learning and characterise its feasibility. We prove that there is a fundamental trade-off between a representation’s utility for a given task and its leakage beyond the intended task: it is not possible to learn representations that have high utility for the intended task but, at the same time, prevent inference of any attribute other than the task label itself. This trade-off holds regardless of the technique used to learn the feature mappings that produce these representations. We empirically validate this result for a wide range of learning techniques, model architectures, and datasets.

Large language models (LLMs) have recently gained much popularity due to their surprising ability at generating human-like English sentences. LLMs are essentially predictors, estimating the probability of a sequence of words given the past. Therefore, it is natural to evaluate their performance from a universal prediction perspective. In order to do that fairly, we introduce the notion of batch regret as a modification of the classical average regret, and we study its asymptotical value for add-constant predictors, in the case of memoryless sources and first-order Markov sources.

Sibson's$\alpha$-mutual information has received renewed attention recently in several contexts: concentration of measure under dependence, statistical learning, hypothesis testing, and estimation theory. In this work, we introduce several variational representations of Sibson's$\alpha$-mutual information: 1) as a supremum over joint distributions of (a combination of) KL divergences; and 2) as a supremum over functions of opportune expected values. Leveraging them, we produce a variety of novel and known results, including a generalization of transportation-cost inequalities and Fano's inequality.

We study communication over a Gaussian multiple-access channel (MAC) with two types of transmitters: Digital transmitters hold a message from a discrete set that needs to be communicated to the receiver. Analog transmitters hold sequences of analog values, and some function of these distributed values (but not the values themselves) need to be conveyed to the receiver. For the digital messages, it is required that they can be decoded error free at the receiver with high probability while the recovered analog function values have to satisfy a fidelity criterion such as an upper bound on mean squared error (MSE) or a certain maximum error with a given confidence. For the case in which the computed function for the analog transmitters is a sum of values in [-1, 1], we derive inner and outer bounds for the tradeoff of digital and analog rates of communication under peak and average power constraints for digital transmitters and a peak power constraint for analog transmitters. We then extend the achievability part of our result to a larger class of functions that includes all linear, but also some non-linear functions.

When a delivery agency persuades a bicycle courier worker to accept a certain job, it does so by revealing the right amount and kind of information. The goal is to reward both the agent as well as the worker accordingly. In this paper, we model the act of persuasion in information-theoretic terms. The main emphasis is on an approach inspired by the so-called information bottleneck problem. We derive results about the structure of the resulting optimization problem and present solutions for certain special cases. An algorithmic perspective is also developed, with potential applications in learning. Finally, we outline an alternative complementary problem formulation leveraging remote rate-distortion theory.

Strong data processing inequalities (SDPI) are an important object of study in Information Theory and have been well studied for$f$-divergences. Universal upper and lower bounds have been provided along with several applications, connecting them to impossibility (converse) results, concentration of measure, hypercontractivity, and so on. In this paper, we study Renyi divergence and the corresponding SDPI constant whose behavior seems to deviate from that of ordinary-divergences. In particular, one can find examples showing that the universal upper bound relating its SDPI constant to the one of Total Variation does not hold in general. In this work, we prove, however, that the universal lower bound involving the SDPI constant of the Chi-square divergence does indeed hold. Furthermore, we also provide a characterization of the distribution that achieves the supremum when is equal to 2 and consequently compute the SDPI constant for Renyi divergence of the general binary channel.

In recent years, transformer-based models have revolutionized deep learning, particularly in sequence modeling. To better understand this phenomenon, there is a growing interest in using Markov input processes to study transformers. However, our current understanding in this regard remains limited with many fundamental questions about how transformers learn Markov chains still unanswered. In this paper, we address this by focusing on first-order Markov chains and single-layer transformers, providing a comprehensive characterization of the learning dynamics in this context. Specifically, we prove that transformer parameters trained on next-token prediction loss can either converge to global or local minima, contingent on the initialization and the Markovian data properties, and we characterize the precise conditions under which this occurs. To the best of our knowledge, this is the first result of its kind highlighting the role of initialization. We further demonstrate that our theoretical findings are corroborated by empirical evidence. Based on these insights, we provide guidelines for the initialization of single-layer transformers and demonstrate their effectiveness. Finally, we outline several open problems in this arena. Code is available at: \url{https://github.com/Bond1995/Markov}.

We formalize the problem of prompt compression for large language models (LLMs) and present a framework to unify token-level prompt compression methods which create hard prompts for black-box models. We derive the distortion-rate function for this setup as a linear program, and provide an efficient algorithm to compute this fundamental limit via the dual of the linear program. Using the distortion-rate function as the baseline, we study the performance of existing compression schemes on a synthetic dataset consisting of prompts generated from a Markov chain, natural language queries, and their respective answers. Our empirical analysis demonstrates the criticality of query-aware prompt compression, where the compressor has knowledge of the downstream task/query for the black-box LLM. We show that there is a large gap between the performance of current prompt compression methods and the optimal strategy, and propose Adaptive QuerySelect, a query-aware, variable-rate adaptation of a prior work to close the gap. We extend our experiments to a small natural language dataset to further confirm our findings on our synthetic dataset.

Attention-based transformers have been remarkably successful at modeling generative processes across various domains and modalities. In this paper, we study the behavior of transformers on data drawn from $k^{\text{th}}$-order Markov processes, where the conditional distribution of the next symbol in a sequence depends on the previous $k$ symbols observed. We observe a surprising phenomenon empirically which contradicts previous findings: when trained for sufficiently long, a transformer with a fixed depth and $1$ head per layer is able to achieve low test loss on sequences drawn from $k^{\text{th}}$-order Markov sources, even as $k$ grows. Furthermore, this low test loss is achieved by the transformer’s ability to represent and learn the in-context conditional empirical distribution. On the theoretical side, we prove that a transformer with $O(\log_2(k))$ layers can represent the in-context conditional empirical distribution by composing induction heads to track the previous $k$ symbols in the sequence. Surprisingly, with the addition of layer normalization, we show that a transformer with a constant number of layers can represent the in-context conditional empirical distribution, concurring with our empirical observations. This result provides more insight into the benefit of soft-attention and non-linearities in the transformer architecture.

This paper focuses on parameter estimation and introduces a new method for lower bounding the Bayesian risk. The method allows for the use of virtually any information measure, including Rényi's $\alpha$, $\varphi$-divergences, and Sibson's $\alpha$-Mutual Information. The approach considers divergences as functionals of measures and exploits the duality between spaces of measures and spaces of functions. In particular, we show that one can lower bound the risk with any information measure by upper bounding its dual via Markov's inequality. We are thus able to provide estimator-independent impossibility results thanks to the Data-Processing Inequalities that divergences satisfy. The results are then applied to settings of interest involving both discrete and continuous parameters, including the “Hide-and-Seek” problem, and compared to the state-of-the-art techniques. An important observation is that the behaviour of the lower bound in the number of samples is influenced by the choice of the information measure. We leverage this by introducing a new divergence inspired by the “Hockey-Stick” divergence, which is demonstrated empirically to provide the largest lower bound across all considered settings. If the observations are subject to privatisation, stronger impossibility results can be obtained via Strong Data-Processing Inequalities. The paper also discusses some generalisations and alternative directions.

This paper considers the problem of distributed lossy compression where the goal is to recover one or more linear combinations of the sources at the decoder, subject to distortion constraints. For certain configurations, it is known that codes with algebraic structure can outperform i.i.d. codebooks. For the special case of finite-alphabet sources, recent work has demonstrated how to incorporate joint typicality decoding alongside linear encoding and binning. This work takes a discretization approach to extend this rate region to include both integer- and real-valued sources. As a case study, the rate region is evaluated for the Gaussian case. The resulting joint-typicality-based rate region recovers and generalizes the best-known rate region for this scenario, based on lattice encoding and sequential decoding.

One major challenge in distributed learning is to efficiently learn for each client when the data across clients is heterogeneous or non iid (not independent or identically distributed). This provides a significant challenge as the data of the other clients may not be helpful to each individual client. Thus the following question arises - can each individual client’s performance be improved with access to the data of other clients in this heterogeneous data setting? A further challenge is to have a good personalized model while still maintaining the privacy of local data samples.We consider a model where the client data distributions are not identical and can be dependent. In this heterogeneous data setting we study the problem of distributed learning of data distributions. We propose a personalized linear estimator for each client and show that this estimator is never worse and can be substantially better (up to a factor equal to the number of clients) than the sample mean estimator while still concentrating around the true probability. This estimator can be implemented by privacy-preserving schemes in both the cryptographic and differentially private settings.

Compute–forward is a coding technique that enables receiver(s) in a network to directly decode one or more linear combinations of the transmitted codewords. Initial efforts focused on Gaussian channels and derived achievable rate regions via nested lattice codes and single-user (lattice) decoding as well as sequential (lattice) decoding. Recently, these results have been generalized to discrete memoryless channels via nested linear codes and joint typicality coding, culminating in a simultaneous-decoding rate region for recovering one or more linear combinations from$K$users. Using a discretization approach, this paper translates this result into a simultaneous-decoding rate region for a wide class of continuous memoryless channels, including the important special case of Gaussian channels. Additionally, this paper derives a single, unified expression for both discrete and continuous rate regions via an algebraic generalization of Rényi’s information dimension.

Inspired by Sibson’s alpha-mutual information, we introduce a new parametric class of universal predictors. This class interpolates two well-known predictors, the mixture estimator, that includes the Laplace and the Krichevsky-Trofimov predictors, and the Normalized Maximum Likelihood (NML) estimator. We point out some advantages of this class of predictors and study its performance in terms of known regret measures under logarithmic loss, in particular for the well-studied case of discrete memoryless sources.

In this work, we connect the problem of bounding the expected generalisation error with transportation-cost inequalities. Exposing the underlying pattern behind both approaches we are able to generalise them and go beyond Kullback- Leibler Divergences/Mutual Information and sub-Gaussian measures. In particular, we are able to provide a result showing the equivalence between two families of inequalities: one involving functionals and one involving measures. This result generalises the one proposed by Bobkov and Götze that connects transportation-cost inequalities with concentration of measure. Moreover, it allows us to recover all standard generalisation error bounds involving mutual information and to introduce new, more general bounds, that involve arbitrary divergence measures.

We explore a family of information measures that stems from Rényi’s α-Divergences with α < 0. In particular, we extend the definition of Sibson’s α-Mutual Information to negative values of α and show several properties of these objects. Moreover, we highlight how this family of information measures is related to functional inequalities that can be employed in a variety of fields, including lower-bounds on the Risk in Bayesian Estimation Procedures.

We prove that every online learnable class of functions of Littlestone dimension d admits a learning algorithm with finite information complexity. Towards this end, we use the notion of a globally stable algorithm. Generally, the information complexity of such a globally stable algorithm is large yet finite, roughly exponential in d. We also show there is room for improvement; for a canonical online learnable class, indicator functions of affine subspaces of dimension d, the information complexity can be upper bounded logarithmically in d.

The Gray-Wyner network subject to a fidelity criterion is studied. Upper and lower bounds for the trade-offs between the private sum-rate and the common rate are obtained for arbitrary sources subject to mean-squared error distortion. The bounds meet exactly, leading to the computation of the rate region, when the source is jointly Gaussian. They meet partially when the sources are modeled via an additive Gaussian “channel”. The bounds are inspired from the Shannon bounds on the rate-distortion problem.

We consider the problem of parameter estimation in a Bayesian setting and propose a general lower-bound that includes part of the family of f-Divergences. The results are then applied to specific settings of interest and compared to other notable results in the literature. In particular, we show that the known bounds using Mutual Information can be improved by using, for example, Maximal Leakage, Hellinger divergence, or generalizations of the Hockey-Stick divergence.

The increasing prevalence of massive datasets makes the outsourcing of storage and computation tasks to distributed servers a necessity. This raises a number of concerns regarding the security and integrity of stored information, the privacy of accessing desired information, the communication overhead of distributed systems, the latency, reliability, and complexity of distributed computing, and privacy in distributed training and learning systems. Recent breakthroughs from coding, communication, and information-theoretic perspectives have opened up exciting new research avenues for these topics. There are many theoretical and practical open problems. This Special Issue is dedicated to communication theory, coding theory, information theory, signal processing, and networking aspects of privacy in information retrieval, privacy in coded computing over distributed servers, and privacy in distributed learning.

Most of our lives are conducted in the cyberspace. The human notion of privacy translates into a cyber notion of privacy on many functions that take place in the cyberspace. This article focuses on three such functions: how to privately retrieve information from cyberspace (privacy in information retrieval), how to privately leverage large-scale distributed/parallel processing (privacy in distributed computing), and how to learn/train machine learning models from private data spread across multiple users (privacy in distributed (federated) learning). The article motivates each privacy setting, describes the problem formulation, summarizes breakthrough results in the history of each problem, and gives recent results and discusses some of the major ideas that emerged in each field. In addition, the cross-cutting techniques and interconnections between the three topics are discussed along with a set of open problems and challenges.

This paper presents explicit solutions for two related non-convex information extremization problems due to Gray and Wyner in the Gaussian case. The first problem is the Gray-Wyner network subject to a sum-rate constraint on the two private links. Here, our argument establishes the optimality of Gaussian codebooks and hence, a closed-form formula for the optimal rate region. The second problem is Wyner’s common information and a generalization thereof, where conditional independence is generalized to a limit on the conditional mutual information. We present full explicit solutions for the scalar as well as the vector case.

In this work, we consider the problem of parameter estimation in a Bayesian setting. We propose a new approach to lower-bounding the Bayesian risk, based on Sibson's$\alpha$-Mutual Information. The results are then applied to specific settings of interest. As an example, we provide a lower-bound on the risk of the so-called “Hide-and-Seek” problem. Generalisations of the results and alternative directions are also briefly presented.

In this work, we analyse how to define a conditional version of Sibson's$\alpha$-Mutual Information. Several such definitions can be advanced and they all lead to different information measures with different (but similar) operational meanings. We will analyse in detail one such definition, compute a closed-form expression for it and endorse it with an operational meaning while also considering some applications. The alternative definitions will also be mentioned and compared.

We present a novel unified framework of compute-forward achievable rate regions for simultaneous decoding of multiple linear codeword combinations. This framework covers a wide class of discrete and continuous-input channels, and computation over finite fields, integers, and reals. The resulting rate regions recover several well-known achievability results, and in some cases extend them. The framework is built upon a recently established achievable rate region based on linear codes and joint typicality decoding. The latter is extended from finite fields to computation over the integers and, via a discretization approach, to computation over the reals with integer coefficients and continuous inputs. Evaluating the latter with Gaussian distributions, we obtain a closed-form rate region which generalizes the classic compute-forward rates originally derived by means of lattice codes by Nazer and Gastpar.

An important notion of common information between two random variables is due to Wyner. In this paper, we derive a lower bound on a relaxed variant of Wyner's common information for continuous random variables. The new bound reduces to the lower bound on Wyner's common information of Liu (2018). We also show that the new lower bound is tight for a special case of the so-called “Gaussian channels”, namely, when the joint distribution of the random variables can be written as the sum of a single underlying random variable and Gaussian noises. We motivate this work from the recent variations of Wyner's common information and applications to network data compression problems such as the Gray-Wyner network.

This paper considers an additive Gaussian noise channel with arbitrarily distributed finite variance input signals. It studies the differential entropy of the minimum mean-square error (MMSE) estimator and provides a new lower bound which connects the differential entropy of the input, output, and conditional mean. That is, the sum of differential entropies of the conditional mean and output is always greater than or equal to twice the input differential entropy. Various other properties such as upper bounds, asymptotics, Taylor series expansion, and connection to Fisher Information are obtained. An application of the lower bound in the remote-source coding problem is discussed, and extensions of the lower and upper bounds to the vector Gaussian channel are given.

The expected excess risk of a learning algorithm is the average suboptimality of using the learning algorithm, relative to the optimal hypothesis in the hypothesis class. In this work, we lower bound the expected excess risk of a learning algorithm using the mutual information between the input and the noisy output of the learning algorithm. The setting we consider is, where the hypothesis class is the set of real numbers and the true risk function has a local strong convexity property. Our main results also lead to asymptotic lower bounds on the expected excess risk, which do not require the knowledge of the local strong convexity constants of the true risk function.

We consider a setup in which confidential i.i.d. samples $X_1,\dotsc,X_n$ from an unknown finite-support distribution $\boldsymbol{p}$ are passed through $n$ copies of a discrete privatization channel (a.k.a. mechanism) producing outputs $Y_1,\dotsc,Y_n$. The channel law guarantees a local differential privacy of $\epsilon$. Subject to a prescribed privacy level $\epsilon$, the optimal channel should be designed such that an estimate of the source distribution based on the channel outputs $Y_1,\dotsc,Y_n$ converges as fast as possible to the exact value $\boldsymbol{p}$. For this purpose we study the convergence to zero of three distribution distance metrics: $f$-divergence, mean-squared error and total variation. We derive the respective normalized first-order terms of convergence (as $n \to \infty$), which for a given target privacy $\epsilon$ represent a rule-of-thumb factor by which the sample size must be augmented so as to achieve the same estimation accuracy as that of a non-randomizing channel. We formulate the privacy-fidelity trade-off problem as being that of minimizing said first-order term under a privacy constraint $\epsilon$. We further identify a scalar quantity that captures the essence of this trade-off, and prove bounds and data-processing inequalities on this quantity. For some specific instances of the privacy-fidelity trade-off problem, we derive inner and outer bounds on the optimal trade-off curve.

We study the cooperative data exchange problem for fully connected networks. In this problem, nodes make broadcast transmissions to recover a file consisting of K independent packets. Each node initially only possesses a subset of the packets. We propose (d, K)-Basis Searching, a deterministic polynomial-time minimization approach, to calculate the minimum rate for this problem. (d, K)-Basis Searching has strictly reduced complexity compared with the state-of-the-art algorithms, which are based on submodular function minimization. We extend our algorithm to a generalized problem: the so-called successive local omniscience problem.

In this work, the probability of an event under some joint distribution is bounded by measuring it with the product of the marginals instead (which is typically easier to analyze) together with a measure of the dependence between the two random variables. These results find applications in adaptive data analysis, where multiple dependencies are introduced and in learning theory, where they can be employed to bound the generalization error of a learning algorithm. Bounds are given in terms of Sibson's Mutual Information, α-Divergences, Hellinger Divergences, and f-Divergences. A case of particular interest is the Maximal Leakage (or Sibson's Mutual Information of order infinity), since this measure is robust to post-processing and composes adaptively. The corresponding bound can be seen as a generalization of classical bounds, such as Hoeffding's and McDiarmid's inequalities, to the case of dependent random variables.

Given two probability measures P and Q and an event E, we provide bounds on P(E) in terms of Q(E) and f-divergences. In particular, the bounds are instantiated when the measures considered are a joint distribution and the corresponding product of marginals. This allows us to control the measure of an event under the joint, using the product of the marginals (typically easier to compute) and a measure of how much the two distributions differ, i.e., an f-divergence between the joint and the product of the marginals, also known in the literature as f-Mutual Information. The result is general enough to induce, as special cases, bounds involving χ2-divergence, Hellinger distance, Total Variation, etc. Moreover, it also recovers a result involving Rényi's α-divergence. As an application, we provide bounds on the generalization error of learning algorithms via f-divergences.

In the celebrated coded caching problem studied by Maddah-Ali and Niesen, the peak-traffic network load is to be reduced by first caching some information about contents into individual memories of end users during the off-peak hours and then upon user requests broadcasting some other information about the contents, which, combined with cached information, can let each user recover their requested content. Thus, information-theoretic studies of coded caching involve the optimal tradeoff among communication rates for the two phases of cache placement and content delivery, and the optimal construction of codes for cache placement and content delivery. In order to allow better utilization of network resources, this paper introduces a new caching model in which user requests can arise at any point of time during the cache placement phase, and proposes a successive refinement approach as an answer to this dynamic caching problem. For uniformly random file requests, the optimal tradeoff among average-case delivery rates are characterized when the cache rate is above a well-defined threshold. For arbitrary file requests, a successive caching algorithm is developed to simultaneously reduce worst-case delivery rates at every request time, which are uniformly within a constant multiplicative factor of their respective optima.

Learning and compression are driven by the common aim of identifying and exploiting statistical regularities in data, which opens the door for fertile collaboration between these areas. A promising group of compression techniques for learning scenarios is normalised maximum likelihood (NML) coding, which provides strong guarantees for compression of small datasets — in contrast with more popular estimators whose guarantees hold only in the asymptotic limit. Here we consider a NMLbased decision strategy for supervised classification problems, and show that it attains heuristic PAC learning when applied to a wide variety of models. Furthermore, we show that the misclassification rate of our method is upper bounded by the maximal leakage, a recently proposed metric to quantify the potential of data leakage in privacy-sensitive scenarios.

Algebraic network information theory is an emerging facet of network information theory, studying the achievable rates of random code ensembles that have algebraic structure, such as random linear codes. A distinguishing feature is that linear combinations of codewords can sometimes be decoded more efficiently than codewords themselves. The present work further develops this framework by studying the simultaneous decoding of multiple messages. Specifically, consider a receiver in a multi-user network that wishes to decode several messages. Simultaneous joint typicality decoding is one of the most powerful techniques for determining the fundamental limits at which reliable decoding is possible. This technique has historically been used in conjunction with random i.i.d. codebooks to establish achievable rate regions for networks. Recently, it has been shown that, in certain scenarios, nested linear codebooks in conjunction with “single-user” or sequential decoding can yield better achievable rates. For instance, the compute-forward problem examines the scenario of recovering L ≤ K linear combinations of transmitted codewords over a K-user multiple-access channel (MAC), and it is well established that linear codebooks can yield higher rates. This paper develops bounds for simultaneous joint typicality decoding used in conjunction with nested linear codebooks, and applies them to obtain a larger achievable region for compute-forward over a K-user discrete memoryless MAC. The key technical challenge is that competing codeword tuples that are linearly dependent on the true codeword tuple introduce statistical dependencies, which requires careful partitioning of the associated error events.

The feedback sum-rate capacity is established for the symmetric J -user Gaussian multiple-access channel (GMAC). The main contribution is a converse bound that combines the dependence-balance argument of Hekstra and Willems (1989) with a variant of the factorization of a convex envelope of Geng and Nair (2014). The converse bound matches the achievable sum-rate of the Fourier-Modulated Estimate Correction strategy of Kramer (2002).

Caching is a technique that alleviates networks during peak hours by transmitting partial information before a request for any is made. In a lossy setting of Gaussian databases, we study a single-user model in which good caching strategies minimize the data still needed on average once the user requests a file. The encoder decides on a caching strategy by weighing the benefit from two key parameters: the prior preference for a file and the correlation among the files. Considering uniform prior preference but correlated files, caching becomes an application of Wyner's common information and Watanabe's total correlation. We show this case triggers a split: caching Gaussian sources is a non-convex optimization problem unless one spends enough rate to cache all the common information between files. Combining both correlation and user preference we explicitly characterize the full trade-off when the encoder uses Gaussian codebooks in a database of two files: we show that as the size of the cache increases, the encoder should change strategy and increasingly prioritize user preference over correlation. In this specific case we also address the loss in performance incurred if the encoder has no knowledge of the user's preference and show that this loss is bounded.

The following problem is considered: given a joint distribution PXYand an event E, bound PXY(E) in terms of PXPY(E) (where PXPYis the product of the marginals of PXY) and a measure of dependence of X and Y. Such bounds have direct applications in the analysis of the generalization error of learning algorithms, where E represents a large error event and the measure of dependence controls the degree of overfitting. Herein, bounds are demonstrated using several information-theoretic metrics, in particular: mutual information, lautum information, maximal leakage, and J∞. The mutual information bound can outperform comparable bounds in the literature by an arbitrarily large factor.

Consider the important special case of the K-user distributed source coding problem where the decoder only wishes to recover one or more linear combinations of the sources. The work of Körner and Marton demonstrated that, in some cases, the optimal rate region is attained by random linear codes, and strictly improves upon the best-known achievable rate region established via random i.i.d. codes. Recent efforts have sought to develop a framework for characterizing the achievable rate region for nested linear codes via joint typicality encoding and decoding. Here, we make further progress along this direction by proposing an achievable rate region for simultaneous joint typicality decoding of nested linear codes. Our approach generalizes the results of Körner and Marton to computing an arbitrary number of linear combinations and to the lossy computation setting.

To reduce the network load during peak hours, servers deliver partial data to users during the off-peak time of the network before the actual requests are known, which is known as caching. This paper studies a single user caching problem in which the file contents are subject to dynamic modifications with respect to a certain probability distribution. To cope with the dynamical nature of the file contents, a successive refinement approach to caching is presented: partial information of the original data is cached first and then if there is a modification, a refinement to the previously cached data is delivered to the user. Given a fixed cache memory, there is a tension between the rates of two cache descriptions. The problem of optimal caching strategies is formulated through a successive Gray-Wyner network, the optimal rate region of which is characterized. Some lower and upper bounds on the performance of optimal caching strategies are developed and shown to actually yield closed form solutions for certain classes of file contents.

There has been growing interest in studying connections between generalization error of learning algorithms and information measures. In this work, we generalize a result that employs the maximal leakage, a measure of leakage of information, and explore how this bound can be applied in different scenarios. The main application can be found in bounding the generalization error. Rather than analyzing the expected error, we provide a concentration inequality. In this work, we do not require the assumption of σ-sub gaussianity and show how our results can be used to retrieve a generalization of the classical bounds in adaptive scenarios (e.g., McDiarmid's inequality for c-sensitive functions, false discovery error control via significance level, etc.).

In the problem of coded caching for media delivery, two separate coding opportunities have been identified. The first opportunity is a multi-user advantage and crucially hinges on a public broadcast link in the delivery phase. This has been explored in a plethora of works. The second opportunity has received far less attention and concerns similarities between files in the database. Here, the paradigm is to cache “the similarity” between the files. Upon the request, the encoder refines this by providing the specific details for the requested files. Extending Gray and Wyner's work (1974), it follows that the right measure of file similarity is Wyner's Common Information and its generalizations. The present paper surveys and extends the role of Wyner's Common Information in caching. As a novel result, explicit solutions are found for the Gaussian case under mean-squared error, both for the caching problem as well as for the network considered by Gray and Wyner. Our solution leverages and extends the recent technique of factorization of convex envelopes.

We present a practical strategy that aims to attain rate points on the dominant face of the multiple access channel capacity using a standard low complexity decoder. This technique is built upon recent theoretical developments of Zhu and Gastpar on compute-forward multiple access which achieves the capacity of the multiple access channel using a sequential decoder. We illustrate this strategy with off-the-shelf LDPC codes. In the first stage of decoding, the receiver first recovers a linear combination of the transmitted codewords using the sum-product algorithm (SPA). In the second stage, by using the recovered sum-of-codewords as side information, the receiver recovers one of the two codewords using a modified SPA, ultimately recovering both codewords. The main benefit of recovering the sum-of-codewords instead of the codeword itself is that it allows to attain points on the dominant face of the multiple access channel capacity without the need of rate-splitting or time sharing while maintaining a low complexity in the order of a standard point-to-point decoder. This property is also shown to be crucial for some applications, e.g., interference channels. For all the simulations with single-layer binary codes, our proposed practical strategy is shown to be within 1.7 dB of the theoretical limits, without explicit optimization on the off-the-self LDPC codes.

The distributed remote source coding (the so-called CEO) problem is studied in the case where the underlying source, not necessarily Gaussian, has finite differential entropy and the observation noise is Gaussian. The main result is a new lower bound for the sum-rate-distortion function under arbitrary distortion measures. When specialized to the case of mean-squared error, it is shown that the bound exactly mirrors a corresponding upper bound, except that the upper bound has the source power (variance), whereas the lower bound has the source entropy power. Bounds exhibiting this pleasing duality of power and entropy power have been well known for direct and centralized source coding since Shannon's work. While the bounds hold generally, their value is most pronounced when interpreted as a function of the number of agents in the CEO problem.

A new scheme for the problem of centralized coded caching with non-uniform demands is proposed. The distinguishing feature of the proposed placement strategy is that it admits equal sub-packetization for all files while allowing the users to allocate more cache to the files which are more popular. This creates natural broadcasting opportunities in the delivery phase which are simultaneously helpful for the users who have requested files of different popularities. For the case of two files, we propose a new delivery strategy based on interference alignment which enables each user to decode his desired file following a two-layer peeling decoder. Furthermore, we extend the existing converse bounds for uniform demands under uncoded placement to the nonuniform case. To accomplish this, we construct$N!$auxiliary users, corresponding to all permutations of the$N$files, each caching carefully selected sub-packets of the files. Each auxiliary user provides a different converse bound. The overall converse bound is the maximum of all these$N!$bounds. We prove that our achievable delivery rate for the case of two files meets this converse, thereby establishing the optimal expected memory-rate trade-off for the case of$K$users and two files with arbitrary popularities under uncoded placement.

Computation codes in network information theory are designed for scenarios where the decoder is not interested in recovering the information sources themselves, but only a function thereof. Körner and Marton showed for distributed source coding (DSC) that such function decoding can be achieved more efficiently than decoding the full information sources. Compute-forward has shown that function decoding, in combination with network coding ideas, is a useful building block for end-to-end communication over a network. In both cases, good computation codes are the key component in the coding schemes. Could these same codes simultaneously also enable full message decoding over a sufficiently strong multiple-access channel (MAC)? This work establishes a partial negative answer and converse result. Specifically, for any code that is known to be a good computation code for some MAC, we characterize a class of MACs for which that code cannot enable full message decoding (and vice versa). Finally, an analogous duality result is established for a related DSC problem.

Adaptive data analysis is known to introduce bias in reported measurements. Russo and Zou [1] recently introduced an information-theoretic framework to study this problem. Herein, this framework is adopted and new dependence measures are introduced to bound the exploration bias. When the measurements have bounded L1- or L2-norms, or when the selection procedure is symmetric, the new bounds are such that the contribution of the selection procedure to the bias is decoupled from the effects of the underlying distribution generating the data, thus enabling direct comparisons between different selection procedures.

In the problem of private information retrieval with side information, a single user wants to recover one of the K independent messages which are stored at one or multiple servers. The user initially has a subset of messages as side information. The goal of the user is to retrieve the demand message by using minimum number of transmissions (R*) from the server(s) to the user under the condition that the index of the demand message should not be inferred by the server. We introduce the multi-user variant into this problem, where each user wants to retrieve one message and has a subset of messages as side information. In this paper, we study the special cases where all users want to retrieve one common message from a single server, but each user has different side information messages. We show that the optimal coding scheme can be constructed by first optimally partitioning the messages and then generating MDS codes separately in each subset of messages in the partition. We determine the R*, propose algorithms to compute R*, and construct optimal linear coding schemes with complexity polynomial in K (but exponential in the number of side information messages).

We introduce the Fixed Cluster Repair System (FCRS) as a novel architecture for Distributed Storage Systems (DSS) that achieves a small repair bandwidth while guaranteeing a high availability. Specifically, we partition the set of servers in a DSS into s clusters and allow a failed server to choose any cluster other than its own as its repair group. Thereby, we guarantee an availability of s-1. We characterize the repair bandwidth vs. storage trade-off for the FCRS under functional repair and show that the minimum repair bandwidth can be improved by an asymptotic multiplicative factor of 2/3 compared to the state of the art coding techniques that guarantee the same availability. Furthermore, we introduce cubic codes designed to minimize the repair bandwidth of the FCRS under the exact repair model. We prove an asymptotic multiplicative improvement of 0.79 in the minimum repair bandwidth compared to the existing exact repair coding techniques that achieve the same availability. We show that cubic codes are information-theoretically optimal for the FCRS with 2 and 3 complete clusters. A full version of this paper is accessible at: https://arxiv.org/pdf/1710.02653.pdf.

The feedback sum-rate capacity is established for the symmetric three-user Gaussian multiple-access channel (GMAC). The main contribution is a converse bound that combines the dependence-balance argument of Hekstra and Willems (1989) with a variant of the “doubling trick” of Geng and Nair (2014). The converse bound matches the achievable sum-rate of the Fourier-Modulated Estimate Correction strategy of Kramer (2002). The proof arguments extend to GMACs with more than three users.

This paper presents a joint typicality framework for encoding and decoding nested linear codes in multi-user networks. This framework provides a new perspective on compute-forward within the context of discrete memoryless networks. In particular, it establishes an achievable rate region for computing a linear combination over a discrete memoryless multiple-access channel (MAC). When specialized to the Gaussian MAC, this rate region recovers and improves upon the lattice-based compute-forward rate region of Nazer and Gastpar, thus providing a unified approach for discrete memoryless and Gaussian networks. Furthermore, our framework provides some valuable insights on establishing the optimal decoding rate region for compute-forward by considering joint decoders, progressing beyond most previous works that consider successive cancellation decoding. Specifically, this paper establishes an achievable rate region for simultaneously decoding two linear combinations of nested linear codewords from K senders.

The coded cooperative data exchange problem is studied for the fully connected network. In this problem, each node initially only possesses a subset of the K packets making up the file. Nodes make broadcast transmissions that are received by all other nodes. The goal is for each node to recover the full file. In this paper, we present a polynomial-time deterministic algorithm to compute the optimal (i.e., minimal) number of required broadcast transmissions and to determine the precise transmissions to be made by the nodes. A particular feature of our approach is that each of the K − d transmissions is a linear combination of exactly d + 1 packets, and we show how to optimally choose the value of d. We also show how the coefficients of these linear combinations can be chosen by leveraging a connection to Maximum Distance Separable (MDS) codes.

Recent work has employed joint typicality encoding and decoding of nested linear code ensembles to generalize the compute-forward strategy to discrete memoryless multiple-access channels (MACs). An appealing feature of these nested linear code ensembles is that the coding strategies and error probability bounds are conceptually similar to classical techniques for random i.i.d. code ensembles. In this paper, we consider the problem of recovering K linearly independent combinations over a K-user MAC, i.e., recovering the messages in their entirety via nested linear codes. While the MAC rate region is well-understood for random i.i.d. code ensembles, new techniques are needed to handle the statistical dependencies between competing codeword K-tuples that occur in nested linear code ensembles.

The classical distributed storage problem can be modeled by a k-uniform complete hyper-graph where vertices represent servers and hyper-edges represent users. Hence each hyper-edge should be able to recover the full file using only the memories of the vertices associated with it. This paper considers the generalization of this problem to arbitrary hyper-graphs and to the case of multiple files, where each user is only interested in one, a problem we will refer to as the graphical distributed storage problem (GDSP). Specifically, we make progress in the analysis of minimum-storage codes for two main subproblems of the GDSP which extend the classical model in two independent directions: the case of an arbitrary graph with multiple files, and the case of an arbitrary hyper-graph with a single file.

Inspired by the compute-and-forward scheme from Nazer and Gastpar, a novel multiple-access scheme introduced by Zhu and Gastpar makes use of nested lattice codes and sequential decoding of linear combinations of codewords to recover the individual messages. This strategy, coined compute-forward multiple access (CFMA), provably achieves points on the dominant face of the multiple-access capacity region while circumventing the need of time sharing or rate splitting. For a two-user multiple-access channel (MAC), we propose a practical procedure to design suitable codes from off-the-shelf LDPC codes and present a sequential belief propagation decoder with complexity comparable with that of point-to-point decoders. We demonstrate the potential of our strategy by comparing several numerical evaluations with theoretical limits.

In this paper, we consider a cache aided network in which each user is assumed to have individual caches, while upon users' requests, an update message is sent through a common link to all users. First, we formulate a general information theoretic setting that represents the database as a discrete memoryless source, and the users' requests as side information that is available everywhere except at the cache encoder. The decoders' objective is to recover a function of the source and the side information. By viewing cache aided networks in terms of a general distributed source coding problem and through information theoretic arguments, we present inner and outer bounds on the fundamental tradeoff of cache memory size and update rate. Then, we specialize our general inner and outer bounds to a specific model of content delivery networks: file selection networks, in which the database is a collection of independent equal-size files and each user requests one of the files independently. For file selection networks, we provide an outer bound and two inner bounds (for centralized and decentralized caching strategies). For the case when the user request information is uniformly distributed, we characterize the rate versus cache size tradeoff to within a multiplicative gap of 4. By further extending our arguments to the framework of Maddah-Ali and Niesen, we also establish a new outer bound and two new inner bounds in which it is shown to recover the centralized and decentralized strategies, previously established by Maddah-Ali and Niesen. Finally, in terms of rate versus cache size tradeoff, we improve the previous multiplicative gap of 72 to 4.7 for the average case with uniform requests.

In this paper, we consider communication on a two-hop channel in which a source wants to send information reliably and securely to the destination via a relay. We consider both the untrusted relay case and the external eavesdropper case. In the untrusted relay case, the relay behaves as an eavesdropper, and there is a cooperative node, which sends a jamming signal to confuse the relay when it is receiving from the source. In the external eavesdropper case, the relay is trusted, and there is an external node eavesdropping the communication. We propose two secure transmission schemes using the scaled compute-and-forward technique. One of the schemes is based on a random binning code, and the other one is based on a lattice chain code. It is proved that in the high signal-to-noise-ratio (SNR) scenario and/or the limited relay power scenario, if the destination is used as the jammer, both schemes outperform all existing schemes and achieve the upper bound. In particular, if the SNR is large and the source, the relay, and the cooperative jammer have identical power and channels, both schemes achieve the upper bound for secrecy rate, which is merely 1/2 bit per channel use lower than the channel capacity without secrecy constraints. We also prove that one of our schemes achieves a positive secrecy rate in the external eavesdropper case in which the relay is trusted and there exists an external eavesdropper.

A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψ log(nψ)), where ψ = √P∥h∥2+ 1 depends on the transmission power and the norm of the channel vector. We will then extend our results to integer-forcing and finally introduce a more general class of lattices for which the SVP and the closest vector problem can be approximated within a constant factor.

Lattice codes used under the compute-and-forward paradigm suggest an alternative strategy for the standard Gaussian multiple-access channel (MAC): the receiver successively decodes the integer linear combinations of the messages until it can invert and recover all messages. In this paper, a multiple-access technique called compute-forward multiple access (CFMA) is proposed and analyzed. For the two-user MAC, it is shown that without time-sharing, the entire capacity region can be attained using CFMA with a single-user decoder as soon as the signal-to-noise ratios are above √1+ 2. A partial analysis is given for more than two users. Finally, the strategy is extended to the so-called dirty MAC, where two interfering signals are known non-causally to the two transmitters in a distributed fashion. Our scheme extends the previously known results and gives new achievable rate regions.

In this paper, we present information theoretic inner and outer bounds on the fundamental tradeoff between cache memory size and update rate in a multi-user cache network. Each user is assumed to have individual caches, while upon users' requests, an update message is sent though a common link to all users. The database is represented as a discrete memoryless source and the user request information is represented as side information that is available at the decoders and the update encoder, but oblivious to the cache encoder. We establish two inner bounds, the first based on a centralized caching strategy and the second based on a decentralized caching strategy. For the case when the user requests are i.i.d. with the uniform distribution, we show that the performance of the decentralized inner bound is within a multiplicative gap of 4 from the optimal cache-rate tradeoff. For general request distributions, we numerically compare the bounds and the baseline uncoded strategy, caching the most popular files.

We consider a setup in which confidential i.i.d. samples X1, ..., Xnfrom an unknown discrete distribution PXare passed through a discrete memoryless privatization channel (a.k.a. mechanism) which guarantees an ϵ-level of local differential privacy. For a given ϵ, the channel should be designed such that an estimate of the source distribution based on the channel outputs converges as fast as possible to the exact value PX. For this purpose we consider two metrics of estimation accuracy: the expected mean-square error and the expected Kullback-Leibler divergence. We derive their respective normalized first-order terms (as n → ∞), which for a given target privacy ϵ represent the factor by which the sample size must be augmented so as to achieve the same estimation accuracy as that of an identity (non-privatizing) channel. We formulate the privacy-utility tradeoff problem as being that of minimizing said first-order term under a privacy constraint ϵ. A converse bound is stated which bounds the optimal tradeoff away from the origin. Inspired by recent work on the optimality of staircase mechanisms (albeit for objectives different from ours), we derive an achievable tradeoff based on circulant step mechanisms. Within this finite class, we determine the optimal step pattern.

Compute-and-forward (CF) is a technique which exploits broadcast and superposition in wireless networks. In this paper, the CF energy benefit is studied for networks with unicast sessions and modeled by connected graphs. This benefit is defined as the ratio of the minimum energy consumption by traditional routing techniques, not using broadcast and superposition features, and the corresponding CF consumption. It is shown to be upper bounded by min(d̅, K, 12√K), where d̅ and K are the average hop-count distance and the number of sessions, respectively. Also, it can be concluded that the energy benefit of network coding (NC) is also upper bounded by the same value, which is a new scaling law of the energy benefit for NC as a function of K.

In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file, while minimizing some communication cost. We assume that the users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user's cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this paper, each user can have any arbitrary convex cost function. We provide deterministic, polynomial-time algorithms (in the number of users and packets), which find an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm, which is based on a random linear network-coding scheme.

The classical problem in a network coding theory considers communication over multicast networks. Multiple transmitters send independent messages to multiple receivers that decode the same set of messages. In this paper, computation over multicast networks is considered: each receiver decodes an identical function of the original messages. For a countably infinite class of two-transmitter two-receiver single-hop linear deterministic networks, the computation capacity is characterized for a linear function (modulo-2 sum) of Bernoulli sources. A new upper bound is derived that is tighter than cut-set-based and genie-aided bounds. A matching inner bound is established via the development of a network decomposition theorem, which identifies elementary parallel subnetworks that can constitute an original network without loss of optimality. The decomposition theorem provides a conceptually simple proof of achievability that generalizes to L-transmitter L-receiver networks.

Under the paradigm of caching, partial data are delivered before the actual requests of users are known. In this paper, this problem is modeled as a canonical distributed source coding problem with side information, where the side information represents the users' requests. For the single-user case, a singleletter characterization of the optimal rate region is established, and for several important special cases, closed-form solutions are given, including the scenario of uniformly distributed user requests. In this case, it is shown that the optimal caching strategy is closely related to total correlation and Wyner's common information. Using the insight gained from the single-user case, three two-user scenarios admitting single-letter characterization are considered, which draw connections to existing source coding problems in the literature: the Gray-Wyner system and distributed successive refinement. Finally, the model studied by Maddah-Ali and Niesen is rephrased to make a comparison with the considered information-theoretic model. Although the two caching models have a similar behavior for the single-user case, it is shown through a two-user example that the two caching models behave differently in general.

For fast-fading memoryless single-user channels, we present new rate expressions that are achievable with i.i.d. Gaussian codes and successive nearest-neighbor decoders based on a Euclidian distance metric. The use of successive decoding is motivated by two factors: firstly, it was recently discovered that successive decoding potentially enhances achievable rates on single-user channels with imperfect channel-state information at the receiver (semicoherent channels); secondly, in the limit as the number of decoding steps tends to infinity, some of these rate expressions become tractable and expressible as integrals. To offer a unified view, we choose to put all rate expressions-old and new-into this integral representation inspired by the infinitesimal successive-decoding approach, in order to unveal their similarities.

Motivated by the caching problem introduced by Maddah-Ali and Niesen, a problem of distributed source coding with side information is formulated, which captures a distinct interesting aspect of caching. For the single-user case, a single-letter characterization of the optimal rate region is presented. For the cases where the source is composed of either independent or nested components, the exact optimal rate regions are found and some intuitive caching strategies are confirmed to be optimal. When the components are arbitrarily correlated with uniform requests, the optimal caching strategy is found to be closely related to total correlation and Wyner's common information. For the two-user case, some subproblems are solved which draw connections to the Gray-Wyner system and distributed successive refinement. Finally, inner and outer bounds are given for the case of two private caches with a common update.

The usefulness of lattice codes is investigated for two-user Gaussian interference channels (IC). A coding scheme based on the compute-and-forward technique is shown to achieve the capacity region of the Gaussian IC under strong interference. The proposed scheme uses single-user decoders whereas the conventional scheme uses multi-user decoders for simultaneous decoding. The same scheme is applicable to the Gaussian Z-interference channel. A lattice-based coding scheme is also devised for the state-dependent Gaussian IC with the state sequence non-causally known to transmitters. The proposed scheme establishes new achievable rate regions, which can be considerably larger than the best known results, especially when the interfering state sequence has very large power.

A two-hop channel is considered, in which the source wants to send information to the destination while keeping the information confidential from the relay. A novel lattice chain and compute-and-forward based scheme is proposed in which the destination provides cooperative jamming. Channel state information is used at the source and the destination to scale the encoding lattices for the message and the jamming signal according to the channel gains. We compare the achievable secrecy rate of our scheme with an upper bound and with the achievable secrecy rate of other schemes. It follows that our scheme outperforms all existing schemes except in the low power region.

The classical modulo-lattice construction of Erez et al. has been successfully applied to several coding problems under Gaussian noise, including coding for computation over multiple-access channels (MAC). For the latter problem, an alternative construction can be developed by extending a recently proposed nested linear code to Gaussian case. In this note, it is shown that using the nested linear code with judiciously chosen input distributions, the original compute-and-forward result is recovered and larger computation rates are achievable. In particular we show that the Gaussian input distribution is not optimal in general for the computation problem over Gaussian MAC. Among other results, new achievable rates for the Gaussian two-way relay channel (TWRC) are given.

Polar codes are introduced for discrete memoryless broadcast channels. For m-user deterministic broadcast channels, polarization is applied to map uniformly random message bits from m-independent messages to one codeword while satisfying broadcast constraints. The polarization-based codes achieve rates on the boundary of the private-message capacity region. For two-user noisy broadcast channels, polar implementations are presented for two information-theoretic schemes: 1) Cover's superposition codes and 2) Marton's codes. Due to the structure of polarization, constraints on the auxiliary and channel-input distributions are identified to ensure proper alignment of polarization indices in the multiuser setting. The codes achieve rates on the capacity boundary of a few classes of broadcast channels (e.g., binary-input stochastically degraded). The complexity of encoding and decoding is O(n log n), where n is the block length. In addition, polar code sequences obtain a stretched-exponential decay of O(2-nβ) of the average block error probability where 0 <; β <; 1/2. Reproducible experiments for finite block lengths n = 512, 1024, 2048 corroborate the theory.

We consider a physical-layer network coding strategy for the random-access channel, based on compute-and-forward. When packets collide, it is possible to reliably recover a linear combination of the packets at the receiver. Over many rounds of transmission, the receiver can thus obtain many linear combinations and eventually recover all original packets. This is by contrast to slotted ALOHA where packet collisions lead to complete erasures. The strategy is shown to be significantly superior to the best known strategies, including multipacket reception.

In wireless sensor networks, various applications involve learning one or multiple functions of the measurements observed by sensors, rather than the measurements themselves. This paper focuses on the class of type-threshold functions, e.g., the maximum and the indicator functions. A simple network model capturing both the broadcast and superposition properties of wireless channels is considered: the collocated Gaussian network. A general multiround coding scheme exploiting superposition and interaction (through broadcast) is developed. Through careful scheduling of concurrent transmissions to reduce redundancy, it is shown that given any independent measurement distribution, all type-threshold functions can be computed reliably with a nonvanishing rate in the collocated Gaussian network, even if the number of sensors tends to infinity.

A new achievable rate region is given for the Gaussian cognitive many-to-one interference channel. The proposed novel coding scheme is based on the compute-and-forward approach with lattice codes. Using the idea of decoding sums of codewords, our scheme improves considerably upon the conventional coding schemes which treat interference as noise or decode messages simultaneously. Our strategy also extends directly to the usual many-to-one interference channels without cognitive messages. Comparing to the usual compute-and-forward scheme where a fixed lattice is used for the code construction, the novel scheme employs scaled lattices and also encompasses key ingredients of the existing schemes for the cognitive interference channel. With this new component, our scheme achieves a larger rate region in general. For some symmetric channel settings, new constant gap or capacity results are established, which are independent of the number of users in the system.

The problem of successive refinement in distributed source coding and in joint source-channel coding is considered. The emphasis is placed on the case where the sources have to be recovered losslessly in the second stage. In distributed source coding, it is shown that all sources are successively refinable in sum rate, with respect to any (joint) distortion measure in the first stage. In joint source-channel coding, the sources are assumed independent and only a (per letter) function is to be recovered losslessly in the first stage. For a class of multiple access channels, it is shown that all sources are successively refinable with respect to a class of linear functions. Finally, when the sources have equal entropy, a simple sufficient condition of successive refinability is provided for partially invertible functions.

Lattice codes are applied to the two-user Gaussian multiple access channel (MAC) combined with a modified compute-and-forward transmitting scheme. It is shown that non-corner points on the boundary of the capacity region can be achieved by decoding two integer sums of the codewords, which can be viewed as a generalization of the well-known successive cancellation decoding. A similar idea is then applied to the so-called dirty MAC where two interfering signals are known non-causally to the two transmitters in a distributed fashion. Our scheme recovers previously known results and gives new achievable rate regions. The proposed scheme can be extended to the case with more than two users.

Consider a receiver that observes multiple interfering codewords. The compute-and-forward technique makes it possible for the receiver to directly decode linear combinations of the codewords. Previous work has focused on compute-and-forward for linear Gaussian networks. This paper explores the corresponding technique for discrete memoryless networks. As a by-product, this leads to a novel way of attaining non-trivial points on the dominant face of the capacity region of discrete memoryless multiple-access channels.

A coding scheme is proposed for the memoryless Gaussian broadcast channel with correlated noises and feedback. For all noise correlations other than ±1, the gap between the sum-rate that the scheme achieves and the full-cooperation bound vanishes as the signal-to-noise ratio tends to infinity. When the correlation coefficient is -1, the gains afforded by feedback are unbounded and the prelog is doubled. When the correlation coefficient is +1, we demonstrate a dichotomy that if the noise variances are equal, then feedback is useless, and otherwise, feedback affords unbounded rate gains and doubles the prelog. The unbounded feedback gains, however, require perfect (noiseless) feedback. When the feedback links are noisy, the feedback gains are bounded, unless the feedback noise decays to zero sufficiently fast with the signal-to-noise ratio. Extensions to more receivers are also discussed as is the memoryless Gaussian interference channel with feedback.

The capacity scaling laws of two overlaid networks are investigated, which are located in the same area sharing the same wireless resources with different priorities. The primary network can be regarded as an existing communication system operated in a licensed band and, therefore, is assumed to operate in an order-optimal fashion to achieve its standalone capacity scaling law. The secondary cognitive network must keep its interference to the primary network below a certain threshold while at the same time maximizing its own throughput scaling law based on cognition information. The existing scaling results for cognitive networks inherently assume multihop communication, which is a restricted coding model. By contrast, in this paper, a general coding model is considered without any specific physical layer coding assumptions. The capacity scaling exponents for both networks are analyzed when the numbers of primary nodes n, primary base stations l, which support the communication between primary nodes, and secondary nodes m increase with the relations m = nβ, β > 1, and l = nγ, 0 ≤ γ ≤ 1. For the extended network model, the capacity scaling exponents are completely characterized as max {2-α/2, 1/2, γ} and max{2-α/2, 1/2} for the primary and secondary networks respectively, where α > 2 denotes the path-loss exponent. That is, the capacity scaling laws for the primary and secondary networks are represented, respectively, by nmax{2-α/2,1/2,γ}±∈and mmax{2-α/2,1/2}±∈for α > 0 arbitrarily small. For the dense network model, when the primary network achieves its standalone capacity scaling exponent of 1, the secondary network is shown to achieve a scaling exponent of 1 - 1/(2β), which improves the previous scaling exponent of 1/2 achieved by multihop. For both models, it turns out that the conventional multihop approach is in general quite suboptimal.

The fading AWGN two-user two-hop network is considered where the channel coefficients are independent and identically distributed (i.i.d.) according to a continuous distribution and vary over time. For a broad class of channel distributions, the ergodic sum capacity is characterized to within a constant number of bits/second/hertz, independent of the signal-to-noise ratio. The achievability follows from the analysis of an interference neutralization scheme where the relays are partitioned into M pairs, and interference is neutralized separately by each pair of relays. When M = 1, the proposed ergodic interference neutralization characterizes the ergodic sum capacity to within 4 bits/sec/Hz for i.i.d. uniform phase fading and approximately 4.7 bits/sec/Hz for i.i.d. Rayleigh fading. It is further shown that this gap can be tightened to 4 log π-4 bits/sec/Hz (approximately 2.6) for i.i.d. uniform phase fading and 4-4 log(3π/8) bits/sec/Hz (approximately 3.1) for i.i.d. Rayleigh fading in the limit of large M1.

Function computation over Gaussian networks with orthogonal components is studied for arbitrarily correlated discrete memoryless sources. Two classes of functions are considered: 1) the arithmetic sum function and 2) the type function. The arithmetic sum function in this paper is defined as a set of multiple weighted arithmetic sums, which includes averaging of the sources and estimating each of the sources as special cases. The type or frequency histogram function counts the number of occurrences of each argument, which yields various fundamental statistics, such as mean, variance, maximum, minimum, median, and so on. The proposed computation coding first abstracts Gaussian networks into the corresponding modulo sum multiple-access channels via nested lattice codes and linear network coding and then computes the desired function using linear Slepian-Wolf source coding. For orthogonal Gaussian networks (with no broadcast and multiple-access components), the computation capacity is characterized for a class of networks. For Gaussian networks with multiple-access components (but no broadcast), an approximate computation capacity is characterized for a class of networks.

Based on the recent compute-and-forward technique, a novel communication strategy is proposed under which functions of the channel state information are forwarded along the network. Those functions are chosen such that on the one hand, they can be efficiently forwarded, and on the other hand, they are maximally useful to the final decoder of the message. It is illustrated that there is generally a tension between these two requirements. The strategy is shown to perform well for certain classes of multilayer networks where channel state information is acquired locally at each receiver. For example, for a two-stage Gaussian relay network with local channel state information, it is shown that the proposed strategy performs optimally in a scaling-law sense, as the number of relays increases.

Linear receivers are often used to reduce the implementation complexity of multiple-antenna systems. In a traditional linear receiver architecture, the receive antennas are used to separate out the codewords sent by each transmit antenna, which can then be decoded individually. Although easy to implement, this approach can be highly suboptimal when the channel matrix is near singular. This paper develops a new linear receiver architecture that uses the receive antennas to create an effective channel matrix with integer-valued entries. Rather than attempting to recover transmitted codewords directly, the decoder recovers integer combinations of the codewords according to the entries of the effective channel matrix. The codewords are all generated using the same linear code, which guarantees that these integer combinations are themselves codewords. Provided that the effective channel is full rank, these integer combinations can then be digitally solved for the original codewords. This paper focuses on the special case where there is no coding across transmit antennas and no channel state information at the transmitter(s), which corresponds either to a multiuser uplink scenario or to single-user V-BLAST encoding. In this setting, the proposed integer-forcing linear receiver significantly outperforms conventional linear architectures such as the zero forcing and linear minimum mean-squared error receiver. In the high signal-to-noise ratio regime, the proposed receiver attains the optimal diversity-multiplexing tradeoff for the standard multiple-input multiple-output (MIMO) channel with no coding across transmit antennas. It is further shown that in an extended MIMO model with interference, the integer-forcing linear receiver achieves the optimal generalized degrees of freedom.

The capacity scaling laws of two overlaid networks sharing the same wireless resources with different priorities are investigated. The primary network is assumed to operate in an order-optimal fashion to achieve its standalone capacity scaling law. The secondary “cognitive” network must keep its interference to the primary network below a certain threshold while at the same time maximizing its own throughput scaling law based on cognition information. The existing scaling results for cognitive networks inherently assume multihop communication treating all other signals except from a single intended transmitter as noise. By contrast, in this paper, a general coding model is considered without any specific physical layer coding assumptions. Therefore, this paper provides a general framework for comprehensive understanding of fundamental limits on the capacity scaling laws of cognitive networks. For the extended network model, the capacity scaling laws of both the primary and secondary networks are completely characterized. For the dense network model, an improved throughput scaling law is achieved by inducing cooperation within the secondary network. In both cases, it turns out that the conventional multihop approach is in general quite suboptimal.

Building on polar code constructions proposed by the authors for deterministic broadcast channels, two theorems are introduced in the present paper for noisy two-user broadcast channels. The theorems establish polar code constructions for two important information-theoretic broadcast strategies: (1) Cover's superposition strategy; (2) Marton's construction. One aspect of the polar code constructions is the alignment of polarization indices via constraints placed on the auxiliary and channel-input distributions. The codes achieve capacity-optimal rates for several classes of broadcast channels (e.g., binary-input stochastically degraded channels). Applying Arıkan's original matrix kernel for polarization, it is shown that the average probability of error in decoding two private messages at the broadcast receivers decays as O(2(-nβ)) where 0 <; β <; 1/2 and n is the code length. The encoding and decoding complexities remain O(n log n). The error analysis is made possible by defining new polar code ensembles for broadcast channels.

We consider a physical-layer network coding strategy for the random-access channel, based on compute-and-forward. When packets collide, it is possible to reliably recover a linear combination of the packets at the receiver. Over many rounds of transmission, the receiver can thus obtain many linear combinations and eventually recover all original packets. This is by contrast to slotted ALOHA where packet collisions lead to complete erasures. In previous work we introduced a compute-and-forward strategy for the two-user random-access channel. In the current work we consider an arbitrary number of users. The strategy is shown to be significantly superior to the best known strategies, including multipacket reception.

Function computation of arbitrarily correlated discrete sources over Gaussian networks with multiple access components but no broadcast is studied. Two classes of functions are considered: the arithmetic sum function and the frequency histogram function. The arithmetic sum function in this paper is defined as a set of multiple weighted arithmetic sums, which includes averaging of sources and estimating each of the sources as special cases. The frequency histogram function counts the number of occurrences of each argument, which yields many important statistics such as mean, variance, maximum, minimum, median, and so on. For a class of networks, an approximate computation capacity is characterized. The proposed approach first abstracts Gaussian networks into the corresponding modulo-sum multiple-access channels via lattice codes and linear network coding and then computes the desired function by using linear Slepian-Wolf source coding.

Signal superposition and broadcast are important features of the wireless medium. Compute-and-Forward, also known as Physical Layer Network Coding, is a technique exploiting these features in order to improve performance of wireless networks. In this paper, the possible benefits for the line network with multiple bi-directional sessions and local interference are investigated. Four different modes, indicating whether or not broadcast and/or superposition are exploited, are considered. In particular, expressions for the maximum achievable common rate are derived for each of the four different modes. Scheduling and coding schemes achieving these rates are presented. From the results it follows that, in most cases, the common rate is improved by a factor close to two by using Compute-and-Forward. However, it is also found that the benefit may be smaller for particular session configurations.

We investigate the role of interaction for computation problem settings where nodes intend to compute functions of the raw messages generated at other nodes. In this work, we make some progress on a more elementary research component: feedback. Specifically we characterize the feedback computing capacity of a two-transmitter two-receiver linear deterministic network in which both receivers wish to decode a linear function (modulo-2 sum) of Bernoulli sources generated at the transmitters. Inspired by the concept of interference alignment and compute-and-forward, we develop a new achievable scheme called interactive function alignment. A new converse theorem is established that is tighter than cut-set based and genie-aided bounds. As a consequence of this result, we show that interaction can provide an arbitrarily large gain for computation, as in classical communication settings.

In wireless sensor networks, various applications involve learning one or multiple functions of the measurements observed by sensors, rather than the measurements themselves. This paper focuses on the computation of type-threshold functions which include the maximum, minimum, and indicator functions as special cases. Previous work studied this problem under the collocated collision network model and showed that under many probabilistic models for the measurements, the achievable computation rates tend to zero as the number of sensors increases. In this paper, wireless sensor networks are modeled as fully connected Gaussian networks with equal channel gains, which are termed collocated Gaussian networks. A general multi-round coding scheme exploiting not only the broadcast property but also the superposition property of Gaussian networks is developed. Through careful scheduling of concurrent transmissions to reduce redundancy, it is shown that given any independent measurement distribution, all type-threshold functions can be computed reliably with a non-vanishing rate even if the number of sensors tends to infinity.

In this work we consider the cognitive many-to-one interference network. We first extend existing coding schemes from the two-user case to this network scenario. Then we present a novel coding scheme using compute-and-forward and show it can enlarge the achievable rate region considerably for a wide range of parameters. Numerical evaluations are given to compare the performance of different schemes. Specializing the results to symmetric settings, for a range of parameters, our achievable rate region is shown to be within a constant gap from capacity, regardless of the number of cognitive users.

In linear function computation, multiple source nodes communicate across a relay network to a single destination whose goal is to recover linear functions of the original source data. When the relay network is a linear deterministic network, a duality relation is established between function computation and broadcast with common messages. Using this relation, a compact sufficient condition is found describing those cases where the cut-set bound is tight. These insights are used to develop results for the case where the relay network contains Gaussian multiple-access channels. The proposed scheme decouples the physical and network layers. Using lattice codes for both source quantization and computation in the physical layer, the original Gaussian sources are converted into discrete sources and the Gaussian network into a linear deterministic network. Network codes for computing functions of discrete sources across the deterministic network are then found by applying the duality relation. The distortion for computing the sum of an arbitrary number of independent Gaussian sources over the Gaussian network is proven to be within a constant factor of the optimal performance. Furthermore, the constant factor results are extended to include asymmetric functions for the case of two sources.

This paper explores the problem of feedback coding for a channel whose output is simultaneously used for two purposes: it is decoded to establish reliable communication, and it is used to control a dynamical system. In general, there is a tradeoff between the rate of communication and the accuracy of control. An intuitive communication and control strategy is analyzed and shown to be optimal in several cases of interest. Using methods from stochastic control, a corresponding upper bound is derived on the rate for a given cost, and this bound can be applied to find the capacity for an interesting class of channels. Under certain regularity conditions, the capacity has a simple characterization, and a series of examples is provided to demonstrate how it can be calculated.

Recovery of the sparsity pattern (or support) of an unknown sparse vector from a small number of noisy linear measurements is an important problem in compressed sensing. In this paper, the high-dimensional setting is considered. It is shown that if the measurement rate and per-sample signal-to-noise ratio (SNR) are finite constants independent of the length of the vector, then the optimal sparsity pattern estimate will have a constant fraction of errors. Lower bounds on the measurement rate needed to attain a desired fraction of errors are given in terms of the SNR and various key parameters of the unknown vector. The tightness of the bounds in a scaling sense, as a function of the SNR and the fraction of errors, is established by comparison with existing achievable bounds. Near optimality is shown for a wide variety of practically motivated signal models.

We investigate how the network connectivity can affect the degrees of freedom (DoF) of wireless networks. We consider a network of n source-destination (SD) pairs and assume that any two nodes are connected with a positive probability p, independent of other node pairs. We show that, for any arbitrarily small p, a constant DoF is achievable for every SD pair with probability approaching one as n tends to infinity. The achievability is based on the two-hop transmission with decode-and-forward relaying and over each-hop we adopt interference alignment. Considering that an achievable per-user DoF for direct or one-hop transmission can be arbitrarily small as the connectivity probability p decreases, our result shows that, somewhat surprisingly, two-hop transmission is enough to guarantee non-vanishing per-user DoF for any p showing that sparsely connected networks can still provide non-vanishing per-user DoF.

We consider a fading AWGN 2-user 2-hop network in which the channel coefficients are independently and identically distributed (i.i.d.) drawn from a continuous distribution and vary over time. For a broad class of channel distributions, we characterize the ergodic sum capacity within a constant number of bits/sec/Hz, independent of signal-to-noise ratio. The achievability follows from the analysis of an interference neutralization scheme where the relays are partitioned into K pairs, and interference is neutralized separately by each pair of relays. For K = 1, we previously proved a gap of 4 bits/sec/Hz for i.i.d. uniform phase fading and approximately 4.7 bits/sec/Hz for i.i.d. Rayleigh fading. In this paper, we give a result for general K. In the limit of large K, we characterize the ergodic sum capacity within 4((log π) - 1) ≃ 2.6 bits/sec/Hz for i.i.d. uniform phase fading and 4(4 - log3π) ≃ 3.1 bits/sec/Hz for i.i.d. Rayleigh fading.

In this paper we construct a deterministic polynomial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another set of terminals in the system, called helpers, who are not interested in the common file, but who are willing to help the users. Given that the collective information of all the terminals is sufficient to allow recovery of the entire file, the goal is to minimize the (weighted) sum of bits that these terminals need to exchange over a noiseless public channel in order achieve this goal. Based on established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing the largest shared secret key in the presence of an eavesdropper. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the terminals' side-information consists of subsets of the file packets; (ii) side-information in the form of linearly correlated packets, where the terminals have access to linear combinations of the file packets; and (iii) the general setting where the the terminals' side-information has an arbitrary (i.i.d.) correlation structure. We provide a polynomial-time algorithm (in the number of terminals) that finds the optimal rate allocations for these terminals, and then determines an explicit optimal transmission scheme for cases (i) and (ii).

We characterize the capacity region to within log {2(M - 1)} bits/s/Hz for the M-transmitter K-receiver Gaussian multicast channel with feedback where each receiver wishes to decode every message from the M transmitters. Extending Cover-Leung's achievable scheme intended for (M, K) = (2, 1), we show that this generalized scheme achieves the cutset-based outer bound within log {2(M - 1)} bits per transmitter for all channel parameters. In contrast to the capacity in the nonfeedback case, the feedback capacity improves upon the naive intersection of the feedback capacities of K individual multiple access channels. We find that feedback provides unbounded multiplicative gain at high signal-to-noise ratios as was shown in the Gaussian interference channel. To complement the results, we establish the exact feedback capacity of the Avestimehr-Diggavi-Tse deterministic model, from which we make the observation that feedback can also be beneficial for function computation.

Determining the capacity of multi-receiver networks with arbitrary message demands is an open problem in the network coding literature. In this paper, we consider a multi-source, multi-receiver symmetric deterministic network model parameterized by channel coefficients (inspired by wireless network flow) in which the receivers compute a sum of the symbols generated at the sources. Scalar and vector linear coding strategies are analyzed. It is shown that computation alignment over finite field vector spaces is necessary to achieve the computation capacities in the network. To aid in the construction of coding strategies, network equivalence theorems are established for the decomposition of deterministic models into elementary sub-networks. The linear coding capacity for computation is characterized for all channel parameters considered in the model for a countably infinite class of networks. The constructive coding schemes introduced herein for a specific class of networks provide an optimistic viewpoint for the application of structured codes in network communication.

Providing adaptive shared control for Brain-Computer Interfaces (BCIs) can result in better performance while reducing the user's mental workload. In this respect, online estimation of accuracy and speed of command delivery are important factors. This study aims at real-time differentiation between fast and slow trials in a motor imagery BCI. In our experiments, we refer to trials shorter than the median of trial lengths as “fast” trials and to those longer than the median as “slow” trials. We propose a classifier for real-time distinction between fast and slow trials based on estimates of the entropy rates for the first 2-3 s of the electroencephalogram (EEG). Results suggest that it can be predicted whether a trial is slow or fast well before a cutoff time. This is important for adaptive shared control especially because 55% to 75% of trials (for the five subjects in this study) are longer than that cutoff time.

This paper develops a new communication strategy, ergodic interference alignment, for theK-user interference channel with time-varying fading. At any particular time, each receiver will see a superposition of the transmitted signals plus noise. The standard approach to such a scenario results in each transmitter-receiver pair achieving a rate proportional to 1/Kits interference-free ergodic capacity. However, given two well-chosen time indices, the channel coefficients from interfering users can be made to exactly cancel. By adding up these two observations, each receiver can obtain its desired signal without any interference. If the channel gains have independent, uniform phases, this technique allows each user to achieve at least 1/2 its interference-free ergodic capacity at any signal-to-noise ratio. Prior interference alignment techniques were only able to attain this performance as the signal-to-noise ratio tended to infinity. Extensions are given for the case where each receiver wants a message from more than one transmitter as well as the “X channel” case (with two receivers) where each transmitter has an independent message for each receiver. Finally, it is shown how to generalize this strategy beyond Gaussian channel models. For a class of finite field interference channels, this approach yields the ergodic capacity region.

Recovery of the sparsity pattern (or support) of an unknown sparse vector from a limited number of noisy linear measurements is an important problem in compressed sensing. In the high-dimensional setting, it is known that recovery with a vanishing fraction of errors is impossible if the measurement rate and the per-sample signal-to-noise ratio (SNR) are finite constants, independent of the vector length. In this paper, it is shown that recovery with an arbitrarily small but constant fraction of errors is, however, possible, and that in some cases computationally simple estimators are near-optimal. Bounds on the measurement rate needed to attain a desired fraction of errors are given in terms of the SNR and various key parameters of the unknown vector for several different recovery algorithms. The tightness of the bounds, in a scaling sense, as a function of the SNR and the fraction of errors, is established by comparison with existing information-theoretic necessary bounds. Near optimality is shown for a wide variety of practically motivated signal models.

List-decoding for arbitrarily varying channels (AVCs) under state constraints is investigated. It is shown that rates within ϵ of the randomized coding capacity of AVCs with input-dependent state can be achieved under maximal error with list-decoding using lists of size O(1/ϵ). Under the average error criterion, an achievable rate and converse bound are given for lists of size L . These bounds are based on two different notions of symmetrizability and do not coincide in general. An example is given which shows that for list size L , the capacity may be positive but strictly smaller than the randomized coding capacity, in contrast to the situation without constraints.

In this paper we study the problem of data exchange, where each node in the system has a number of linear combinations of the data packets. Communicating over a public channel, the goal is for all nodes to reconstruct the entire set of the data packets in minimal total number of bits exchanged over the channel. We present a novel divide and conquer based architecture that determines the number of bits each node should transmit. This along with the well known fact, that it is sufficient for the nodes to broadcast linear combinations of their local information, provides a polynomial time deterministic algorithm for reconstructing the entire set of the data packets at all nodes in minimal amount of total communication.

The Compute-and-Forward approach has been proven to be very beneficial for communication over Gaussian networks. While the theoretical results are promising, it is still not completely understood how to best apply this scheme in practice. The objective of this work is to provide a low complexity scheme suitable for Compute-and-Forward. The scheme is based on utilizing linear codes over ℤqwhere q is not restricted to be prime and allows to achieve high transmission rates following Ungerboeck's set partitioning principle.

A major challenge in sparsity pattern estimation is that small modes are difficult to detect in the presence of noise. This problem is alleviated if one can observe samples from multiple realizations of the nonzero values for the same sparsity pattern. We will refer to this as “diversity”. Diversity comes at a price, however, since each new realization adds new unknown nonzero values, thus increasing uncertainty. In this paper, upper and lower bounds on joint sparsity pattern estimation are derived. These bounds, which improve upon existing results even in the absence of diversity, illustrate key tradeoffs between the number of measurements, the accuracy of estimation, and the diversity. It is shown, for instance, that diversity introduces a tradeoff between the uncertainty in the noise and the uncertainty in the nonzero values. Moreover, it is shown that the optimal amount of diversity significantly improves the behavior of the estimation problem for both optimal and computationally efficient estimators.

We show that the recently proposed integer-forcing linear receiver provides an attractive approach to the problem of mitigating external interference in MIMO channels. The integer-forcing receiver proceeds by first decoding a set of full rank integer linear combinations of the data streams. The resulting full rank equations are then inverted to find the original data. By selecting equation coefficients in a direction that depends on both the interference space and the channel matrix, the impact of external interference can be effectively reduced. We show that this technique attains a non-trivial gain over traditional linear receivers. Furthermore, the integer-forcing linear receiver achieves the same generalized degrees of freedom for the M×M MIMO channel with K dimensional external interference as the joint decoder.

A multiplicative Gaussian wire-tap channel inspired by compressed sensing is studied. Lower and upper bounds on the secrecy capacity are derived, and shown to be relatively tight in the large system limit for a large class of compressed sensing matrices. Surprisingly, it is shown that the secrecy capacity of this channel is nearly equal to the capacity without any secrecy constraint provided that the channel of the eavesdropper is strictly worse than the channel of the intended receiver. In other words, the eavesdropper can see almost everything and yet learn almost nothing. This behavior, which contrasts sharply with that of many commonly studied wiretap channels, is made possible by the fact that a small number of linear projections can make a crucial difference in the ability to estimate sparse vectors.

A fundamental problem in dynamic frequency reuse is that the cognitive radio is ignorant of the amount of interference it inflicts on the primary license holder. Policies that attempt to limit interference without the active participation of the primary are thus difficult to implement. However, many wireless systems use flow control feedback such as ARQs. By listening to these control signals, a cognitive radio can obtain indirect information about the interference it generates and thus behave in an acceptable manner. This paper introduces an information-theoretic model of this basic observation and develops and analyzes algorithms that can exploit it. In particular, a simple generic strategy is proposed where the cognitive radio monitors the primary's effective packet rate and only transmits when that rate is above a threshold. The strategy is shown to have important universality properties with respect to unknown time-varying interference characteristics as well as favorable delay properties.

When two or more users in a wireless network transmit simultaneously, their electromagnetic signals are linearly superimposed on the channel. As a result, a receiver that is interested in one of these signals sees the others as unwanted interference. This property of the wireless medium is typically viewed as a hindrance to reliable communication over a network. However, using a recently developed coding strategy, interference can in fact be harnessed for network coding. In a wired network, (linear) network coding refers to each intermediate node taking its received packets, computing a linear combination over a finite field, and forwarding the outcome towards the destinations. Then, given an appropriate set of linear combinations, a destination can solve for its desired packets. For certain topologies, this strategy can attain significantly higher throughputs over routing-based strategies. Reliable physical layer network coding takes this idea one step further: using judiciously chosen linear error-correcting codes, intermediate nodes in a wireless network can directly recover linear combinations of the packets from the observed noisy superpositions of transmitted signals. Starting with some simple examples, this paper explores the core ideas behind this new technique and the possibilities it offers for communication over interference-limited wireless networks.

Capacity bounds are compared for four different deterministic models of wireless networks, representing four different ways of handling broadcast and superposition in the physical layer. In particular, the transport capacity under a multiple unicast traffic pattern is studied for a 1-D network of regularly spaced nodes on a line and for a 2-D network of nodes placed on a hexagonal lattice. The considered deterministic models are: (i) P/P, a model with exclusive transmission and reception, (ii) P/M, a model with simultaneous reception of the sum of the signals transmitted by all nearby nodes, (iii) B/P, a model with simultaneous transmission to all nearby nodes but exclusive reception, and (iv) B/M, a model with both simultaneous transmission and simultaneous reception. All four deterministic models are considered under half-duplex constraints. For the 1-D scenario, it is found that the transport capacity under B/M is twice that under P/P. For the 2-D scenario, it is found that the transport capacity under B/M is at least 2.5 times, and no more than six times, the transport capacity under P/P. The transport capacities under P/M and B/P fall between these bounds.

Interference is usually viewed as an obstacle to communication in wireless networks. This paper proposes a new strategy, compute-and-forward, that exploits interference to obtain significantly higher rates between users in a network. The key idea is that relays should decode linear functions of transmitted messages according to their observed channel coefficients rather than ignoring the interference as noise. After decoding these linear equations, the relays simply send them towards the destinations, which given enough equations, can recover their desired messages. The underlying codes are based on nested lattices whose algebraic structure ensures that integer combinations of codewords can be decoded reliably. Encoders map messages from a finite field to a lattice and decoders recover equations of lattice points which are then mapped back to equations over the finite field. This scheme is applicable even if the transmitters lack channel state information.

In the distributed linear source coding problem a set of distributed sensors observe subsets of a data vector, and provide the fusion center with linearly encoded data. The goal is to determine the encoding matrix of each sensor such that the fusion center reconstructs the entire data vector with minimum mean square error (MSE). The recently proposed local Karhunen Loève transform (KLT) approach performs this task by optimally determining the encoding matrix of each sensor assuming the other matrices are fixed. This approach is implemented iteratively until convergence is reached. Herein, we propose a greedy-based non-iterative algorithm. In each step, one of the encoding matrices is updated by appending an additional row. The algorithm selects in a greedy fashion one sensor that provides the largest improvement in MSE, and terminates when all the encoding matrices reach their predefined encoded data size. The algorithm can be implemented recursively, and it reduces the complexity from cubic dependency on the data size, using the iterative method, to quadratic dependency. This makes it a prime candidate for on-line and real-time implementations of the distributed KLT. Simulation results show that for many covariance matrix types, the MSE performance of the suggested algorithm is equivalent to the iterative approach.

In this work we study the problem of key agreement over a public noiseless channel when Alice, Bob and Charlie observe discrete memoryless sources of an unknown distribution. Alice and Bob want to agree on a key KABthat is protected from Charlie. At the same time, Alice and Charlie want to agree on a key KACthat is protected from Bob. In order to construct codebooks for the key agreement, Alice has to know how the sources are distributed. Therefore, she requests Bob and Charlie to send her sufficient information about their observations. We also assume that Bob and Charlie, besides agreeing with Alice on the keys, want to learn as much as possible about the other user's key: we call this quantity the leakage. We model these reports by having Bob and Charlie select discrete memoryless channels and passing their true observations through them. We approach this problem from a game-theoretic point of view. For a class of Bob and Charlie's objective functions which are linear in the key rate and the leakage rate, we characterize a Nash equilibrium. Also, we propose a strategy that Alice can apply in order to ensure that Bob and Charlie's honest reporting is a Nash equilibrium.

The field of compressed sensing has shown that a sparse but otherwise arbitrary vector can be recovered exactly from a small number of randomly constructed linear projections (or samples). The question addressed in this paper is whether an even smaller number of samples is sufficient when there exists prior knowledge about the distribution of the unknown vector, or when only partial recovery is needed. An information-theoretic lower bound with connections to free probability theory and an upper bound corresponding to a computationally simple thresholding estimator are derived. It is shown that in certain cases (e.g. discrete valued vectors or large distortions) the number of samples can be decreased. Interestingly though, it is also shown that in many cases no reduction is possible.

Linear receivers are often used to reduce the implementation complexity of multiple antenna systems. In a traditional linear receiver architecture, the receive antennas are used to separate out the codewords sent by each transmit antenna, which can then be decoded individually. Although easy to implement, this approach can be highly sub-optimal when the channel matrix is near singular. In this paper, we develop a new linear architecture that uses the receive antennas to create an effective channel matrix with integer-valued entries. Instead of attempting to recover a transmitted codeword directly, each decoder recovers a different integer combination of the codewords according to the effective channel matrix. If the effective channel is full rank, these linear equations can be digitally solved for the original codewords. By allowing the receiver to equalize the channel to any matrix with integer entries, this scheme can outperform traditional linear architectures such as decorrelators and MMSE receivers while maintaining a similar complexity. Furthermore, in the case where each transmit antenna encodes an independent data stream, the proposed receiver attains the optimal diversity multiplexing tradeoff.

Polar codes are the first codes to provably achieve capacity on the symmetric binary-input discrete memoryless channel (B-DMC) with low encoding and decoding complexity. The parity check matrix of polar codes is high-density and we show that linear program (LP) decoding fails on the fundamental polytope of the parity check matrix. The recursive structure of the code permits a sparse factor graph representation. We define a new polytope based on the fundamental polytope of the sparse graph representation. This new polytope P is defined in a space of dimension O(N logN) where N is the block length. We prove that the projection of P in the original space is tighter than the fundamental polytope based on the parity check matrix. The LP decoder over P obtains the ML-certificate property. In the case of the binary erasure channel (BEC), the new LP decoder is equivalent to the belief propagation (BP) decoder operating on the sparse factor graph representation, and hence achieves capacity. Simulation results of SC (successive cancellation) decoding, LP decoding over tightened polytopes, and (ML) maximum likelihood decoding are provided. For channels other than the BEC, we discuss why LP decoding over P with a linear objective function is insufficient.

We propose a new framework for MIMO decoding based on a recently developed technique for reliably conveying linear equations over wireless channels. Each transmit antenna sends an independent data stream using the same linear code. As a result, any integer combination of the codewords is itself a codeword. Each receive antenna observes a random complex-valued combination of the codewords according to the fading coefficients. We use a linear pre-processing step at the receiver to transform the effective channel into a (full-rank) integer matrix. A single stream decoder is then used to recover integer combinations of the codewords. These equations of codewords are then translated into equations of the transmitted data streams over a finite field which can be easily solved for the original data. We examine the performance of our scheme in terms of the probability of outage and show that significant gains are possible over standard linear architectures for both i.i.d. and correlated Rayleigh fading.

Shannon's discovery of digital communication has shaped the architecture of virtually all communication systems in use today. The digital communication paradigm is built around the notion of bits and uses careful coding to deliver bits reliably end-to-end. It has been shown that this architectural principle can lead to a very significant performance penalty in wireless sensor networks. For a limited class of network scenarios, it was shown that optimal architectures are analog in nature, simple and scalable. In this paper, we show that more generally, simple analog architectures crucially depend on feedback to the sensors. Interesting questions then concern the amount of feedback needed and the resulting trade-off with performance. This paper provides rules-of-thumb for the selection of the number of feedback bits.

In this paper, sensor network scenarios are considered where the underlying signals of interest exhibit a degree of sparsity, which means that in an appropriate basis, they can be expressed in terms of a small number of nonzero coefficients. Following the emerging theory of compressive sensing (CS), an overall architecture is considered where the sensors acquire potentially noisy projections of the data, and the underlying sparsity is exploited to recover useful information about the signals of interest, which will be referred to as distributed sensor perception. First, we discuss the question of which projections of the data should be acquired, and how many of them. Then, we discuss how to take advantage of possible joint sparsity of the signals acquired by multiple sensors, and show how this can further improve the inference of the events from the sensor network. Two practical sensor applications are demonstrated, namely, distributed wearable action recognition using low-power motion sensors and distributed object recognition using high-power camera sensors. Experimental data support the utility of the CS framework in distributed sensor perception.

The utility of limited feedback for coding over an individual sequence of discrete memoryless channels is investigated. This study complements recent results showing how limited or noisy feedback can boost the reliability of communication. A strategy with fixed input distributionPis given that asymptotically achieves rates arbitrarily close to the mutual information induced byPand the state-averaged channel. When the capacity-achieving input distribution is the same over all channel states, this achieves rates at least as large as the capacity of the state-averaged channel, sometimes called the empirical capacity.

Information theory has been used as an organizing principle in neuroscience for several decades. Estimates of the mutual information (MI) between signals acquired in neurophysiological experiments are believed to yield insights into the structure of the underlying information processing architectures. With the pervasive availability of recordings from many neurons, several information and redundancy measures have been proposed in the recent literature. A typical scenario is that only a small number of stimuli can be tested, while ample response data may be available for each of the tested stimuli. The resulting asymmetric information estimation problem is considered. It is shown that the direct plug-in information estimate has a negative bias. An anthropic correction is introduced that has a positive bias. These two complementary estimators and their combinations are natural candidates for information estimation in neuroscience. Tail and variance bounds are given for both estimates. The proposed information estimates are applied to the analysis of neural discrimination and redundancy in the avian auditory system.

A fundamental problem in wireless networks is determining the broadcast capacity, i.e., the maximum data transfer rate from a given node to every other node in a relay network. This paper studies the scaling of the broadcast capacity for a network with a single source and N destinations, of which f(N) are randomly selected to also act as relays. In high-density networks (i.e., the node density goes to infinity; the network area is fixed), it is shown that the broadcast capacity is upper bounded by Θ(log f(N)). Schemes are provided that achieve i) Θ(log f(N)) throughput if the channel fading is spatially continuous; ii) Θ(log log f(N)) throughput if the channel fading is spatially i.i.d.. For extended networks (i.e., the node density is fixed; the network area goes to infinity), the broadcast capacity is upper bounded by Θ(1) under channel models with fading and path-loss exponent α > 2. A multistage cooperative broadcasting scheme, which achieves Θ(1) broadcast rate for the high-density extended networks with pathloss channel model is proposed. These results quantifies the gains obtained due to cooperation compared to multihop noncooperative broadcasting, which has a maximum rate that scales as Θ(1) for high-density and Θ(1/(log f(N))α/2) for extended networks.

The arbitrarily varying channel (AVC) is a channel model whose state is selected maliciously by an adversary. Fixed-blocklength coding assumes a worst-case bound on the adversary's capabilities, which leads to pessimistic results. This paper defines a variable-length perspective on this problem, for which achievable rates are shown that depend on the realized actions of the adversary. Specifically, rateless codes are constructed which require a limited amount of common randomness. These codes are constructed for two kinds of AVC models. In the first the channel state cannot depend on the channel input, and in the second it can. As a by-product, the randomized coding capacity of the AVC with state depending on the transmitted codeword is found and shown to be achievable with a small amount of common randomness. The results for this model are proved using a randomized strategy based on list decoding.

A network in which sensors observe a common Gaussian source is analyzed. Using a fixed linear transform, each sensor compresses its high-dimensional observation into a low-dimensional representation. The latter is provided to a central decoder that reconstructs the source according to a mean squared error (MSE) distortion metric. The distributed Karhunen-Loeve Transform (d-KLT) has been shown to provide a (locally) optimal linear solution for compression at each sensor. While the d-KLT achieves the lowest distortion linear reconstruction known, it does not maintain a nested subspace structure. In the case of ideal links to the decoder, this paper presents transforms that maintain nested subspaces, allowing the decoder to approximate a delay-limited source in an online fashion according to a desired sensor schedule. A distortion envelope for one distributed transform with nested subspace properties (d-nested-KLT) is provided. In the case of i.i.d. noise to the decoder, under assumptions of power allocation over subspaces, it is also possible to achieve nested subspaces utilizing correlations between sensors' observations. Results are applicable for data access over networks, and online information processing in sensor networks.

In this paper, we study a gossip algorithm for distributed averaging over a wireless sensor network. The usual assumption is that, through properly chosen codes, the physical layer is reduced to a set of reliable bit pipes for the distributed averaging algorithm. However, with a new channel coding technique, computation coding, we can exploit the interference property of the wireless medium for efficient averaging. This then provides a new abstraction for the physical layer: reliable linear equations instead of reliable bit pipes. The ldquoneighborhood gossiprdquo algorithm operates modularly on top of this abstraction. We will show that for certain regimes, such an approach can lead to energy savings that are exponential in the network size and time savings that are polynomial.

A linear compressive network (LCN) is defined as a graph of sensors in which each encoding sensor compresses incoming jointly Gaussian random signals and transmits (potentially) low-dimensional linear projections to neighbors over a noisy uncoded channel. Each sensor has a maximum power to allocate over signal subspaces. The networks of focus are acyclic, directed graphs with multiple sources and multiple destinations. LCN pathways lead to decoding leaf nodes that estimate linear functions of the original high dimensional sources by minimizing a mean squared error (MSE) distortion cost function. An iterative optimization of local compressive matrices for all graph nodes is developed using an optimal quadratically constrained quadratic program (QCQP) step. The performance of the optimization is marked by power-compression-distortion spectra, with converse bounds based on cut-set arguments. Examples include single layer and multi-layer (e.g. p-layer tree cascades, butterfly) networks. The LCN is a generalization of the Karhunen-Loeve Transform to noisy multi-layer networks, and extends previous approaches for point-to-point and distributed compression-estimation of Gaussian signals. The framework relates to network coding in the noiseless case, and uncoded transmission in the noisy case.

Confidential communication aided by a relay without security clearance is studied. General strategies and outer bounds are derived for the problem of secret communication and secret key generation when correlated observations at all terminals are available. In a variation of the problem, it is assumed that the quality of the channel to the relay is known only to the relay. If the throughput-maximizing strategy is used according to the relay's claimed channel quality, the question is: what should the relay claim about the channel in order to maximize its eavesdropping capabilities? We propose a strategy that Alice and Bob may agree on in order to suppress any leakage of confidential communication between the source and the receiver.

Consider a K-user interference channel with timevarying fading. At any particular time, each receiver will see a signal from most transmitters. The standard approach to such a scenario results in each transmitter-receiver pair achieving a rate proportional to 1/K the single user rate. However, given two well chosen time indices, the channel coefficients from interfering users can be made to exactly cancel. By adding up these two signals, the receiver can see an interference-free version of the desired transmission. We show that this technique allows each user to achieve at least half its interference-free ergodic capacity at any SNR. Prior work was only able to show that half the interference-free rate was achievable as the SNR tended to infinity. We examine a finite field channel model and a Gaussian channel model. In both cases, the achievable rate region has a simple description and, in the finite field case, we prove it is the ergodic capacity region.

In this paper, we demonstrate the advantage of the inherent algebraic structure of lattice codes, for the uplink channel of a cellular deployment. The out-of-cell interference is assumed to be symmetric, as in Wyner's model. We employ a new relaying technique, compute-and-forward, which allows cell-sites to decode equations of the transmitted bits by exploiting the channel interference. However, the standard compute-and-forward technique is penalized whenever the channel coefficients are non-integer. We develop a superposition strategy to mitigate this penalty. By using part of the power towards a private message, we can effectively modify the channel seen by compute-and-forward. We demonstrate that, in certain regimes, this mixed strategy significantly outperforms decode-and-forward, compress-and-forward, and ordinary compute-and-forward.

Most information-theoretic analyses of communication systems with feedback assume perfect output feedback. For multiaccess channels, this feedback can enable cooperation between users. However, as shown by a simple example, the rate required by the feedback link may exceed the capacity gains in the forward link. It is therefore of interest to look at systems where the feedback is rate-limited. For the compound multiaccess channel zero-rate feedback can tune the communication system to the realized channel, but for discrete memoryless channel the capacity region under zero-rate feedback is the same as that without feedback.

In many network communication scenarios, a relay in the network may only need to recover and retransmit an equation of the transmitted messages. In previous work, it has been shown that if each transmitter employs the same lattice code, the interference structure of the channel can be exploited to recover an equation much more efficiently than possible with standard multiple-access strategies. Here, we generalize this compute-and-forward framework to the multiple antenna setting. Our results show that it is often beneficial to use extra antennas at the receiver to rotate the channel coefficients towards the nearest integer vector instead of separating out the transmitted signals. We also demonstrate that in contrast to classical strategies, the multiplexing gain of compute-and-forward increases if the transmitters have channel state information. Finally, we apply our scheme to the two way relay network and observe performance gains over traditional strategies.

In large relay networks, the assumption of full and perfect channel knowledge at the destination is optimistic in practice. The fading coefficients are typically measured at the relays but not directly known at the destination. Traditionally, each fading coefficient is individually forwarded to the destination. However, it is often sufficient for the decoder to know only a function of the various channel states rather than the full information. We develop a general framework for forwarding channel state information in relay systems with local channel knowledge. We apply our framework to several networks and find that functional forwarding of channel state information can be attained much more efficiently than full forwarding.

A novel estimator for mutual information is proposed. The estimator is useful for the (asymmetric) scenario where only a few samples for one random variable are available, but for each sample, the conditional distribution of the other random variable can be accurately characterized. Such asymmetry is common in neuroscience where it is often necessary to repeat the same stimulus many times to obtain a stable response.

In this work, we study a communication scheme in which nodes transmit sufficient statistics of their observations over non-orthogonal medium access channels for distributed estimation. This scheme unifies and generalizes several multiple access schemes such as uncoded transmissions of Gaussian observations and type-based multiple access. For the exponential family of distributions, we show that the sufficient-statistic based multiple access (SSBMA) achieves the Cramer-Rao bound on the estimation error asymptotically. Further, we argue that such an optimality result only applies to the exponential family of distributions. In addition, we present a simplified and unified analysis of asymptotic distribution of estimation error for a very general class of communication schemes and estimators. The proposed analysis method reduces the computation of asymptotic estimation error to mere calculation of derivatives. With the proposed technique, we analyze the performance of various communication schemes with optimal and suboptimal estimators and with i.i.d. (independent and identically distributed) data.

A generalization of the additive Gaussian two-way channel toMusers is considered. Such channels contain implicit feedback in the sense that the channel output signals observed by the different encoders are correlated. While the benefits of feedback are shown to be negligible at high SNR, for moderate SNR, feedback can play a significant role in boosting the sum-rate performance. To highlight this potential gain, the special case of theM-user multiway channel with a common output is considered. By taking insights from Kramerpsilas Fourier MEC, a feedback strategy is introduced and shown to strictly dominate the performance of a pre-log optimal non-feedback strategy. Furthermore, an upper bound is derived to show this feedback strategy achieves the sum-rate capacity beyond a certain SNR threshold. Under per-symbol power constraints, this upper bound can be tightened to show the feedback strategy is sum-rate optimal for all SNR values.

For a centralized encoder and decoder, a channel matrix is simply a set of linear equations that can be transformed into parallel channels. We develop a similar approach to multi-user networks: we view interference as creating linear equations of codewords and that a receiverpsilas goal is to collect a full rank set of such equations. Our new relaying technique, compute-and-forward, uses structured codes to reliably compute functions over channels. This allows the relays to efficiently recover a linear functions of codewords without recovering the individual codewords. Thus, our scheme can work with the structure of the interference while removing the effects of the noise at the relay. We apply our scheme to a Gaussian relay network with interference and achieve better rates than either compress-and-forward or decode-and-forward for certain regimes.

It is well known that the support of a sparse signal can be recovered from a small number of random projections. However, in the presence of noise all known sufficient conditions require that the per-sample signal-to-noise ratio (SNR) grows without bound with the dimension of the signal. If the noise is due to quantization of the samples, this means that an unbounded rate per sample is needed. In this paper, it is shown that an unbounded SNR is also a necessary condition for perfect recovery, but any fraction (less than one) of the support can be recovered with bounded SNP. This means that a finite rate per sample is sufficient for partial support recovery. Necessary and sufficient conditions are given for both stochastic and non-stochastic signal models. This problem arises in settings such as compressive sensing, model selection, and signal denoising.

A deterministic dirty-paper coding strategy for communication over an arbitrarily varying channel with an interference signal known to the transmitter is investigated. The presence of a known interference signal at the transmitter is shown to provide some protection against jamming interference. For some values of the parameters the scheme is capacity- achieving. Applications to watermarking and spectrum-sharing channels are described.

A generic intuition says that the pre-log, or multiplexing gain, cannot be larger than the minimum of the number of transmit and receive dimensions. This suggests that for the scalar broadcast channel, the pre-log cannot exceed one. By contrast, in this note, we show that when the noises are anti-correlated and feedback is present, then a pre-log of two can be attained. In other words, in this special case, in the limit of high SNR, the scalar Gaussian broadcast channel turns into two parallel AWGN channels. Achievability is established via a coding strategy due to Schalkwijk, Kailath, and Ozarow.

A single memoryless Gaussian source is observed by many terminals, subject to independent Gaussian observation noises. The terminals are linked to a fusion center via a standard Gaussian multiple-access channel. The fusion center needs to recover the underlying Gaussian source with respect to mean-squared error. In this correspondence, a theorem of Witsenhausen is shown to imply that an optimal communication strategy is uncoded transmission, i.e., each terminal's channel input is merely a scaled version of its noisy observation.

We study a problem motivated by cognitive radio in which the primary is a packet system that employs ARQ feedback. A secondary system is allowed to transmit in the same frequency band provided it ensures that the primary attains a specified target rate. That is, the secondary has a certain "interference budget". The crux of the problem is that the secondary does not know how much interference it creates on the primary and therefore is ignorant of its interference budget. Absent this knowledge, we propose a scheme in which the secondary eavesdrops on the primary's ARQ and uses this knowledge to stay within its interference budget. Under certain assumptions, we show there exists an optimal rate-interference budget (RIB) tradeoff. We compare how far fixed strategies are from this RIB function as we vary the interference budget. Further, we exhibit a strategy that is optimal beyond a threshold interference budget and within 1 bit per primary packet elsewhere.

Recently, Shayevitz and Feeler introduced an individual sequence formulation of channel coding under model uncertainty and an elegant coding strategy that adapts Horstein's scheme to this setting to achieve the empirical capacity of the channel. Their scheme requires both full-rate output feedback and common randomness. We present a strategy in the style of Hybrid ARQ that requires no output feedback by using common randomness and zero-rate active feedback. This strategy still asymptotically achieves the empirical capacity.

We consider the problem of computing the sum of independent Gaussian sources over a Gaussian multiple-access channel (MAC) with respect to a mean-squared error criterion. When the source and channel bandwidths are equal, the best separation-based solution to this problem performs exponentially worse in a distortion sense compared to the optimal solution: uncoded transmission. In this paper, we develop lattice codes for exploiting the structure of the Gaussian MAC when there are more channel uses than source symbols. We also demonstrate the usefulness of these codes in determining the multicast capacity of a simple AWGN network.

Coding over channels whose state can depend non- causally on the entire transmitted codeword and message are studied. The channel model is a variation on the arbitrarily varying channel (AVC) with state constraints. The randomized coding capacity of this channel is shown to be equal to the randomized coding capacity Crin the case where the jammer does not know the codeword, and common randomness of O (log n) bits is sufficient to achieve this capacity.

Capacity is often studied under constraints on the channel input signals. This paper investigates the behavior of capacity when constraints are placed on the channel output signal (as well as generalizations thereof). While such a change in perspective leaves the point-to-point problem (essentially) unchanged, the main conclusion is that in certain network scenarios, including multiple-access and relay situations, both the structure of the problem and the conclusions change. For example, capacity results are found for the many-user Gaussian multiple-access channel (MAC) with arbitrarily dependent sources, cooperation, or feedback, and for the nondegraded Gaussian relay network. The investigations are motivated by recent questions arising in spectrum sharing and dynamic spectrum allocation: Multiple independent networks share the same frequency band, but are spatially mostly disjoint. One approach to grant coexistence is via spatial interference power restrictions, imposed at the network level, rather than at the device level. The corresponding capacity question is posed and partially answered in this paper

The thirty-four papers in this special issue are devoted to models, theories, and codes for relaying and cooperation in communication networks. The demand for large, more efficient, reliable, and cost effective communication networks is motivating new network architectures for cellular and wireless communications as well as cognitive radio and sensor networks.

The problem of reliably reconstructing a function of sources over a multiple-access channel (MAC) is considered. It is shown that there is no source–channel separation theorem even when the individual sources are independent. Joint source–channel strategies are developed that are optimal when the structure of the channel probability transition matrix and the function are appropriately matched. Even when the channel and function are mismatched, these computation codes often outperform separation-based strategies. Achievable distortions are given for the distributed refinement of the sum of Gaussian sources over a Gaussian multiple-access channel with a joint source–channel lattice code. Finally, computation codes are used to determine the multicast capacity of finite-field multiple-access networks, thus linking them to network coding.

The successful design of sensor network architectures depends crucially on the structure of the sampling, observation, and communication processes. One of the most fundamental questions concerns the sufficiency of discrete approximations in time, space, and amplitude. In the case of space and time, the question can be rephrased as whether there is a spatio-temporal sampling theorem for typical data sets in sensor networks. This question has a positive answer in many cases of interest. The issue of discretization of amplitudes is more subtle and can be expressed as the question of whether there is a (source/channel) separation theorem for typical sensor networks. We show that this question has a negative answer in general and that the price of separation can be large. To illustrate these issues, we review the underlying theory and discuss specific examples

A decode-and-forward LDPC-based coding and decoding scheme is proposed and applied to the BAWGN single-relay channel. The source broadcasts information to both the relay and the destination. The relay is able to simultaneously receive and transmit. Both the relay and the destination apply successive iterative decoding using belief propagation. In the proposed scheme, the LDPC code used by the source and the LDPC code used by the relay are designed independently of each outer: optimality properties of this approach are established via information-theoretic upper and lower bounds. Asymptotic analysis shows that the performance of the proposed scheme can be as close as 0.02 dB away from the theoretical limit for any decode-and-forward scheme, and simulation results show that its performance for a block code of length 214can be within 0.55 dB away from the same limit with a corresponding bit error probability of ~10-6

We study the problem of multicasting over a network of multiple-access channels (MACs). The separation-based solution to this problem is to reduce each MAC to a set of noiseless bit pipes via a channel code and then employ network coding. Sometimes, however, the physical-layer structure of the MAC can be exploited more advantageously. In many cases of interest, the MAC output is a (deterministic) function of its inputs, corrupted by noise. We develop structured codes to exploit the natural function of a MAC to reliably compute functions as part of a network code and show that in many scenarios of interest our scheme outperforms the separation-based solution. If each MAC can be written as a sum over some finite field plus noise, then our achievable rate coincides with the max-flow min-cut bound

The random coding capacity of the Gaussian arbitrarily varying channel (GAVC) under a maximal probability of error criterion is equal to that of an additive white Gaussian noise (AWGN) channel with the interference power as additional noise. The deterministic coding capacity under an average probability of error criterion is zero if the transmitter power does not exceed the interference power. We show that the random coding capacity for average probability error is the same as that for maximal probability of error and that the randomization need only be over a sub-exponential number of codebooks. The achievable error exponent is related to the amount of randomization. An application of these results to the degraded broadcast channel is discussed

An efficient distributed source coding system with two encoders and dependent data streams must remove two kinds of redundancy: redundancy in each stream and between the two streams. The striking result of Slepian and Wolf showed that the latter can be eliminated even if each encoder only observes one of the source streams. The coding technique that permits to achieve this is often referred to as "binning." In large source networks, binning can result in considerable savings in terms of encoding rate. The focus of this paper is on the scaling-law behavior, i.e., the characteristic performance in the limit as the source network size tends to infinity. For paradigmatic network topologies, we analyze the rate savings through binning, and we show that in some cases of interest, binning is scaling-law irrelevant.

Dependence balance bounds of Hekstra and Willems are generalized and refined. The new bounds are applied to the K-user multiaccess channel (MAC) with output feedback, and they are shown to establish the feedback sum-rate capacity for the Gaussian MAC when all users have the same per-symbol power constraints. The sum-rate capacity is achieved by Fourier modulated estimate correction. The feedback sum-rate capacity is shown to improve the no-feedback capacity by only log log K nats per use for large K. The new bounds also improve on cut-set bounds for asymmetric powers and rates.

The Karhunen-Loeve transform (KLT) is a key element of many signal processing and communication tasks. Many recent applications involve distributed signal processing, where it is not generally possible to apply the KLT to the entire signal; rather, the KLT must be approximated in a distributed fashion. This paper investigates such distributed approaches to the KLT, where several distributed terminals observe disjoint subsets of a random vector. We introduce several versions of the distributed KLT. First, a local KLT is introduced, which is the optimal solution for a given terminal, assuming all else is fixed. This local KLT is different and in general improves upon the marginal KLT which simply ignores other terminals. Both optimal approximation and compression using this local KLT are derived. Two important special cases are studied in detail, namely, the partial observation KLT which has access to a subset of variables, but aims at reconstructing them all, and the conditional KLT which has access to side information at the decoder. We focus on the jointly Gaussian case, with known correlation structure, and on approximation and compression problems. Then, the distributed KLT is addressed by considering local KLTs in turn at the various terminals, leading to an iterative algorithm which is locally convergent, sometimes reaching a global optimum, depending on the overall correlation structure. For compression, it is shown that the classical distributed source coding techniques admit a natural transform coding interpretation, the transform being the distributed KLT. Examples throughout illustrate the performance of the proposed distributed KLT. This distributed transform has potential applications in sensor networks, distributed image databases, hyper-spectral imagery, and data fusion

In some remote sensing applications, the functional relationship between the source being observed and the sensor readings may not be known. Because of communication constraints, this uncertainty may result in poor end-to-end distortion. If the sensors have some knowledge of their joint statistics, they may be able to communicate collaboratively to combat the channel noise. A model is proposed for capturing some of the uncertainty in the observation process, called a fading observation model. An example with fading observations is analysed. For M sensors with no fading there exists a scheme for which the achievable distortion scales with M as M/sup -1/, but with fading the distortion does not scale with M. In this paper, a one-bit feedback scheme is presented that provides enough information about the joint statistics to achieve scaling rates like M/sup -1/3/. Additional feedback improves the achievable scaling rate. For comparison, a scheme based on separate source and channel coding at best gives a distortion scaling behaviour of (log M)/sup -1/. Some extensions to multiple sources and observation models with unknown delay are discussed.

In the CEO problem, introduced by Berger et al, IEEE Trans. Info. Theory, 1996, a CEO is interested in a source that cannot be observed directly. M agents observe independently noisy versions of the source and, without collaborating, must encode these across noiseless rate-constrained channels to the CEO. The quadratic AWGN CEO problem refers to the class of CEO problems for which the agents view the source through additive white Gaussian noise, and the distortion is squared error. This paper discusses two upper bounds to the CEO sum-rate distortion function for this class of problems. The first follows from elementary arguments. It permits two conclusions. First, the worst case is when the underlying source is Gaussian (for fixed variance). Second, there are source distributions that lead to a significantly better behavior. The second upper bound follows from a new bound on the rate loss between the CEO and the remote rate-distortion function. For certain source distributions and certain ranges of distortion, this bound is better than the first

We introduce a new problem of broadcast source coding with a discrimination requirement - there is an eavesdropping user from whom we wish to withhold the true message in an entropic sense. Binning can achieve the Slepian-Wolf rate, but at the cost of full information leakage to the eavesdropper. Our main result is a lower bound that implies that any entropically efficient broadcast scheme must be "like binning" in that it also must leak significant information to eavesdroppers

For the point-to-point additive white Gaussian noise (AWGN) channel with noiseless feedback and an average power constraint, Schalkwijk and Kailath's scheme achieves a doubly-exponential decay of the probability of error. While some coding schemes for networks with noiseless feedback incorporate variations on the Schalkwijk-Kailath scheme, they do not in general achieve better than single-exponential decays in their probabilities of error everywhere in their achievable rate regions. We give a technique that can boost the reliability as high as desired of any from a large class of block coding schemes for networks with feedback. The technique relies crucially on the average nature of the power constraints. We explain and illustrate our results in the context of Ozarow's feedback strategy for the AWGN multiple-access channel

For a class of sensor networks, the task is to monitor an underlying physical phenomenon over space and time through an imperfect observation process. The sensors can communicate back to a central data collector over a noisy channel. The key parameters in such a setting are the fidelity (or distortion) at which the underlying physical phenomenon can be estimated by the data collector, and the cost of operating the sensor network. This is a network joint source-channel communication problem, involving both compression and communication. It is well known that these two tasks may not be addressed separately without sacrificing optimality, and the optimal performance is generally unknown. This paper presents a lower bound on the best achievable end-to-end distortion as a function of the number of sensors, their total transmit power, the number of degrees of freedom of the underlying source process, and the spatio-temporal communication bandwidth. Particular coding schemes are studied, and it is shown that in some cases, the lower bound is tight in a scaling-law sense. By contrast, it is shown that the standard practice of separating source from channel coding may incur an exponential penalty in terms of communication resources, as a function of the number of sensors. Hence, such code designs effectively prevent scalability. Finally, it is outlined how the results extend to cases involving missing synchronization and channel fading.

The capacity of a particular large Gaussian relay network is determined in the limit as the number of relays tends to infinity. Upper bounds are derived from cut-set arguments, and lower bounds follow from an argument involving uncoded transmission. It is shown that in cases of interest, upper and lower bounds coincide in the limit as the number of relays tends to infinity. Hence, this paper provides a new example where a simple cut-set upper bound is achievable, and one more example where uncoded transmission achieves optimal performance. The findings are illustrated by geometric interpretations. The techniques developed in this paper are then applied to a sensor network situation. This is a network joint source-channel coding problem, and it is well known that the source-channel separation theorem does not extend to this case. The present paper extends this insight by providing an example where separating source from channel coding does not only lead to suboptimal performance-it leads to an exponential penalty in performance scaling behavior (as a function of the number of nodes). Finally, the techniques developed in this paper are extended to include certain models of ad hoc wireless networks, where a capacity scaling law can be established: When all nodes act purely as relays for a single source-destination pair, capacity grows with the logarithm of the number of nodes.

Coding strategies that exploit node cooperation are developed for relay networks. Two basic schemes are studied: the relays decode-and-forward the source message to the destination, or they compress-and-forward their channel outputs to the destination. The decode-and-forward scheme is a variant of multihopping, but in addition to having the relays successively decode the message, the transmitters cooperate and each receiver uses several or all of its past channel output blocks to decode. For the compress-and-forward scheme, the relays take advantage of the statistical dependence between their channel outputs and the destination's channel output. The strategies are applied to wireless channels, and it is shown that decode-and-forward achieves the ergodic capacity with phase fading if phase information is available only locally, and if the relays are near the source node. The ergodic capacity coincides with the rate of a distributed antenna array with full cooperation even though the transmitting antennas are not colocated. The capacity results generalize broadly, including to multiantenna transmission with Rayleigh fading, single-bounce fading, certain quasi-static fading problems, cases where partial channel knowledge is available at the transmitters, and cases where local user cooperation is permitted. The results further extend to multisource and multidestination networks such as multiaccess and broadcast relay channels.

In this paper, we investigate properties of good coding strategies for a class of wireless sensor networks that could be termed "monitoring" networks: their task is to monitor an underlying physical reality at the highest possible fidelity. Since the sensed signals are often analog, and the communication channels noisy, it is not generally possible to exactly communicate the sensed signals. Rather, such sensor network scenarios involve both a compression and a communication problem. It is well known that these two tasks must be addressed jointly for optimal performance, but optimal performance is unknown in general. This problem is addressed from a scaling-law perspective in this paper, i.e., as the number of nodes becomes large. The goal of the paper is to characterize the key properties of coding strategies that achieve the optimum scaling behavior, and hence to identify the scaling-law relevant issues in code design. We first present a lower bound to the cost-distortion tradeoff, and then compare two fundamentally different coding strategies to that lower bound.

In this paper, we discuss a framework for the distributed compression of vector sources, based on our previous work on distributed transform coding (2002, 2003). In particular, our goal is to develop a strategy of first applying a suitable distributed Karhunen-Loeve transform, whereafter each component can be handled by standard distributed compression techniques. In the present paper, we first study the scenario where all but one terminal furnish a noisy approximation of their observation. For the case where the underlying vector is Gaussian, and the added noise is also Gaussian, we establish that indeed it is optimal for the last terminal to apply a (local) transform to its observations, and to separately compress each component in the transform domain. Then, we outline how this leads to a general simple distributed compression strategy for Gaussian vector sources: each terminal applies a suitable local transform to its observations, and encodes the resulting components separately in a Wyner-Ziv fashion, i.e., treating the compressed descriptions of all other terminals as side information available to the decoder. This achieves the best known performance. The optimum performance in unknown to date.

The goal of a class of sensor networks is to monitor an underlying physical reality at the highest possible fidelity. Sensors acquire noisy measurements and have to communicate them over a power- and possibly bandwidth-constrained interference channel to a set of base stations. The goal of this paper is to analyze, as a function of the number of sensors, the trade-offs between the degrees of freedom of the underlying physical reality, the communication resources (power, temporal and spatial bandwidth), and the resulting distortion at which the physical reality can be estimated by the base stations. The distortion can be expressed as the sum of two fundamentally different terms. The first term reflects the fact that the measurements are noisy. It depends on the number of sensors and on their locations, but it cannot be influenced by the communication resources. The second contribution to the distortion can be controlled by the communication resources, and the key question becomes: What resources are necessary to make it decay at least as fast as the first distortion term, as a function of the number of sensors? This question is answered threefold: First, a lower bound to the power-bandwidth trade-o is derived, showing that at least a constant to linearly increasing total power is required for typical cases (as a function of M). But is this also sufficient? In the second answer, communication strategies are considered where each sensor applies the best possible distributed compression algorithm, followed by capacity-achieving channel codes. For such a separation strategy, it is shown for typical cases that the power must increase exponentially as a function of the number of sensors, suggesting that the lower bound derived in this paper is far too optimistic. However, in the third answer, it is shown that this is not the case: For some example scenarios, the power requirements of the lower bound are indeed achievable, but joint source-channel coding is required. Finally, the problem of sensor synchronization is considered, and it is shown that the scaling laws derived in this paper continue to hold under a Rician fading model.

This paper suggests a simple cut-set argument to bound the optimum trade-offs, by combining the capacity-cost function of the channel with the rate-distortion function of the source.

For a class of sensor networks, the task is to monitor an underlying physical phenomenon over space and time through a noisy observation process. The sensors can communicate back to a data collector over a noisy channel. The key parameters in such a setting are the fidelity at which the underlying physical phenomenon can be estimated by a central data collector, and the cost of operating the communication network. This paper presents a lower bound to the scaling behavior of sensor networks

Performance limits for multiple-access channels are well known as long as the messages of different nodes are independent. Considerable research efforts have been devoted to the problem when the source information is dependent across nodes, revealing capacities for certain special cases. This work presents a new scenario for which conclusive results can be established: The additive white Gaussian multiple-access channel under a constraint on the power at the receiver. The results of this paper have natural applications to sensor networks. By contrast to recent scaling-law results, this paper establishes coinciding upper and lower bounds, and hence, the exact performance limits, for some scenarios of interest.

This paper provides bounds on the rate-distortion region for the distributed compression scenario where two (or more) sources are compressed separately for a decoder that has access to side information. Conclusive rate-distortion results are found for the case where the sources are conditionally independent, given the side information.

The Karhunen-Loeve transform (KLT) is a key element of many signal processing tasks, including approximation, compression, and classification. Many recent applications involve distributed signal processing where it is not generally possible to apply the KLT to the signal; the KLT must be approximated in a distributed fashion. Investigations were carried out on the distributed approximations to the KLT. First, explicit solutions to special cases were presented including a partial KLT, a conditional KLT, and the combination of these two special cases. These results were used to derive an algorithm that finds the best distributed approximation to the KLT. Applications of the results from sensor networks and distributed databases were discussed.

Distributed ways of communicating, processing, and sensing are replacing more traditional centralized architectures. An early example of this revolution in distributed communications is appearing in the form of sensor networks, which are densely distributed networks of embedded signal sensors, controls and processors. These nodes could be simple signal sensors, but could also be cameras and microphones. In this distributed scenario, there are several interesting topics to investigate that span from traditional signal processing problems (i.e. sampling, compression, detection) to communication and information theory (i.e. transmission protocols, capacity bounds for ad-hoc networks). This paper reviews some recent results on the topic of source representations and distributed source coding and transmission.

Feedback may greatly simplify the coding techniques needed to achieve the (information-theoretically) optimum performance. This is true both for the capacity problem and for the joint source-channel coding problem. We are interested in the latter. Gaussian examples involving feedback have appeared in the literature (Cruise, T.J., 1967; Kailath, T., 1967; Schalkwijk, J.P.M. and Bluestein, L.I., 1967). We present a general matching condition for source-channel communication with feedback, extending our previous results for the case without feedback (Gastpar, M. et al., Proc. IEEE Int. Symp. Inf. Theory, p.236, 2000; IEEE Trans. Inf. Theory, 2003). This condition permits, for example, the characterizing of instances of source/channel pairs for which very simple yet optimal feedback coding strategies exist, and leads to an understanding of the potential offered by feedback, and how to exploit it.

What makes a source-channel communication system optimal? It is shown that in order to achieve an optimal cost-distortion tradeoff, the source and the channel have to be matched in a probabilistic sense. The match (or lack of it) involves the source distribution, the distortion measure, the channel conditional distribution, and the channel input cost function. Closed-form necessary and sufficient expressions relating the above entities are given. This generalizes both the separation-based approach as well as the two well-known examples of optimal uncoded communication. The condition of probabilistic matching is extended to certain nonergodic and multiuser scenarios. This leads to a result on optimal single-source broadcast communication.

Gupta and Kumar (see IEEE Transactions an Information Theory, vol.46, no.2, p.388-404, 2000) determined the capacity of wireless networks under certain assumptions, among them point-to-point coding, which excludes for example multi-access and broadcast codes. We consider essentially the same physical model of a wireless network under a different traffic pattern, namely the relay traffic pattern, but we allow for arbitrarily complex network coding. In our model, there is only one active source/destination pair, while all other nodes assist this transmission. We show code constructions leading to achievable rates and derive upper bounds from the max-flow min-cut theorem. It is shown that lower and upper bounds meet asymptotically as the number of nodes in the network goes to infinity, thus proving that the capacity of the wireless network with n nodes under the relay traffic pattern behaves like log n bits per second. This demonstrates also that network coding is essential: under the point-to-point coding assumption considered by Gupta et al., the achievable rate is constant, independent of the number of nodes. Moreover, the result of this paper has implications' and extensions to fading channels and to sensor networks.

It is known that in the absence of distortion, the necessary sampling density for a multiband signal is given by its spectral occupancy. However, in general, the samples have to be acquired nonuniformly. There exist sampling patterns such that reconstruction is feasible even if the actual spectral support of the multiband signal is not known. If the samples are distorted, an increased sampling density may lead to a superior performance. In this paper, we consider the case of small distortion due to fine quantization of the samples, and we derive a necessary condition on the optimal sampling density.