We study lossy source coding under a distortion measure defined by the negative log-likelihood induced by a prescribed conditional distribution $P_{X|U}$. This \emph{log-likelihood distortion} models compression settings in which the reconstruction is a semantic representation from which the source can be probabilistically generated, rather than a pointwise approximation. We formulate the corresponding rate-distortion problem and characterize fundamental properties of the resulting rate-distortion function, including its connections to lossy compression under log-loss, classical rate-distortion problems with arbitrary distortion measures, and rate-distortion with perfect perception.

We consider the problem of non-coherent over-the-air computation (AirComp), where$n$devices carry highdimensional data vectors$\mathrm{x}_{i} \in \mathbb{R}^{d}$of sparsity$\left\vert\mathrm{x}_{i}\right\vert_{0} \leq k$and the sum of these data vectors has to be computed at a receiver. Previous results on non-coherent AirComp require more than$d$channel uses to compute functions of$\mathrm{x}_{i}$, where the extra redundancy is used to combat non-coherent signal aggregation. However, if the data vectors are sparse, sparsity can be exploited to offer significantly cheaper communication. In this paper, we propose to use random transforms to transmit lower-dimensional projections$s_{i} \in \mathbb{R}^{T}$of the data vectors. These projected vectors are communicated to the receiver using a majority vote (MV)AirComp scheme, which estimates the bit-vector corresponding to the signs of the aggregated projections, i.e.,$\mathbf{y}=\text{sign}\left(\sum_{i} \mathbf{s}_{i}\right)$. By leveraging 1-bit compressed sensing (1bCS) at the receiver, the real-valued and high-dimensional aggregate$\sum_{i} \mathrm{x}_{i}$can be recovered from$y$. We prove analytically that the proposed MVCS scheme estimates the aggregate data vector$\sum_{i} \mathrm{x}_{i}$with$\ell_{2}$-norm error$\epsilon$in$T=\mathcal{O}\left(k n \log (d) / \epsilon^{2}\right)$channel uses. We consider distributed histogram estimation, a canonical building block for federated analytics, as an aplication for MVCS where the data vectors$\mathrm{x}_{i}$are inherently 1 -sparse. Our numerical evaluations demonstrate that our scheme achieves the same order of communication cost as state-of-the-art methods while avoiding the complexity and overhead of additional cryptographic tools.

We study how inherent randomness in the training process—where each sample (or client in federated learning) contributes only to a randomly selected portion of training—can be leveraged for privacy amplification. This includes (1) data partitioning, where a sample participates in only a subset of training iterations, and (2) model partitioning, where a sample updates only a subset of the model parameters. We apply our framework to model parallelism in federated learning, where each client updates a randomly selected subnetwork to reduce memory and computational overhead, and show that existing methods, e.g. model splitting or dropout, provide a significant privacy amplification gain not captured by previous privacy analysis techniques. Additionally, we introduce balanced iteration subsampling, a new data partitioning method where each sample (or client) participates in a fixed number of training iterations. We show that in certain regimes, this method yields stronger privacy amplification than Poisson (i.i.d.) sampling of data (or clients). Our results demonstrate that randomness in the training process, which is structured rather than i.i.d. and interacts with data in complex ways, can be systematically leveraged for nontrivial privacy amplification.

We consider inferring a stationary ergodic source by lossily compressing observations of the source made through a memoryless noisy channel. By bounding the deviation of the empirical joint distribution of source, observation, and inference output from satisfying a Markov property, we give an exact characterization of the loss achieved. We show that this analysis is applicable to general memoryless noise channels by deliberately choosing the distortion measure for the lossy compressor to match the channel conditional distribution. Consequences of these results are given in the specific cases of MSE and Hamming loss. A comparison is made to an indirect rate-distortion perspective on the problem.

This survey article focuses on the emerging connections between machine learning and data compression. While the fundamental limits of classical (lossy) data compression are well-established through rate-distortion theory, recent advancements have uncovered new theoretical analyses and application areas inspired by machine learning. We review recent works on task-based and goal-oriented compression, rate-distortion-perception theory, and compression for estimation and inference. Deep learning-based approaches have provided natural, data-driven methods for compression. Accordingly, we survey recent efforts in applying deep learning techniques to task-based or goal-oriented compression, as well as image/video compression and transmission. Additionally, we discuss the potential use of large language models for text compression. Finally, we outline future research directions in this promising field.

Experiment design has a rich history dating back over a century and has found many critical applications across various fields since then. The use and collection of users’ data in experiments often involve sensitive personal information, so additional measures to protect individual privacy are required during data collection, storage, and usage. In this work, we focus on the rigorous protection of users’ privacy (under the notion of differential privacy (DP)) while minimizing the trust toward service providers. Specifically, we consider the estimation of the average treatment effect (ATE) under DP, while only allowing the analyst to collect population-level statistics via secure aggregation, a distributed protocol enabling a service provider to aggregate information without accessing individual data. Although a vital component in modern A/B testing workflows, private distributed experimentation has not previously been studied. To achieve DP, we design local privatization mechanisms that are compatible with secure aggregation and analyze the utility, in terms of the width of confidence intervals, both asymptotically and non-asymptotically. We show how these mechanisms can be scaled up to handle the very large number of participants commonly found in practice. In addition, when introducing DP noise, it is imperative to cleverly split privacy budgets to estimate both the mean and variance of the outcomes and carefully calibrate the confidence intervals according to the DP noise. Last, we present comprehensive experimental evaluations of our proposed schemes and show the privacy-utility trade-offs in experiment design.

We consider the problem of secure histogram es-timation, where$n$users hold private items xifrom a size-d domain and a server aims to estimate the histogram of the user items. Previous results utilizing orthogonal communication schemes have shown that this problem can be solved securely with a total communication cost of O(n2log(d)) bits by hiding each item xiwith a mask. In this paper, we offer a different approach to achieving secure aggregation. Instead of masking the data, our scheme protects individuals by aggregating their messages via a multiple-access channel. A naive communication scheme over the multiple-access channel requires$d$channel uses, which is generally worse than the O(n21og(d)) bits communication cost of the prior art in the most relevant regime$d$>>$n$. Instead, we propose a new scheme that we call Over-the-Air Group Testing (AirG T) which uses group testing codes to solve the histogram estimation problem in O(n log(d)) channel uses. AirGT reconstructs the histogram exactly with a vanishing probability of error Perror= O(d-T) that drops exponentially in the number of channel uses$T$.

Van Trees inequality, also known as the Bayesian Cramér- Rao lower bound, is a powerful tool for establishing lower bounds for minimax estimation through Fisher information. It easily adapts to different statistical models and often yields tight bounds. Recently, its application has been extended to distributed estimation with privacy and communication constraints where it yields order-wise optimal minimax lower bounds for various parametric tasks under squared$L_{2}$loss. However, a widely perceived drawback of the van Trees inequality is that it is limited to squared$L_{2}$loss. The goal of this paper is to dispel that perception by introducing a strengthened version of the van Trees inequality that applies to general$L_{q}$loss functions by building on the Efroimovich's inequality - a lesser-known entropic inequality dating back to the$1970\mathrm{s}$. We then apply the generalized van Trees inequality to lower bound$L_{q}$loss in distributed minimax estimation under communication and local differential privacy constraints. This leads to lower bounds for$L_{q}$loss that apply to sequentially interactive and blackboard communication protocols. Additionally, we show how the generalized van Trees inequality can be used to obtain local and non-asymptotic minimax results that capture the hardness of estimating each instance at finite sample sizes.

Local differential privacy is a powerful method for privacy-preserving data collection. In this paper, we develop a framework for training Generative Adversarial Networks (GANs) on differentially privatized data. We show that entropic regularization of optimal transport - a popular regularization method in the literature that has often been leveraged for its computational benefits - enables the generator to learn the raw (unprivatized) data distribution even though it only has access to privatized samples. We prove that at the same time this leads to fast statistical convergence at the parametric rate. This shows that entropic regularization of optimal transport uniquely enables the mitigation of both the effects of privatization noise and the curse of dimensionality in statistical convergence. The omitted proofs can be found in the full version of the paper https://arxiv.org/abs/2306.09547

To reduce the communication cost of differential privacy mechanisms, we introduce a novel construction, called Poisson private representation (PPR), designed to compress and simulate any local randomizer while ensuring local differential privacy. Unlike previous simulation-based local differential privacy mechanisms, PPR exactly preserves the joint distribution of the data and the output of the original local randomizer. Hence, the PPR-compressed privacy mechanism retains all desirable statistical properties of the original privacy mechanism such as unbiasedness and Gaussianity. Moreover, PPR achieves a compression size within a logarithmic gap from the theoretical lower bound. Using the PPR, we give a new order-wise trade-off between communication, accuracy, central and local differential privacy for distributed mean estimation. Experiment results on distributed mean estimation show that PPR consistently gives a better trade-off between communication, accuracy and central differential privacy compared to the coordinate subsampled Gaussian mechanism, while also providing local differential privacy.

Generative Adversarial Networks (GANs) are a popular method for learning distributions from data by modeling the target distribution as a function of a known distribution. The function, often referred to as the generator, is optimized to minimize a chosen distance measure between the generated and target distributions. One commonly used measure for this purpose is the Wasserstein distance. However, Wasserstein distance is hard to compute and optimize, and in practice entropic regularization techniques are used to facilitate its computation and improve numerical convergence. The influence of regularization on the learned solution, however, remains not well-understood. In this paper, we study how several popular entropic regularizations of Wasserstein distance impact the solution learned by a Wasserstein GAN in a simple benchmark setting where the generator is linear and the target distribution is high-dimensional Gaussian. We show that entropy regularization of Wasserstein distance promotes sparsification of the solution, while replacing the Wasserstein distance with the Sinkhorn divergence recovers the unregularized solution. The significant benefit of both regularization techniques is that they remove the curse of dimensionality suffered by Wasserstein distance. We show that in both cases the optimal generator can be learned to accuracy $\epsilon$ with $O(1/\epsilon^2)$ samples from the target distribution without requiring to constrain the discriminator. We thus conclude that these regularization techniques can improve the quality of the generator learned from empirical data in a way that is applicable for a large class of distributions.

We consider the federated frequency estimation problem, where each user holds a private item $X_i$ from a size-$d$ domain and a server aims to estimate the empirical frequency (i.e., histogram) of $n$ items with $n \ll d$. Without any security and privacy considerations, each user can communicate its item to the server by using $\log d$ bits. A naive application of secure aggregation protocols would, however, require $d\log n$ bits per user. Can we reduce the communication needed for secure aggregation, and does security come with a fundamental cost in communication? In this paper, we develop an information-theoretic model for secure aggregation that allows us to characterize the fundamental cost of security and privacy in terms of communication. We show that with security (and without privacy) $\Omega\left( n \log d \right)$ bits per user are necessary and sufficient to allow the server to compute the frequency distribution. This is significantly smaller than the $d\log n$ bits per user needed by the naive scheme but significantly higher than the $\log d$ bits per user needed without security. To achieve differential privacy, we construct a linear scheme based on a noisy sketch that locally perturbs the data and does not require a trusted server (a.k.a. distributed differential privacy). We analyze this scheme under $\ell_2$ and $\ell_\infty$ loss. By using our information-theoretic framework, we show that the scheme achieves the optimal accuracy-privacy trade-off with optimal communication cost, while matching the performance in the centralized case where data is stored in the central server.

We consider the group testing problem over probabilistic community-oriented infection models, which have attracted significant attention in the wake of the COVID-19 pandemic. To the best of our knowledge, existing theoretical results on the complexity of group testing in such settings are derived under the assumption that tests are noiseless. We present novel upper and lower bounds for the noisy case, focusing on adaptive group testing schemes tailored to the community structure of the population. For the achievability result, we devise an algorithm which incorporates knowledge of the community structure into a noisy binary search procedure from [1]. Our algorithm exhibits favorable performance in the context of the recently-introduced stochastic block infection model [2]. Furthermore, our lower bound applies to any adaptive algorithm, any probabilistic infection model, and any (noisy or noiseless) testing model satisfying certain natural criteria, and thus can be of independent interest.

Privacy and communication constraints are two major bottlenecks in federated learning (FL) and analytics (FA). We study the optimal accuracy of mean and frequency estimation (canonical models for FL and FA respectively) under joint communication and $(\varepsilon, \delta)$-differential privacy (DP) constraints. We consider both the central and the multi-message shuffled DP models. We show that in order to achieve the optimal $\ell_2$ error under $(\varepsilon, \delta)$-DP, it is sufficient for each client to send $\Theta\left( n \min\left(\varepsilon, \varepsilon^2\right)\right)$ bits for FL %{\color{blue}(assuming the dimension $d \gg n \min\left(\varepsilon, \varepsilon^2\right)$)} and $\Theta\left(\log\left( n\min\left(\varepsilon, \varepsilon^2\right) \right)\right)$ bits for FA to the server, where $n$ is the number of participating clients. Without compression, each client needs $O(d)$ bits and $O\left(\log d\right)$ bits for the mean and frequency estimation problems respectively (where $d$ corresponds to the number of trainable parameters in FL or the domain size in FA), meaning that we can get significant savings in the regime $ n \min\left(\varepsilon, \varepsilon^2\right) = o(d)$, which is often the relevant regime in practice. We propose two different ways to leverage compression for privacy amplification and achieve the optimal privacy-communication-accuracy trade-offs. In both cases, each client communicates only partial information about its sample and we show that privacy is amplified by randomly selecting the part contributed by each client. In the first method, the random selection is revealed to the server, which results in a central DP guarantee with optimal privacy-communication-accuracy trade-offs. In the second method, the random data parts from the clients are shuffled by a secure shuffler resulting in a multi-message shuffling scheme with the same optimal trade-offs. As a result, we establish the optimal three-way trade-offs between privacy, communication, and accuracy for both the central DP and multi-message shuffling frameworks.

Graph Neural Networks (GNNs) have proven to be highly effective in solving real-world learning problems that involve graph-structured data. However, GNNs can also inadvertently expose sensitive user information and interactions through their model predictions. To address these privacy concerns, Differential Privacy (DP) protocols are employed to control the trade-off between provable privacy protection and model utility. Applying standard DP approaches to GNNs directly is not advisable due to two main reasons. First, the prediction of node labels, which relies on neighboring node attributes through graph convolutions, can lead to privacy leakage. Second, in practical applications, the privacy requirements for node attributes and graph topology may differ. In the latter setting, existing DP-GNN models fail to provide multigranular trade-offs between graph topology privacy, node attribute privacy, and GNN utility. To address both limitations, we propose a new framework termed Graph Differential Privacy (GDP), specifically tailored to graph learning. GDP ensures both provably private model parameters as well as private predictions. Additionally, we describe a novel unified notion of graph dataset adjacency to analyze the properties of GDP for different levels of graph topology privacy. Our findings reveal that DP-GNNs, which rely on graph convolutions, not only fail to meet the requirements for multigranular graph topology privacy but also necessitate the injection of DP noise that scales at least linearly with the maximum node degree. In contrast, our proposed Differentially Private Decoupled Graph Convolutions (DPDGCs) represent a more flexible and efficient alternative to graph convolutions that still provides the necessary guarantees of GDP. To validate our approach, we conducted extensive experiments on seven node classification benchmarking and illustrative synthetic datasets. The results demonstrate that DPDGCs significantly outperform existing DP-GNNs in terms of privacy-utility trade-offs.

We study the mean estimation problem under communication and local differential privacy constraints. While previous work has proposed order-optimal algorithms for the same problem (i.e., asymptotically optimal as we spend more bits), exact optimality (in the non-asymptotic setting) still has not been achieved. In this work, we take a step towards characterizing the exact-optimal approach in the presence of shared randomness (a random variable shared between the server and the user) and identify several conditions for exact optimality. We prove that one of the conditions is to utilize a rotationally symmetric shared random codebook. Based on this, we propose a randomization mechanism where the codebook is a randomly rotated simplex -- satisfying the properties of the exact-optimal codebook. The proposed mechanism is based on a $k$-closest encoding which we prove to be exact-optimal for the randomly rotated simplex codebook.

Group testing was conceived during World War II to identify soldiers infected with syphilis using as few tests as possible, and it has attracted renewed interest during the COVID-19 pandemic. A long-standing assumption in the probabilistic variant of the group testing problem is that individuals are infected by the diseaseindependently. However, this assumption rarely holds in practice, as diseases often spread through interactions between individuals and therefore cause infections to be correlated. Inspired by characteristics of COVID-19 and other infectious diseases, we introduce an infection model over networks which generalizes the traditional i.i.d. model from probabilistic group testing. Under this model, we ask whether knowledge of the network structure can be leveraged to perform group testing more efficiently, focusing specifically on community-structured graphs drawn from the stochastic block model. We prove that a simple community-aware algorithm outperforms the baseline binary splitting algorithm when the model parameters are conducive to “strong community structure.” Moreover, our novel lower bounds imply that the community-aware algorithm is order-optimal in certain parameter regimes. We extend our bounds to the noisy setting and support our results with numerical experiments.

The optimal transport problem studies how to transport one measure to another in the most cost-effective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand’s celebrated transportation cost inequality. Following Marton’s approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this new inequality to network information theory. We show that it can be used to recover almost immediately a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.

Two major challenges in distributed learning and estimation are 1) preserving the privacy of the local samples; and 2) communicating them efficiently to a central server, while achieving high accuracy for the end-to-end task. While there has been significant interest in addressing each of these challenges separately in the recent literature, treatments that simultaneously address both challenges are still largely missing. In this paper, we develop novel encoding and decoding mechanisms that simultaneously achieve optimal privacy and communication efficiency in various canonical settings. In particular, we consider the problems of mean estimation and frequency estimation under$\varepsilon $-local differential privacy and$b$-bit communication constraints. For mean estimation, we propose the SQKR mechanism, a scheme based on Kashin’s representation and random sampling, with order-optimal estimation error under both constraints. We further apply SQKR to distributed SGD and obtain a communication efficient and (locally) differentially private distributed SGD protocol. For frequency estimation, we present the RHR mechanism, a scheme that leverages the recursive structure of Walsh-Hadamard matrices and achieves order-optimal estimation error for all privacy levels and communication budgets. As a by-product, we also construct a distribution estimation mechanism that is rate-optimal for all privacy regimes and communication constraints, extending recent work that is limited to$b=1$and$\varepsilon =O(1)$. Our results demonstrate that intelligent encoding under joint privacy and communication constraints can yield a performance that matches the optimal accuracy achievable under either constraint alone. In other words, the optimal performance is determined by the more stringent of the two constraints, and the less stringent constraint can be satisfied for free.

We study the asymptotic performance of the Thompson sampling algorithm in the batched multi-armed bandit setting where the time horizon$T$is divided into batches, and the agent is not able to observe the rewards of her actions until the end of each batch. We show that in this batched setting, Thompson sampling achieves the same asymptotic performance as in the case where instantaneous feedback is available after each action, provided that the batch sizes increase subexponentially. This result implies that Thompson sampling can maintain its performance even if it receives delayed feedback in$\omega (\log T)$batches. We further propose an adaptive batching scheme that reduces the number of batches to$O(\log \log T)$while maintaining the same performance. Although the batched multi-armed bandit setting has been considered in several recent works, previous results rely on tailored algorithms for the batched setting, which optimize the batch structure and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. We show that Thompson sampling, on the other hand, is able to achieve a similar asymptotic performance in the batched setting without any modifications.

We introduce the Poisson Binomial mechanism (PBM), a discrete differential privacy mechanism for distributed mean estimation (DME) with applications to federated learning and analytics. We provide a tight analysis of its privacy guarantees, showing that it achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism. Our analysis is based on a novel bound on the Rényi divergence of two Poisson binomial distributions that may be of independent interest. Unlike previous discrete DP schemes based on additive noise, our mechanism encodes local information into a parameter of the binomial distribution, and hence the output distribution is discrete with bounded support. Moreover, the support does not increase as the privacy budget goes to zero as in the case of additive schemes which require the addition of more noise to achieve higher privacy; on the contrary, the support becomes smaller as eps goes to zero. The bounded support enables us to combine our mechanism with secure aggregation (SecAgg), a multi-party cryptographic protocol, without the need of performing modular clipping which results in an unbiased estimator of the sum of the local vectors. This in turn allows us to apply it in the private FL setting and provide an upper bound on the convergence rate of the SGD algorithm. Moreover, since the support of the output distribution becomes smaller as $\varepsilon \ra 0$, the communication cost of our scheme decreases with the privacy constraint $\varepsilon$, outperforming all previous distributed DP schemes based on additive noise in the high privacy or low communication regimes.

We consider the problem of estimating a d-dimensional, s-sparse discrete distribution from independent samples subject to a joint b-bit communication constraint and ε-local differential privacy constraint. As an intermediate step, we introduce the Privatized Random Hashing (PRH) scheme, which concatenates a hashing-based quantization strategy with the randomized response privacy mechanism. Despite its simplicity, PRH turns out to achieve the order-optimal minimax estimation error and sample complexity in the standard (non-sparse) estimation setting, for all communication and privacy regimes. We then address the sparse case by developing a two-stage, non-interactive estimation scheme based on PRH in which the first half of samples are used to localize the unknown support of the distribution, and the remaining samples are used to obtain precise estimates of the individual probabilities. Using this scheme, we characterize the minimax sample complexity of the sparse case up to logarithmic factors, unifying existing results in the literature that considered communication and privacy constraints separately.

We study schemes and lower bounds for distributed minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss. Our framework combines statistical estimation and wireless communication. First, we develop “analog” joint estimation-communication schemes that exploit the superposition property of the Gaussian MAC. We characterize their risk in terms of the number of nodes and dimension of the parameter space. Then, we derive information-theoretic lower bounds on the minimax risk of any estimation scheme that is restricted to communicate the samples over a given number of uses of the channel. This shows that the risk achieved by our proposed schemes is within a logarithmic factor of these lower bounds. We compare both achievability and lower bound results to previous “digital” lower bounds, where nodes transmit errorless bits at the Shannon capacity of the MAC. Our key finding is that analog estimation schemes that leverage the physical layer offer a drastic reduction in estimation error over digital schemes relying on a physical-layer abstraction.

The fourth call for papers of the Series on Machine Learning in Communications and Networks has continued to receive a great number of high-quality papers covering various aspects of intelligent communications, from which we have included 16 original contributions in this issue. In the following, we provide a brief review of these papers according to their topics.

The third call for papers of the Series on Machine Learning in Communications and Networks has continued to receive a great number of high-quality papers covering various aspects of intelligent communications, from which we have included 26 original contributions in this issue. In the following, we provide a brief review of key contributions of papers in this issue according to their topics.

The fourth (and final) call for papers of the Series on Machine Learning in Communications and Networks has continued to receive a great number of high-quality papers covering various aspects of intelligent communications. In addition to those published in the August issue, we include in this issue 16 articles submitted to the call. In the following, we provide a brief review of these articles according to their topics.

We consider the problem of estimating a $d$-dimensional $s$-sparse discrete distribution from its samples observed under a $b$-bit communication constraint. The best-known previous result on $\ell_2$ estimation error for this problem is $O\left( \frac{s\log\left( {d}/{s}\right)}{n2^b}\right)$. Surprisingly, we show that when sample size $n$ exceeds a minimum threshold $n^*(s, d, b)$, we can achieve an $\ell_2$ estimation error of $O\left( \frac{s}{n2^b}\right)$. This implies that when $n>n^*(s, d, b)$ the convergence rate does not depend on the ambient dimension $d$ and is the same as knowing the support of the distribution beforehand. We next ask the question: ``what is the minimum $n^*(s, d, b)$ that allows dimension-free convergence?'. To upper bound $n^*(s, d, b)$, we develop novel localization schemes to accurately and efficiently localize the unknown support. For the non-interactive setting, we show that $n^*(s, d, b) = O\left( \min \left( {d^2\log^2 d}/{2^b}, {s^4\log^2 d}/{2^b}\right) \right)$. Moreover, we connect the problem with non-adaptive group testing and obtain a polynomial-time estimation scheme when $n = \tilde{\Omega}\left({s^4\log^4 d}/{2^b}\right)$. This group testing based scheme is adaptive to the sparsity parameter $s$, and hence can be applied without knowing it. For the interactive setting, we propose a novel tree-based estimation scheme and show that the minimum sample-size needed to achieve dimension-free convergence can be further reduced to $n^*(s, d, b) = \tilde{O}\left( {s^2\log^2 d}/{2^b} \right)$.

Since the inception of the group testing problem in World War II, one of the prevailing assumptions in the probabilistic variant of the problem has been that individuals in the population are infected by a disease independently. However, this assumption rarely holds in practice, as diseases typically spread through interactions between individuals and therefore cause infections to be correlated. Inspired by characteristics of COVID-19 and similar diseases, we consider an infection model over networks which generalizes the traditional i.i.d. model from probabilistic group testing. Under this infection model, we ask whether knowledge of the network structure can be leveraged to perform group testing more efficiently, focusing specifically on community-structured graphs drawn from the stochastic block model. We prove that when the network and infection parameters are conducive to “strong community structure;” our proposed adaptive, graph-aware algorithm outperforms the baseline binary splitting algorithm, and is even order-optimal in certain parameter regimes. A full version of this paper is accessible at http://arxiv.org/abs/2101.0240S. Omitted proofs and numerical experiments are provided in the full version

We propose a new technique for deriving the differential privacy parameters in federated learning (FL). We consider the setting where a machine learning model is iteratively trained using stochastic gradient descent (SGD) and only the last update is publicly released. In this approach, we interpret each training iteration as a Markov kernel. We then quantify the impact of the kernel on privacy parameters via the contraction coefficient of the$E_{\gamma}$-divergence that underlies differential privacy. To do so, we generalize the well-known Dobrushin's ergodicity coefficient, originally defined in terms of total variation distance, to a family of$f$-divergences. We then analyze the convergence rate of SGD under the proposed private FL framework.

We consider the processing of statistical samples$X\sim P_{\theta}$by a channel$p(y\vert x)$, and characterize how the statistical information from the samples for estimating the parameter$\theta\in \mathbb{R}^{d}$can scale with the mutual information or capacity of the channel. We show that if the statistical model has a sub-Gaussian score function, then the trace of the Fisher information matrix for estimating$\theta$from$Y$can scale at most linearly with the mutual information between$X$and$Y$. We apply this result to obtain minimax lower bounds in distributed statistical estimation problems, and obtain a tight preconstant for Gaussian mean estimation. We then show how our Fisher information bound can also imply mutual information or Jensen-Shannon divergence based distributed strong data processing inequalities.

We study the asymptotic performance of the Thompson sampling algorithm in the batched multi-armed bandit setting where the time horizon$T$is divided into batches, and the agent is not able to observe the rewards of her actions until the end of each batch. We show that in this batched setting, Thompson sampling achieves the same asymptotic performance as in the case where instantaneous feedback is available after each action, provided that the batch sizes increase subexponentially. This result implies that Thompson sampling can maintain its performance even if it receives delayed feedback in ω(log T) batches. We further propose an adaptive batching scheme that reduces the number of batches to Θ(log T) while maintaining the same performance. Although the batched multi-armed bandit setting has been considered in several recent works, previous results rely on tailored algorithms for the batched setting, which optimize the batch structure and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. We show that Thompson sampling, on the other hand, is able to achieve a similar asymptotic performance in the batched setting without any modifications.

We study lower bounds for minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss, using techniques from both statistical estimation and information theory. We characterize these bounds in terms of the number of nodes$n$and the dimension of the parameter space$d$, showing that the risk must be$\Omega(d/n\log n)$. This is within a$\log n$factor of previous analog achievability results. While lower bounds for minimax statistical estimation have been previously studied under quantization constraints that abstract the physical layer as noiseless bit pipes, to our knowledge our paper provides the first lower bounds for statistical estimation over noisy multi-user channels. This adds to a body of works showing how analog schemes that consider the physical layer jointly with the estimation scheme, can outperform digital schemes that separate the two with an abstraction layer.

Generative Adversarial Networks (GANs) are a popular method for learning distributions from data by modeling the target distribution as a function of a known distribution. The function, often referred to as the generator, is optimized to minimize a chosen distance measure between the generated and target distributions. One commonly used measure for this purpose is the Wasserstein distance. However, Wasserstein distance is hard to compute and optimize, and in practice entropic regularization techniques are used to facilitate its computation and improve numerical convergence. The influence of regularization on the learned solution, however, remains not well-understood. In this paper, we study how several popular entropic regularizations of Wasserstein distance impact the solution learned by a Wasserstein GAN in a simple benchmark setting where the generator is linear and the target distribution is high-dimensional Gaussian. We show that entropy regularization of Wasserstein distance promotes sparsification of the solution, while replacing the Wasserstein distance with the Sinkhorn divergence recovers the unregularized solution. The significant benefit of both regularization techniques is that they remove the curse of dimensionality suffered by Wasserstein distance. We show that in both cases the optimal generator can be learned to accuracy ∊ with$O$(1/ ∊2) samples from the target distribution without requiring to constrain the discriminator. We thus conclude that these regularization techniques can improve the quality of the generator learned from empirical data in a way that is applicable for a large class of distributions.

We consider the problem of estimating a $d$-dimensional discrete distribution from its samples observed under a $b$-bit communication constraint. In contrast to most previous results that largely focus on the global minimax error, we study the local behavior of the estimation error and provide \emph{pointwise} bounds that depend on the target distribution $p$. In particular, we show that the $\ell_2$ error decays with $O\left(\frac{\lVert p\rVert_{1/2}}{n2^b}\vee \frac{1}{n}\right)$ when $n$ is sufficiently large, hence it is governed by the \emph{half-norm} of $p$ instead of the ambient dimension $d$. For the achievability result, we propose a two-round sequentially interactive estimation scheme that achieves this error rate uniformly over all $p$. Our scheme is based on a novel local refinement idea, where we first use a standard global minimax scheme to localize $p$ and then use the remaining samples to locally refine our estimate.We also develop a new local minimax lower bound with (almost) matching $\ell_2$ error, showing that any interactive scheme must admit a $\Omega\left( \frac{\lVert p \rVert_{{(1+\delta)}/{2}}}{n2^b}\right)$ $\ell_2$ error for any $\delta > 0$ when $n$ is sufficiently large. The lower bound is derived by first finding the best parametric sub-model containing $p$, and then upper bounding the quantized Fisher information under this model. Our upper and lower bounds together indicate that the $\mathsf{H}_{1/2}(p) = \log(\lVert p \rVert_{{1}/{2}})$ bits of communication is both sufficient and necessary to achieve the optimal (centralized) performance, where $\mathsf{H}_{{1}/{2}}(p)$ is the R\'enyi entropy of order $2$. Therefore, under the $\ell_2$ loss, the correct measure of the local communication complexity at $p$ is its R\'enyi entropy.

We introduce a novel anytime batched Thompson sampling policy for multi-armed bandits where the agent observes the rewards of her actions and adjusts her policy only at the end of a small number of batches. We show that this policy simultaneously achieves a problem dependent regret of order $O(\log(T))$ and a minimax regret of order $O(\sqrt{T\log(T)})$ while the number of batches can be bounded by $O(\log(T))$ independent of the problem instance over a time horizon $T$. We also prove that in expectation the instance dependent batch complexity of our policy is of order $O(\log\log(T))$. These results indicate that Thompson sampling performs competitively with recently proposed algorithms for the batched setting, which optimize the batch structure for a given time horizon $T$ and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. Unlike these algorithms, the batched Thompson sampling algorithm we propose is an anytime policy, i.e. it operates without the knowledge of the time horizon $T$, and as such it is the only anytime algorithm that achieves optimal regret with $O(\log\log(T))$ expected batch complexity. This is achieved through a dynamic batching strategy, which uses the agents estimates to adaptively increase the batch duration.

In the era of the new generation of communication systems, data traffic is expected to continuously strain the capacity of future communication networks. Along with the remarkable growth in data traffic, new applications, such as wearable devices, autonomous systems, and the Internet of Things (IoT), continue to emerge and generate even more data traffic with vastly different requirements. This growth in the application domain brings forward an inevitable need for more intelligent processing, operation, and optimization of future communication networks.

The Second Call for Papers of the Series on Machine Learning in Communications and Networks has continued to receive a great number of high-quality papers covering various aspects of intelligent communication systems. In addition to 23 original contributions in response to the first call for papers, we include in this issue 5 articles submitted to the second call for papers. In the following, we provide a brief review of key contributions of papers in this issue according to their topics.

We consider parameter estimation in distributed networks, where each sensor in the network observes an independent sample from an underlying distribution and has$k$bits to communicate its sample to a centralized processor which computes an estimate of a desired parameter. We develop lower bounds for the minimax risk of estimating the underlying parameter for a large class of losses and distributions. Our results show that under mild regularity conditions, the communication constraint reduces the effective sample size by a factor of$d$when$k$is small, where$d$is the dimension of the estimated parameter. Furthermore, this penalty reduces at most exponentially with increasing$k$, which is the case for some models, e.g., estimating high-dimensional distributions. For other models however, we show that the sample size reduction is re-mediated only linearly with increasing$k$, e.g. when some sub-Gaussian structure is available. We apply our results to the distributed setting with product Bernoulli model, multinomial model, Gaussian location models, and logistic regression which recover or strengthen existing results. Our approach significantly deviates from existing approaches for developing information-theoretic lower bounds for communication-efficient estimation. We circumvent the need for strong data processing inequalities used in prior work and develop a geometric approach which builds on a new representation of the communication constraint. This approach allows us to strengthen and generalize existing results with simpler and more transparent proofs.

We study minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss, in a framework combining statistical estimation and wireless communication. We develop “analog” joint estimationcommunication schemes that leverage the additive nature of the Gaussian MAC and characterize their minimax risk in terms of the number of nodes , the dimension of the parameter space and the signal-to-noise ratio of the MAC, for two estimation tasks: Gaussian location and product Bernoulli model. We then compare this risk to existing lower bounds for risk in digital schemes, in which nodes transmit bits noiselessly at the Shannon capacity. We show that, by leveraging the summation inherent in the Gaussian MAC, our analog schemes in both cases outperform these lower bounds, scaling with (d/n) rather than Ω(d/log ). This suggests that in over-the-air statistical estimation, drastic improvements in estimation error can be obtained by using analog schemes that work in tandem with the physical layer, rather than digital schemes using a physical-layer abstraction.

The optimal transport problem studies how to transport one measure to another in the most cost-effective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand's celebrated transportation cost inequality. Following Marton's approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this inequality to network information theory. We show that it can be used to recover a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.

We consider the Courtade-Kumar most informative Boolean function conjecture for balanced functions, as well as a conjecture by Li and Médard that dictatorship functions also maximize the Lαnorm of Tpf for 1 ≤ α ≤ 2 where Tpis the noise operator and f is a balanced Boolean function. By using a result due to Laguerre from the 1880's, we are able to bound how many times an Lα-norm related quantity can cross zero as a function of α, and show that these two conjectures are essentially equivalent.

We consider the non-adaptive probabilistic group testing problem where d random defective items are identified with high probability from a population of N items by applying t binary group tests. There has been recent progress towards developing explicit and efficiently decodable group testing schemes with t = Θ(dlogN) tests, which is known to be order-optimal for this setting when d = O(N1-α) for some constant α > 0. In particular, a recent work develops an explicit scheme while another one develops an efficiently decodable scheme for this setting, both with the order-optimal t = Θ(dlogN) tests. However, to the best of our knowledge, there is no order-optimal scheme that is both explicit and efficiently decodable. In this paper, we close this gap by introducing the first (strongly) explicit and efficiently decodable construction that is order-optimal for the non-adaptive probabilistic group testing problem.

Thompson sampling has been of significant recent interest due to its wide range of applicability to online learning problems and its good empirical and theoretical performance. In this paper, we analyze the performance of Thompson sampling in the canonical Gaussian linear bandit setting. We prove that the Bayesian regret of Thompson sampling in this setting is bounded by O(√T log (T)) improving on an earlier bound of O(√T log (T)) n the literature for the case of the infinite, and compact action set. Our proof relies on a Cauchy-Schwarz type inequality which can be of interest in its own right.

Two major challenges in distributed learning and estimation are 1) preserving the privacy of the local samples; and 2) communicating them efficiently to a central server, while achieving high accuracy for the end-to-end task. While there has been significant interest in addressing each of these challenges separately in the recent literature, treatments that simultaneously address both challenges are still largely missing. In this paper, we develop novel encoding and decoding mechanisms that simultaneously achieve optimal privacy and communication efficiency in various canonical settings. In particular, we consider the problems of mean estimation and frequency estimation under epsilon-local differential privacy and b-bit communication constraints. For mean estimation, we propose a scheme based on Kashin’s representation and random sampling, with order-optimal estimation error under both constraints. For frequency estimation, we present a mechanism that leverages the recursive structure of Walsh-Hadamard matrices and achieves order-optimal estimation error for all privacy levels and communication budgets. As a by-product, we also construct a distribution estimation mechanism that is rate-optimal for all privacy regimes and communication constraints, extending recent work that is limited to b = 1 and epsilon = O(1). Our results demonstrate that intelligent encoding under joint privacy and communication constraints can yield a performance that matches the optimal accuracy achievable under either constraint alone.

In combinatorial group testing, the primary objective is to fully identify the set of at most d defective items from a pool of n items using as few tests as possible. The celebrated result for the combinatorial group testing problem is that the number of tests, denoted by t, can be made logarithmic in n when d = O(poly(log n)). However, state-of-the-art group testing codes require the items to be tested w = Ω (d log n)/[(q log d+log log n)] times and tests to include p = Ω (n/(d logdn)) items. In many emerging applications, items can only participate in a limited number of tests and tests are constrained to include a limited number of items. In this paper, we study the “sparse” regime for the group testing problem where we restrict the number of tests each item can participate in by wmaxor the number of items each test can include by pmaxin both noiseless and noisy settings. These constraints lead to a largely unexplored regime where t is a fractional power of n, rather than logarithmic in n as in the classical setting. Our results characterize the number of tests t needed in this regime as a function of wmax or pmax and show, for example, that t decreases drastically when wmax is increased beyond a bare minimum. In particular, in the noiseless case it can be shown that if wmax≤ d, then we must have t = n, i.e., testing every item individually is optimal. We show that if wmax= d+1, the number of tests decreases suddenly from t = n to t = Θ(d√n). The order-optimal construction is obtained via a modification of the classical Kautz-Singleton construction, which is known to be suboptimal for the classical group testing problem. For the more general case, when wmax= ld + 1 for integer l > 1, the modified Kautz-Singleton construction requires t = Θ(dn1/(l+1)) tests, which we prove to be near order-optimal. We also show that our constructions have a favorable encoding and decoding complexity, i.e. they can be decoded in (poly(d) + O(t))-time and each entry in any codeword can be computed in poly(log n) memory space. We finally discuss an application of our results to the construction of energy-limited random access schemes for Internet of Things networks, which provided the initial motivation for our work.

The classical problem of supervised learning is to infer an accurate estimate of a target variable Y from a measured variable X using a set of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, this paper considers a variation of this classical problem in which the inference is distributed between two nodes, e.g., a mobile device and a cloud, with a rate constraint on the communication between them. The mobile device observes X and sends a description M of X to the cloud, which computes an estimate Y̑ of Y. We follow the recent minimax learning approach to study this inference problem and show that it corresponds to a one-shot minimax noisy lossy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost, leading to a general method for designing a near-optimal descriptor-estimator pair. A key ingredient in the proof of our result is a refined version of the strong functional representation lemma previously used to establish several one-shot source coding theorems. Our results show that a naive estimate-compress scheme for rate-constrained inference is not optimal in general. When the distribution of (X, Y) is known and the error is measured by the logarithmic loss, our bounds on the risk-rate Lagrangian cost provide a new one-shot operational interpretation of the information bottleneck. We also demonstrate a way to bound the excess risk of the descriptor-estimator pair obtained by our method.

We revisit the primitive relay channel, introduced by Cover in 1987. Recent work derived upper bounds on the capacity of this channel that are tighter than the classical cutset bound using the concentration of measure. In this paper, we recover, generalize, and improve upon some of these upper bounds with simpler proofs using reverse hypercontractivity. To our knowledge, this is the first application of reverse hypercontractivity in proving first-order converses in network information theory.

We consider the problem of learning high-dimensional discrete distributions and structured (e.g. Gaussian) distributions in distributed networks, where each node in the network observes an independent sample from the underlying distribution and can use k bits to communicate its sample to a central processor. We consider a blackboard communication model, where nodes can share information interactively through a public blackboard but each node is restricted to write at most k bits on the final transcript. We characterize the impact of the communication constraint k on the minimax risk of estimating the underlying distribution under ℓ2loss, and develop minimax lower bounds that apply in a unified way to many common statistical models. This is achieved by explicitly characterizing the Fisher information from the blackboard transcript.

We propose a grant-free random access scheme for short-packet communication on a collision channel without feedback, where user identities are conveyed through their activity patterns. We show that this problem is inherently related to the non-adaptive group testing problem, where the goal is to identify a small subset of defective items within a larger population, using as few (pre-determined) tests as possible. In the frame-synchronous case, where users' transmissions are aligned, we find that any solution to the non-adaptive group testing problem is also a solution to the random access problem. Similar connections to group testing are identified in the asynchronous variant of the problem, in which case users' transmissions within a frame are received with arbitrary and unknown delays at the receiver. We show that such delays can be accommodated without any additional penalty with respect to the scaling of the transmission length, and that in the regime where the data payload is small, the performance of the proposed random access scheme comes close to that of fully coordinated access schemes.

We revisit the primitive relay channel, introduced by Cover in 1987. Previously, the cut-set bound was shown to be loose for the primitive relay channel, in the discrete memoryless and the Gaussian cases, using the concentration of measure. In this paper, we give simpler proofs using reverse hypercontractivity, with shaper bounds and applying to wider range of channels. To our knowledge, this is the first application of reverse hypercontractivity in first-order converses in network information theory.

Consider a primitive diamond relay channel, where a source X wants to send information to a destination with the help of two relays Y1and Y2, and the two relays can communicate to the destination via error-free digital links of capacities C1and C2respectively, while Y1and Y2are conditionally independent given X. In this paper, we develop new upper bounds on the capacity of such primitive diamond relay channels that are tighter than the cut-set bound. Our results include both the Gaussian and the discrete memoryless case and build on the information inequalities recently developed in [6]-[8] that characterize the tension between information measures in a certain Markov chain.

We consider the probabilistic group testing problem where d random defective items in a large population of N items are identified with high probability by applying binary tests. It is known that the Θ(d log N) tests are necessary and sufficient to recover the defective set with vanishing probability of error when d = O(Nα) for some α ∈ (0, 1). However, to the best of our knowledge, there is no explicit (deterministic) construction achieving Θ(d log N) tests in general. In this paper, we show that a famous construction introduced by Kautz and Singleton for the combinatorial group testing problem (which is known to be suboptimal for combinatorial group testing for moderate values of d) achieves the order optimal Θ(d log N) tests in the probabilistic group testing problem when d = Ω(log2N). This provides a strongly explicit construction achieving the order optimal result in the probabilistic group testing setting for a wide range of values of d. To prove the order-optimality of Kautz and Singleton's construction in the probabilistic setting, we provide a novel analysis of the probability of a non-defective item being covered by a random defective set directly, rather than arguing from combinatorial properties of the underlying code, which has been the main approach in the literature. Furthermore, we use a recursive technique to convert this construction into one that can also be efficiently decoded with only a log-log factor increase in the number of tests.

Consider a memoryless relay channel, where the relay is connected to the destination with an isolated bit pipe of capacity C0. Let C(C0) denote the capacity of this channel as a function of C0. What is the critical value of C0, such that C(C0) first equals C(∞)? This is a long-standing open problem posed by Cover and named “The Capacity of the Relay Channel,” in Open Problems in Communication and Computation, Springer-Verlag, 1987. In this paper, we answer this question in the Gaussian case and show that C(C0) cannot equal to C(∞) unless C0= ∞, regardless of the SNR of the Gaussian channels. This result follows as a corollary to a new upper bound we develop on the capacity of this channel. Instead of “single-letterizing” expressions involving information measures in a high-dimensional space as is typically done in converse results in information theory, our proof directly quantifies the tension between the pertinent n-letter forms. This is done by translating the information tension problem to a problem in high-dimensional geometry. As an intermediate result, we develop an extension of the classical isoperimetric inequality on a high-dimensional sphere, which can be of interest in its own right.

We consider parameter estimation in distributed networks, where each sensor in the network observes an independent sample from an underlying distribution and has $k$ bits to communicate its sample to a centralized processor which computes an estimate of a desired parameter. We develop lower bounds for the minimax risk of estimating the underlying parameter under squared $\ell_2$ loss for a large class of distributions. Our results show that under mild regularity conditions, the communication constraint reduces the effective sample size by a factor of $d$ when $k$ is small, where $d$ is the dimension of the estimated parameter. Furthermore, this penalty reduces at most exponentially with increasing $k$, which is the case for some models, e.g., estimating high-dimensional distributions. For other models however, we show that the sample size reduction is re-mediated only linearly with increasing $k$, e.g. when some sub-Gaussian structure is available. We apply our results to the distributed setting with product Bernoulli model, multinomial model, and dense/sparse Gaussian location models which recover or strengthen existing results. Our approach significantly deviates from existing approaches for developing information-theoretic lower bounds for communication-efficient estimation. We circumvent the need for strong data processing inequalities used in prior work and develop a geometric approach which builds on a new representation of the communication constraint. This approach allows us to strengthen and generalize existing results with simpler and more transparent proofs.

We consider the problem of estimating high-dimensional and nonparametric distributions in distributed networks, where each sensor in the network observes an independent sample from the underlying distribution and can communicate it to a central processor by writing at most k bits on a public blackboard. We obtain matching upper and lower bounds for the minimax risk of estimating the underlying distribution under L1loss. Our results reveal that the minimax risk reduces exponentially in k. Instead of relying on strong data processing inequalities for the converse as commonly done in the literature, we build on a new representation of the communication constraint, which leads to a tight characterization of the problem.

We consider a random access scheme with a massive number of low-energy wireless devices, where a small but arbitrary subset of them can be active at a given time. We develop a solution to this problem via the noisy group testing framework, where the goal is to identify with high probability a small set of defectives in a large set of items with minimum number of noisy binary tests. We translate the power constraint for the wireless devices to a constraint on the number of tests each item can participate in the group testing problem. We present fundamental upper and lower bounds on the length of the codewords in terms of the total number of devices, the number of active devices, the error probability, the noise and the power constraint. We conclude with a scheme that enjoys low decoding complexity under this model.

The classical problem of supervised learning is to infer an accurate predictor of a target variable Y from a measured variable X by using a finite number of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, in this paper we consider a variation of this classical problem in which the prediction is performed remotely based on a rate-constrained description M of X. Upon receiving M, the remote node computes an estimate Y of Y. We follow the recent minimax approach to study this learning problem and show that it corresponds to a one-shot minimax noisy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost and a general method to design a near-optimal descriptor-estimator pair, which can be viewed as a rate-constrained analog to the maximum conditional entropy principle used in the classical minimax learning problem. Our results show that a naive estimate-compress scheme for rate-constrained prediction is not in general optimal.

We consider a communication channel where there is no common clock between the transmitter and the receiver. This is motivated by the recent interest in building system-on-chip radios for Internet of Things applications, which cannot rely on crystal oscillators for accurate timing. We identify two types of clock uncertainty in such systems: timing jitter, which occurs at a time scale faster than the communication duration (or equivalently blocklength), and clock drift, which occurs at a slower time scale. We study the zero-error capacity under both types of timing imperfections and obtain optimal zero-error codes for some cases. Our results show that, as opposed to common practice, in the presence of clock drift, it is highly suboptimal to try to learn and track the clock frequency at the receiver; rather, one can design codes that come close to the performance of perfectly synchronous communication systems without any clock synchronization at the receiver.

This paper investigates the achievable rates of an additive white Gaussian noise energy-harvesting (EH) channel with an infinite battery. The EH process is characterized by a sequence of blocks of harvested energy, which is known causally at the source. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed random variables. The blocks have length L , which can be interpreted as the coherence time of the energy-arrival process. If L is a constant or grows sublinearly in the blocklength n , we fully characterize the first-order term in the asymptotic expansion of the maximum transmission rate subject to a fixed tolerable error probability ε. The first-order term is known as the ε-capacity. In addition, we obtain lower and upper bounds on the second-order term in the asymptotic expansion, which reveal that the second order term is proportional to -(L/n)1/2for any ε less than 1/2. The lower bound is obtained through analyzing the save-and-transmit strategy. If L grows linearly in n, we obtain lower and upper bounds on the ε-capacity, which coincide whenever the cumulative distribution function of the EH random variable is continuous and strictly increasing. In order to achieve the lower bound, we have proposed a novel adaptive save-and-transmit strategy, which chooses different save-and-transmit codes across different blocks according to the energy variation across the blocks.

Motivated by the recent emergence of energy harvesting and wirelessly powered transceivers, we study communication over a memoryless channel with a transmitter, whose battery is recharged at random or deterministic times known to the receiver. We characterize the capacity of this channel as the limit of an n-letter maximum mutual information rate under various assumptions: causal and noncausal transmitter knowledge of the battery recharges, with or without feedback from the receiver to the transmitter. While the resultant n-letter capacity expressions are not computable in the general case, we demonstrate their usefulness by focusing on two important special cases, namely, the binary erasure channel (BEC) and the additive white Gaussian noise (AWGN) channel, where they lead to some interesting, and somewhat surprising, insights. By focusing on the BEC, we show that output feedback can strictly increase the capacity of this channel, even though the channel is memoryless and the battery recharging process is independent over time. Interestingly, this provides a counter example to an old claim by Shannon stated without proof in his 1956 paper. On the other hand, by focusing on the AWGN channel, we are able to show that the capacity with noncausal knowledge of the battery recharging times at the transmitter is strictly larger than that with causal knowledge, even though the battery recharging process is independent over time and known to the receiver. The n-letter expressions can also be used to derive explicit upper and lower bounds on capacity. In particular, we derive simple upper and lower bounds on the capacity of the AWGN channel with random battery recharges, which are within 1.05 b/s/Hz of each other for all parameter values.

The cut-set bound developed by Cover and El Gamal in 1979 has since remained the best known upper bound on the capacity of the Gaussian relay channel. We develop a new upper bound on the capacity of the Gaussian primitive relay channel, which is tighter than the cut-set bound. Our proof uses Gaussian measure concentration to establish geometric relations, satisfied with high probability, between the n-letter random variables associated with a reliable code for communicating over this channel. We then translate these geometric relations into new information inequalities that cannot be obtained with classical methods. Combined with a tensorization argument proposed by Courtade and Ozgur in 2015, our result also implies that the current capacity approximations for Gaussian relay networks, which have linear gap to the cut-set bound in the number of nodes, are order-optimal and lead to a lower bound on the pre-constant.

We study the problem of online power control for energy harvesting communication nodes with random energy arrivals and a finite battery. We assume a block i.i.d. stochastic model for the energy arrivals, in which the energy arrivals are constant for a fixed duration T, but are independent across different blocks, drawn from an arbitrary distribution. This model serves as a simple approximation to a random process with coherence time T. We propose a simple online power control policy, and prove that its performance gap to the optimal throughput is bounded by a constant which is independent of the parameters of the problem. This also yields a simple formula for the approximately optimal long-term average throughput, which sheds some light on the qualitative behavior of the throughput and how it depends on the coherence time of the energy arrival process. Our results show that, perhaps counter-intuitively, for a fixed mean energy arrival rate the approximate throughput decreases with increasing coherence time T of the energy arrival process. In particular, the battery size needed to approach the AWGN capacity of the channel increases linearly with the coherence time of the process. Finally, we show that our results can provide an approximation to the information-theoretic capacity of the same channel.

We consider a communication channel where there is no common clock between the transmitter and the receiver. This is motivated by the recent interest in building system-on-chip radios for Internet of Things applications, which cannot rely on crystal oscillators for accurate timing. We identify two types of clock uncertainty in such systems: timing jitter, which occurs at a time scale faster than the communication duration (or equivalently blocklength); and clock drift, which occurs at a slower time scale. We study the zero-error capacity under both types of timing imperfections, and obtain optimal zero-error codes for some cases. Our results show that, as opposed to common practice, in the presence of clock drift it is highly suboptimal to try to learn and track the clock frequency at the receiver; rather, one can design codes that come close to the performance of perfectly synchronous communication systems without any clock synchronization at the receiver.

This paper investigates the achievable rates of an additive white Gaussian noise (AWGN) energy-harvesting (EH) channel with an infinite battery under the assumption that the error probabilities do not vanish as the blocklength increases. The EH process is characterized by a sequence of blocks of harvested energy. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed (i.i.d.) random variables. The blocks have length L, which can be interpreted as the coherence time of the energy arrival process. If L is a constant or grows sublinearly in the blocklength n, we fully characterize the first-order coding rate. In addition, we obtain lower and upper bounds on the second-order coding rate, which are proportional to −√L/n for any fixed error probability < 1 /2. If L grows linearly in n, we obtain lower and upper bounds on the first-order coding rate, which coincide whenever the EH random variable is continuous. Our results suggest that correlation in the energy-arrival process decreases the effective blocklength by a factor of L.

The capacity of two semi-deterministic channels with the presence of non-causal channel state information (CSI) is characterized. The first channel is a state-dependent semi-deterministic relay channel. The CSI is available only at the transmitter and receiver, but not at the relay. The second channel is a state-dependent multiple access channel (MAC) with partial cribbing and CSI only at one transmitter and the receiver. In the semi-deterministic relay channel without states, the capacity can be achieved using partial-decode-forward scheme. The transmission is split to blocks; in each block, the relay decodes a part of the message and cooperation is established using those bits. When the channel depends on a state, the decoding procedure at the relay reduces the transmission rate. Recently, a cooperative bin forward scheme has been proposed which establishes cooperation without requiring the relay to decode a part of the message. In this scheme, the relay maps its received sequence, which is a deterministic function of the transmitted sequence, into bins. The transmitter coordinates its transmission with the bin index that is chosen by the relay. This scheme achieves the capacity when the CSI is available causally. In this work, we present a variation of the cooperative-bin-forward scheme that achieves capacity for non-causal CSI. The bin index corresponding to the deterministic output of the relay is selected by the transmitter in such a way that the relay's transmission is coordinated with the states. This coding scheme also applies for the MAC with partial cribbing and non-causal CSI at one transmitter and receiver. The capacity is achieved by the new variation of cooperative bin-forward. On top of that, we show an example in which the capacity with non-causal CSI is strictly greater than with causal CSI.

Usually, wireless radios are half-duplex, i.e. they can not transmit and receive at the same time over the same frequency band. However, building on self-interference cancellation techniques, full-duplex radios have emerged as a viable paradigm over the recent years. In this paper, we ask the following question: how much can full-duplex increase the capacity of wireless networks? Intuitively, one may expect that full-duplex radios can at most double the capacity of wireless networks, since they enable nodes to transmit and receive at the same time. In this paper, we show that the capacity gain can indeed be larger than a factor of 2; in particular, we construct a specific instance of a wireless relay network where the capacity with full-duplex radios is triple the capacity of the network when the relays are half-duplex. We also propose a universal schedule for half-duplex networks composed of independent, memoryless, point-to-point channels which achieves at least a fraction of 1/4 of the corresponding full-duplex capacity. This means that for wireless networks composed of point-to-point channels full-duplex capability at the relays cannot more than quadruple the capacity of network.

Consider a memoryless relay channel, where the channel from the relay to the destination is an isolated bit pipe of capacity C0. Let C(C0) denote the capacity of this channel as a function of C0. What is the critical value of C0such that C(C0) first equals C(∞)? This is a long-standing open problem posed by Cover and named “The Capacity of the Relay Channel,” in Open Problems in Communication and Computation, Springer-Verlag, 1987. In our recent work, we answered this question in the case when the channels from the source to the relay and destination are symmetric, which is the original assumption imposed by Cover, and when these channels are Gaussian. We showed that C(C0) can not equal to C(∞) unless C0= ∞, regardless of the SNR of the Gaussian channels, while the cut-set bound would suggest that C(∞) can be achieved at finite C0. In this paper, we show that our techniques for solving Cover's problem can be naturally extended to the general Gaussian case, where the channels from the source to the relay and destination may be asymmetric, and prove an upper bound on the capacity C(C0) of a general Gaussian relay channel for any C0. This upper bound immediately implies that our previous conclusion, i.e. C(C0) can not equal to C(∞) unless C0= ∞, also holds in the asymmetric case. Our approach is geometric and relies on a strengthening of the isoperimetric inequality on the sphere by using the Riesz rearrangement inequality.

We consider a general class of stochastic optimization problems, in which the state represents a certain level or amount which can be partly used and depleted, and subsequently filled by a random amount. This is motivated by energy harvesting applications, in which one manages the amount of energy in a battery, but is also related to inventory models and queuing models. We propose a simple policy that requires minimal knowledge of the distribution of the stochastic process involved, and show that it is a close approximation to the optimal solution with bounded guarantees. Specifically, under natural assumptions on the reward function, we provide constant multiplicative and additive gaps to optimality, which do not depend on the problem parameters. This allows us to obtain a simple formula for approximating the long-term expected average reward, which gives some insight on its qualitative behavior as a function of the maximal state and the distribution of the disturbance.

Motivated by the recent developments in wireless power transfer, we study communication with a remotely powered transmitter. We propose an information-theoretic model where a charger can dynamically decide on how much power to transfer to the transmitter based on its side information regarding the communication, while the transmitter needs to dynamically adapt its coding strategy to its instantaneous energy state, which in turn depends on the actions previously taken by the charger. We characterize the capacity as an n-letter mutual information rate under various levels of side information available at the charger. When the charger is finely tunable to different energy levels, referred to as a “precision charger,” we show that these expressions reduce to single-letter form and there is a simple and intuitive joint charging and coding scheme achieving capacity. The precision charger scenario is motivated by the observation that in practice the transferred energy can be controlled by simply changing the amplitude of the beamformed signal. When the charger does not have sufficient precision, for example, when it is restricted to use a few discrete energy levels, we show that the computation of the n-letter capacity can be cast as a Markov decision process if the channel is noiseless. This allows us to numerically compute the capacity for specific cases and obtain insights on the corresponding optimal policy, or even to obtain closed-form analytical solutions by solving the corresponding Bellman equations, as we demonstrate through examples. Our findings provide some surprising insights on how side information at the charger can be used to increase the overall capacity of the system.

We consider the discrete memoryless symmetric primitive relay channel, where, a source$X$wants to send information to a destination$Y$with the help of a relay$Z$and the relay can communicate to the destination via an error-free digital link of rate$R_{0}$, while$Y$and$Z$are conditionally independent and identically distributed given$X$. We develop two new upper bounds on the capacity of this channel that are tighter than existing bounds, including the celebrated cut-set bound. Our approach significantly deviates from the standard information-theoretic approach for proving upper bounds on the capacity of multi-user channels. We build on the blowing-up lemma to analyze the probabilistic geometric relations between the typical sets of the$n$-letter random variables associated with a reliable code for communicating over this channel. These relations translate to new entropy inequalities between the$n$-letter random variables involved. As an application of our bounds, we study an open question posed by (Cover, 1987), namely, what is the minimum rate$R_{0}^{*}$needed for the$Z$–$Y$link in order for the capacity of the relay channel to be equal to that of the broadcast cut. We consider the special case when the$X$–$Y$and$X$–$Z$links are both binary symmetric channels. Our tighter bounds on the capacity of the relay channel immediately translate to tighter lower bounds for$R_{0}^{*}$. More interestingly, we show that when$p\to 1/2$,$R_{0}^{*}\geq 0.1803$; even though the broadcast channel becomes completely noisy as$p\to 1/2$and its capacity, and therefore the capacity of the relay channel, goes to zero, a strictly positive rate$R_{0}$is required for the relay channel capacity to be equal to the broadcast bound. Existing upper bounds on the capacity of the relay channel, and the cut-set bound in particular, would rather imply$R_{0}^{*}\to 0$, while achievability schemes require$R_{0}^{*}\to 1$. We conjecture that$R_{0}^{*}\to 1$as$p\to 1/2$.

We consider online power control for an energy harvesting system with random i.i.d. energy arrivals and a finite size battery. We propose a simple online power control policy for this channel that requires minimal information regarding the distribution of the energy arrivals and prove that it is universally near-optimal for all parameter values. In particular, the policy depends on the distribution of the energy arrival process only through its mean and achieves the optimal long-term average throughput of the channel within a constant gap. Existing heuristics for online power control fail to achieve such universal performance. This result also allows us to obtain a simple constant-gap approximation for the long-term average throughput of the system, which sheds some light on the qualitative behavior of the throughput, namely how it depends on the distribution of the energy arrivals and the size of the battery.

We consider an energy harvesting multiple access channel where the transmitters are powered by an exogenous stochastic energy harvesting process and equipped with finite batteries. We characterize the capacity region of this channel as n-letter mutual information rate and develop inner and outer bounds that differ by a constant gap. An interesting conclusion that emerges from our results is that in a symmetric system, where transmitters are statistically equivalent to each other, the largest achievable common rate point approaches that of a standard AWGN MAC with an average power constraint, as the number of users in the MAC becomes large.

Motivated by recent developments in wireless power transfer, we study communication with a remotely powered transmitter. We propose an information-theoretic model where a charger can dynamically decide on how much power to transfer to the transmitter based on its side information regarding the communication, while the transmitter needs to dynamically adopt its coding strategy to its instantaneous energy state, which in turn depends on the actions previously taken by the charger. We characterize the capacity as n-letter mutual information rate under various levels of side information available at the charger. In some special cases, motivated by different settings of practical interest, we simplify these expressions to single-letter form, or provide an algorithm to efficiently compute capacity using dynamic programming. Our results provide some surprising insights on how side information at the charger can be used to increase the overall capacity of the system.

Consider a primitive relay channel, where, a source X wants to send information to a destination Y with the help of a relay Z and the relay can communicate to the destination via an error-free digital link of rate R0. For the symmetric case, i.e., when Y and Z are conditionally i.i.d. given X, we have recently developed new upper bounds on the capacity of this channel that are tighter than existing bounds, including the celebrated cut-set bound. In this paper, we extend these bounds to the asymmetric case, where Y and Z are conditionally independent given X with arbitrary conditional marginal distributions, for both discrete memoryless and Gaussian channels.

We consider online power control for a K-user energy harvesting multiple-access channel (MAC). We show that a simple online power control policy that requires each user to know only the mean of its own energy harvesting process and does not require any information regarding the energy harvesting processes of the other users is near optimal for any joint distribution of the energy harvesting processes and for arbitrary battery sizes at the K users. In particular, for any parameter values this strategy achieves a throughput region which is within a constant gap to the capacity region of the classical additive white Gaussian noise (AWGN) MAC. When the number of users in the MAC becomes large, the gap becomes negligible. Therefore, an interesting consequence of our result is that in the limit when the number of users becomes large, the sum throughput of the online energy harvesting MAC approaches the sum capacity of the classical AWGN MAC. While it has been known that the online throughput of an energy harvesting system can approach the AWGN capacity in the limit when the battery size goes to infinity, it is interesting that the AWGN capacity can be also approached in limit of large number of users.

The data center network (DCN), wired or wireless, features large amounts of many-to-one (M2O) sessions. Each M2O session is currently established using point-to-point (P2P) communications and store-and-forward (SAF) relays, and is generally followed by a certain computation at the destination, typically a weighted summation of the received information digits. Fundamentally different from this separate P2P/SAF-based-transmission and computation framework, this paper proposes simultaneous transmission and air computation (STAC), a novel physical layer scheme that achieves STAC in wireless DCNs. In particular, STAC builds on a number of distinguishing characteristics of DCs to take advantage of the superposition nature of electromagnetic signals. With STAC, multiple sources transmit in the same time slot with appropriately chosen parameters, such that the superimposed signal can be directly transformed to the desired summation at the receiver. To enable STAC, we propose an enhanced software-defined network architecture, where a wired low-bandwidth backbone provides wireless transceivers with external reference signals. We also discuss some new challenges that STAC brings to scheduling and routing. Theoretical analysis and simulation results show that STAC can significantly improve both bandwidth and energy efficiency in DCNs.

We consider an n-relay Gaussian diamond network where a source communicates to a destination with the help of n half-duplex relays. Achieving rates close to the capacity of this network requires to employ all the n relays under an optimal transmit/receive schedule. Even for the moderate values of n, this can have significant operational complexity as the optimal schedule may possibly have 2ndifferent states for the network (since each of the relays can be in either transmitting or receiving mode). In this paper, we investigate whether a significant fraction of the network capacity can be achieved by using transmit/receive schedules that have only few active states and by using only few relays. First, we conjecture that the approximately optimal schedule has at most n+1 states instead of the 2npossible states. We prove this conjecture for networks of size n ≤ 6 by developing a proof strategy and implementing it computationally. Second, we show that routing strategies that only employ the point-to-point communication and two of the relays with a half-duplex schedule that has only two active states can achieve at least half the capacity (approximately) of the network. Techniques from linear programming and submodular functions are used to derive the results.

We consider communication over heterogeneous parallel channels, where a transmitter is connected to two users via two parallel channels: a multiple-input multiple-output (MIMO) broadcast channel (BC) and a noiseless rate-limited multicast channel. We characterize the optimal degrees of freedom (DoF) region of this setting when the transmitter has delayed channel state information (CSIT) regarding the MIMO BC. Our results show that jointly coding over the two channels strictly outperforms simple channel aggregation and can even achieve the instantaneous CSIT performance with completely outdated CSIT on the MIMO BC in the sum DoF sense; this happens when the multicast rate of the second channel is larger than a certain threshold. The main idea is to send information over the MIMO BC at a rate above its capacity and then use the second channel to send additional side information to allow for reliable decoding at both receivers. We call this scheme a two-phase overload-multicast strategy. We show that such a strategy is also sum DoF optimal for the K-user MIMO BC with a parallel multicast channel when the rate of the multicast channel is high enough and can again achieve the instantaneous CSIT performance (optimal sum DoF) with completely outdated CSIT. For the regime where the capacity of the multicast channel is small, we propose another joint coding strategy, which is sum DoF optimal.

The capacity regions of semideterministic multiuser channels, such as the semideterministic relay channel and the multiple access channel with partially cribbing encoders, have been characterized using the idea of partial-decode-forward. However, the requirement to explicitly decode part of the message at intermediate nodes can be restrictive in some settings; for example, when nodes have different side information regarding the state of the channel. In this paper, we generalize this scheme to cooperative-bin-forward by building on the observation that explicit recovering of part of the message is not needed to induce cooperation. Instead, encoders can bin their received signals and cooperatively forward the bin index to the decoder. The main advantage of this new scheme is illustrated by considering state-dependent extensions of the aforementioned semideterministic setups. While partial-decode-forward is suboptimal in these new setups, cooperative-bin-forward continues to achieve capacity.

The best known inner bound for the two-user discrete memoryless interference channel is the Han-Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with ON/OFF interference, which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (also known as unidirectional partial cribbing).

We consider vector space interference alignment strategies over the$K$-user interference channel and derive an upper bound on the achievable degrees of freedom as a function of the channel diversity$L$, where the channel diversity is modeled by$L$real-valued parallel channels with coefficients drawn from a nondegenerate joint distribution. The seminal work of Cadambe and Jafar shows that when$L$is unbounded, vector space interference alignment can achieve 1/2 degrees of freedom per user independent of the number of users$K$. However, wireless channels have limited diversity, in practice, dictated by their coherence time and bandwidth, and an important question is the number of degrees of freedom achievable at finite$L$. When$K=3$and if$L$is finite, Bresleret al.show that the number of degrees of freedom achievable with vector space interference alignment is bounded away from 1/2, and the gap decreases inversely proportional to$L$. In this paper, we show that when$K\geq 4$, the gap is significantly larger. In particular, the gap to the optimal 1/2 degrees of freedom per user can decrease at most like$1/\sqrt {L}$, and when$L$is smaller than the order of$2^{(K-2)(K-3)}$, it decays at most like$1/\sqrt [{4}]{L}$.

We investigate the degrees of freedom (DoF) for the two-user multiple-input multiple-output interference channel (MIMO IC) with parallel multicasting channels. Specifically, in addition to the MIMO IC, each transmitter is also connected to both receivers via an out-of-band multicast channel. Our main contribution lies in the characterization of the optimal sum DoF when the channel state information (CSI) on the MIMO IC is available to the transmitters with some delay (delayed CSIT). We show that jointly coding over the parallel multicast channels can achieve higher DoF than channel aggregation does. Furthermore, as long as the rate of the multicast channels is above a certain threshold, delayed CSIT is enough to achieve the same DoF performance as with instantaneous CSIT.

Beginning with work by Avestimehr, Diggavi and Tse, there have been a series of papers showing that the capacity of Gaussian relay networks can be closely approximated by the cutset bound. More precisely, it is known that the gap between the cutset bound and capacity in these networks can be bounded by a function that grows linearly with the number of nodes in the network and is otherwise independent of network topology and channel configurations. We argue that this linear gap is fundamental to such approximations, and prove that improvement to a sublinear function is possible if, and only if, capacity is equal to the cutset bound for all Gaussian relay networks.

Motivated by the cellular uplink scenario along with the increasing capabilities of radio nodes, we consider a state-dependent multiple-access channel in which the encoders can overhear other transmissions while simultaneously sending their own transmissions. In addition, the channel is state dependent and encoders have access to independent causal state information while the decoder has complete state information. We characterize the capacity region of this setup. The encoders in our achievability scheme make full use of the partial cribbing resources by jointly mapping the cribbed sequences and cooperatively forwarding the information to the decoder, without attempting to explicitly recover any part of the other encoder's message or state information.

We consider an energy harvesting channel, in which the transmitter is powered by an exogenous stochastic energy arrival process, which can be stored in a battery of finite size. We provide an n-letter expression for the capacity of this channel under various assumptions on the availability of energy arrival information: causal and noncausal knowledge of the energy arrivals at the transmitter with and without knowledge at the receiver. We then proceed to deriving lower and upper bounds on the capacity that are easier to compute and are within a constant gap of each other. In particular, we show that the power control problem for energy-harvesting communication, extensively studied in the communication theory literature over the recent years, provides an upper bound on the true information-theoretic capacity of the channel. For example, the offline power control problem provides an upper bound on the information-theoretic capacity with noncausal knowledge of the energy arrivals at the transmitter and the receiver, while the online problem is an upper bound on the capacity with causal information. Perhaps more surprisingly, we also show that given an optimal power control policy there is a natural way to construct an explicit scheme which achieves a rate within a constant gap of the upper bound for any i.i.d. energy harvesting process and any battery size. This shows that these two different formulations of the energy-harvesting communication problem, so far studied in isolation, are strongly coupled; solving the power control problem is almost sufficient to solve the information-theoretic problem.

We consider communication over the AWGN channel with a transmitter whose battery is recharged with RF energy transfer at random times known to the receiver. We assume that the recharging process is i.i.d. Bernoulli. We characterize the capacity of this channel as the limit of an n-letter maximum mutual information rate under both causal and noncausal transmitter knowledge of the battery recharges. With noncausal knowledge, it is possible to explicitly identify the maximizing input distribution, which we use to demonstrate that the capacity with noncausal knowledge of the battery recharges is strictly larger than that with causal knowledge. We then proceed to derive explicit upper and lower bounds on the capacity, which are within 1.05 bits/s/Hz of each other for all parameter values.

Consider a symmetric primitive relay channel, where, the source X wants to send information to the destination Y with the help of a relay Z, the relay Z can communicate to the destination Y via an error-free digital link of rate R0, and Y, Z are conditionally independent and identically distributed given X. This paper presents two new upper bounds on the capacity of such relay channels, where the first one is a sharpened version of the recently proposed bound by (Xue, 2014), and the second one is novel. These two bounds are shown to be generally tighter than the cut-set bound, and as an example they are numerically evaluated for the case of binary symmetric channels.

We investigate if feedback can increase the capacity of an energy harvesting communication channel where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery communicates to a receiver over a memoryless channel. For a simple special case where the energy arrival process is deterministic and the channel is a BEC, we explicitly compute the feed-forward and feedback capacities and show that feedback can strictly increase the capacity of this channel. Building on this example, we also show that feedback can increase the capacity when the energy arrivals are i.i.d. known noncausally at the transmitter and the receiver.

We consider an energy harvesting system where the fixed size battery of the transmitter is recharged with certain probability at each channel use. For this setup, we explicitly characterize the optimal online energy management strategy for maximizing the long-term throughput under different assumptions on the availability of channel state information. We show that in the case of no fading, the amount of energy allocated to each channel use decreases exponentially with time since the last battery recharge and in the case of fading, the optimal solution has a discounted water-filling structure. Our results reveal that the structure of the optimal energy management strategy in the online case with finite battery is significantly different from the infinite battery and offline cases characterized in the literature.

We consider an energy-harvesting communication system where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery of size Bmaxcommunicates over a discrete-time AWGN channel. We first concentrate on a simple Bernoulli energy arrival process where at each time step, either an energy packet of size E is harvested with probability p, or no energy is harvested at all, independent of the other time steps. We provide a near optimal energy control policy and a simple approximation to the information-theoretic capacity of this channel. Our approximations for both problems are universal in all the system parameters involved (p, E and Bmax), i.e., we bound the approximation gaps by a constant independent of the parameter values. Our results suggest that a battery size Bmax≥ E is (approximately) sufficient to extract the infinite battery capacity of this channel. We then extend our results to general i.i.d. energy arrival processes. Our approximate capacity characterizations provide important insights for the optimal design of energy harvesting communication systems in the regime where both the battery size and the average energy arrival rate are large.

The study of feedback has been mostly limited to single-hop communication settings. In this paper, we consider Gaussian networks where sources and destinations can communicate with the help of intermediate relays over multiple hops. We assume that links in the network can be bidirected providing opportunities for feedback. We ask the following question: can the information transfer in both directions of a link be critical to maximizing the end-to-end communication rates in the network? Equivalently, could one of the directions in each bidirected link (and more generally at least one of the links forming a cycle) be shut down and the capacity of the network still be approximately maintained? We show that in any arbitrary Gaussian network with bidirected edges and cycles and unicast traffic, we can always identify a directed acyclic subnetwork that approximately maintains the capacity of the original network. For Gaussian networks with multiple-access and broadcast traffic, an acyclic subnetwork is sufficient to achieve every rate point in the capacity region of the original network, however, there may not be a single acyclic subnetwork that maintains the whole capacity region. For networks with multicast and multiple unicast traffic, on the other hand, bidirected information flow across certain links can be critically needed to maximize the end-to-end capacity region. These results can be regarded as generalizations of the conclusions regarding the usefulness of feedback in various single-hop Gaussian settings and can provide opportunities for simplifying operation in Gaussian multihop networks.

In this paper, we study a simple question: when are dynamic relaying strategies essential in optimizing the diversity-multiplexing tradeoff (DMT) in half-duplex wireless relay networks? This is motivated by apparently two contrasting results even for a simple three-node network with a single half-duplex relay. When all channels in the system are assumed to be independent and identically fading, a static schedule where the relay listens half the time and transmits half the time combined with quantize-map-and-forward (QMF) relaying is known to achieve the full-duplex performance. However, when there is no direct link between the source and the destination, a dynamic decode-and-forward (DDF) strategy is needed to achieve the optimal tradeoff. In this case, a static schedule is strictly suboptimal and the optimal tradeoff is significantly worse than the full-duplex performance. In this paper, we study the general case when the direct link is neither as strong as the other links nor fully nonexistent, and identify regimes where dynamic schedules are necessary and those where static schedules are enough. We identify four qualitatively different regimes for the single-relay channel, where the tradeoff between diversity and multiplexing is significantly different. We show that in all these regimes one of the above two strategies is sufficient to achieve the optimal tradeoff by developing a new upper bound on the best achievable tradeoff under channel state information available only at the receivers. A natural next question is whether these two strategies are sufficient to achieve the DMT of more general half-duplex wireless networks with a larger number of relays. We propose a generalization of the two existing schemes through a dynamic QMF (DQMF) strategy, where the relay listens for a fraction of time depending on received channel state information but not long enough to be able to decode. We show that such a DQMF strategy is needed to achieve the optimal DMT in a parallel channel with two relays, outperforming both DDF and static QMF strategies.

Consider a Gaussian relay network where a source node communicates to a destination node with the help of several layers of relays. Recent work has shown that compress-and-forward-based strategies can achieve the capacity of this network within an additive gap. Here, the relays quantize their received signals at the noise level and map them to random Gaussian codebooks. The resultant gap to capacity is independent of the SNRs of the channels in the network and the topology, but is linear in the total number of nodes. In this paper, we provide an improved lower bound on the rate achieved by the compress-and-forward-based strategies (noisy network coding in particular) in arbitrary Gaussian relay networks, whose gap to capacity depends on the network not only through the total number of nodes but also through the degrees of freedom of the min cut of the network. We illustrate that for many networks, this refined lower bound can lead to a better approximation of the capacity. In particular, we demonstrate that it leads to a logarithmic rather than linear capacity gap in the total number of nodes for certain classes of layered networks. The improvement comes from quantizing the received signals of the relays at a resolution decreasing with the total number of nodes in the network. This suggests that the rule-of-thumb in the literature of quantizing the received signals at the noise level can be highly suboptimal.

We consider communication over heterogeneous parallel channels, where a transmitter is connected to two users via two parallel channels: (1) a MISO broadcast channel (BC), and (2) a noiseless rate-limited multicast channel. We characterize the optimal degrees of freedom (DoF) region of this setting when the transmitter has delayed channel state information (CSIT) regarding the MISO BC. Our results show that jointly coding over the two channels can strictly outperform simple channel aggregation (or channel separation) and can even achieve the same performance as with instantaneous CSIT when the CSIT on the MISO BC is completely stale; this occurs when the multicast rate of the second channel is larger than a certain threshold, in the DoF sense. The main idea to achieve full DoF with completely stale CSIT is to send information over the MISO BC at a rate above its capacity and use the second channel to send additional side information to allow for reliable decoding at both receivers.

We consider an energy-harvesting communication system where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery communicates over a discrete-time AWGN channel. Assuming that the energy arrival process is i.i.d. Bernoulli, we provide a simple approximation to the capacity of this channel and bound the approximation gap by a constant independent of all system parameters. Our result reveals two qualitatively different regimes for the channel: in the large battery regime, the capacity depends critically on the average energy arrival rate and not so much on the exact value of the battery size; while in the small-battery regime, the capacity depends on the peakiness of the energy arrival process and is logarithmically increasing in the battery size.

We consider the problem of communicating over the state-dependent Z-interference channel (S-D Z-IC), when the state is known noncausally only to the interfering transmitter. We present an achievability scheme and show that it is optimal for the injective deterministic S-D Z-IC. This scheme is simple in the sense that it does not involve rate-splitting. The idea of the scheme is that the interfering transmitter chooses its signal to be jointly typical with an auxilary coordination codebook that allows the unintended receiver to partly decode the resultant interference. We then investigate the special case of the modulo-additive S-D Z-IC in detail and show that in this case standard Gelfand-Pinsker coding for the interfering link and treating interference as noise at the second link is optimal. We also extend our main result to the deterministic state-dependent Z-channel (S-D Z-C) in which an additional message is transmitted on the cross-link.

In this paper, we consider vector space interference alignment strategies over the K-user interference channel and derive an upper bound on the achievable degrees of freedom as a function of the channel diversity L. The channel diversity L is modeled by L independently fading real-valued parallel channels. Existing results in the literature for K = 3 show that the optimal 1/2 degrees of freedom per user can be approached at the speed of 1/L (i.e. the gap to 1/2 degrees of freedom per user decreases inversely proportional to L). In this paper, we show that when K ≥ 4, the speed of convergence is significantly slower. In particular, the gap to 1/2 degrees of freedom per user can decrease at most like 1/√L. Furthermore, when K is of the order of √logL, the speed of convergence is smaller than 1√(L)4.

We consider the$N$-relay Gaussian diamond network where a source node communicates to a destination node via$N$parallel relays through a cascade of a Gaussian broadcast (BC) and a multiple access (MAC) channel. Introduced in 2000 by Schein and Gallager, the capacity of this relay network is unknown in general. The best currently available capacity approximation, independent of the coefficients and the SNRs of the constituent channels, is within an additive gap of$1.3 N$bits, which follows from the recent capacity approximations for general Gaussian relay networks with arbitrary topology. In this paper, we approximate the capacity of this network within 2 log$N$bits. We show that two strategies can be used to achieve the information-theoretic cut-set upper bound on the capacity of the network up to an additive gap of$O(\log N)$bits, independent of the channel configurations and the SNRs. The first of these strategies is simple partial decode-and-forward. Here, the source node uses a superposition codebook to broadcast independent messages to the relays at appropriately chosen rates; each relay decodes its intended message and then forwards it to the destination over the MAC channel. A similar performance can be also achieved with compress-and-forward type strategies (such as quantize-map-and-forward and noisy network coding) that provide the$1.3 N$-bit approximation for general Gaussian networks, but only if the relays quantize their observed signals at a resolution inversely proportional to the number of relay nodes$N$. This suggests that the rule-of-thumb to quantize the received signals at the noise level in the current literature can be highly suboptimal.

We consider the Gaussian N-relay diamond network, where a source wants to communicate to destination node through a layer of N-relay nodes. We investigate the following question: what fraction of the capacity can we maintain using only k out of the N available relays? We show that independent of the channel configurations and operating SNR, we can always find a subset of k relays, which alone provide a rate k/(k + 1) C̅ - G, where C̅ is the information theoretic cutset upper bound on the capacity of the whole network and G is independent of the channel coefficients and the SNR and depends only on N and k (logarithmic in N and linear in k). In particular, for k = 1, this means that half of the capacity of any N-relay diamond network can be approximately achieved by routing information over a single relay. We also show that this fraction is tight: there are configurations of the N-relay diamond network, where every subset of k relays alone can at most provide approximately a fraction k/(k + 1) of the total capacity. These high-capacity k-relay subnetworks can be also discovered efficiently. We propose an algorithm that computes a constant gap approximation to the capacity of the Gaussian N-relay diamond network in O(N log N) running time and discovers a high-capacity k-relay subnetwork in O(kN) running time. This result also provides a new approximation to the capacity of the Gaussian N-relay diamond network, which is hybrid in nature: it has both multiplicative and additive gaps. In the intermediate SNR regime, this hybrid approximation is tighter than existing purely additive or purely multiplicative approximations to the capacity of this network.

Diversity-multiplexing trade-off has been studied extensively to quantify the benefits of different relaying strategies in terms of error and rate performance. However, even in the case of a single half-duplex relay, which seems fully characterized, implications are not clear. When all channels in the system are assumed to be independent and identically fading, a fixed schedule where the relay listens half of the total duration for communication and transmits the second half combined with quantize-map-and-forward relaying (static QMF) is known to achieve the full-duplex performance [1]. However, when there is no direct link between the source and the destination, a dynamic decode-and-forward (DDF) strategy is needed [2]. It is not clear which one of these two conclusions would carry to a less idealized setup, where the direct link can be neither as strong as the other links nor fully non-existent. In this paper, we provide a generalized diversity-multiplexing trade-off for the half-duplex relay channel which accounts for different channel strengths and recovers the two earlier results as two special cases. We show that these two strategies are sufficient to achieve the diversity-multiplexing trade-off across all channel configurations, by characterizing the best achievable trade-off when channel state information (CSI) is only available at the receivers (CSIR). However, for general relay networks we show that a generalization of these two schemes through a dynamic QMF strategy is needed to achieve optimal performance.

We consider a wireless network with n users distributed over a square area A = n. Under line-of-sight propagation, this network has Θ(√n) degrees of freedom. At high SNR, these degrees of freedom can be readily achieved by multi-hop relaying between nodes. At low SNR however, the performance is determined by the power transfer in the network. We show that none of the existing architectures can achieve optimal capacity scaling. We develop a beamforming architecture where signals are relayed by coherent combining over multiple clusters. The key ingredient is an analysis of the beamforming gain achievable between two clusters of nodes under the line-of-sight propagation model. This result reveals a new regime for large two-dimensional wireless networks, where beamforming techniques are needed to achieve capacity.

We consider wireless relay networks where a source node communicates to a destination node with the help of multiple intermediate relay nodes. In wireless, if a node can send information to another node, typically it can also receive information from that node. Therefore, inherently there are many possibilities for feeding back information in wireless networks. However, transmissions are not isolated but usually subject to broadcast and interference. In this paper, we ask the following question: Can the information transfer in both directions of a link be critical to maximizing the end-to-end communication rate in such networks? Equivalently, could one of the directions in each bidirected link (and more generally at least one of the links forming a cycle) be shut down and the capacity of the network still be approximately maintained? Our main result is to show that in any arbitrary Gaussian relay network with bidirected edges and cycles, we can always identify a directed acyclic subnetwork that approximately maintains the capacity of the original network. The edges of this subnetwork can be identified as the information carrying links, and the remaining links as feedback, which can only provide limited contribution to capacity.

Consider a Gaussian relay network where a number of sources communicate to a destination with the help of several layers of relays. Recent work has shown that a compress-and-forward based strategy at the relays can achieve the capacity of this network within an additive gap. In this strategy, the relays quantize their observations at the noise level and map it to a random Gaussian codebook. The resultant capacity gap is independent of the SNR's of the channels in the network but linear in the total number of nodes. In this paper, we show that if the relays quantize their signals at a resolution decreasing with the number of nodes in the network, the additive gap to capacity can be made logarithmic in the number of nodes for a class of layered, time-varying wireless relay networks. This suggests that the rule-of-thumb to quantize the received signals at the noise level used for compress-and-forward in the current literature can be highly suboptimal.

We consider a large distributed MIMO system where wireless users with single transmit and receive antenna cooperate in clusters to form distributed transmit and receive antenna arrays. We characterize how the capacity of the distributed MIMO transmission scales with the number of cooperating users, the area of the clusters and the separation between them, in a line-of-sight propagation environment. We use this result to answer the following question: can distributed MIMO provide significant capacity gain over traditional multi-hop in large ad hoc networks with n source-destination pairs randomly distributed over an area A? Two diametrically opposite answers [24] and [26] have emerged in the current literature. We show that neither of these two results are universal and their validity depends on V the relation between the number of users n and √A/λ, which we identify as the spatial degrees of freedom in the network. λ is the carrier wavelength. When √A/λ ≥ n, there are n degrees of freedom in the network and distributed MIMO with hierarchical cooperation can achieve a capacity scaling linearly in n as in [24], while capacity of multihop scales only as √n. On the other hand, when √A/λ ≤ √n as in [26], there are only √n degrees of freedom in the network and they can be readily achieved by multihop. Our results also reveal a third regime where √n ≤ √A/λ ≤ n. Here, the number of degrees of freedom are smaller than n but larger than what can be achieved by multi-hop. We construct scaling optimal architectures for this intermediate regime.

Recently, a new relaying strategy, quantize-map-and-forward (QMF) scheme, has been demonstrated to approximately achieve (within an additive constant number of bits) the Gaussian relay network capacity, universally, i.e., for arbitrary topologies, channel gains, and SNRs. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we develop structured lattice codes that implement the QMF strategy. The main result of this paper is that such structured lattice codes can approximately achieve the Gaussian relay network capacity universally, again within an additive constant. In addition, we establish a similar result for half-duplex networks, where we demonstrate that one can approximately achieve the capacity using fixed transmit-receive (TX-RX) schedules for the relays with no transmit power optimization across the different TX-RX states of the network.

Abstract—We consider the diamond network where a source communicates with the destination through N non-interfering half-duplex relays. Using simple outer bounds on the capacity of the network, we show that simple relaying strategies having exactly two states and avoiding broadcast and multiple access communication can still achieve a significant constant fraction of the capacity of the 2 relay network, independent of the SNR values. The results are extended to the case of 3 relays for the special class of antisymmetric networks. We also study the structure of (approximately) optimal relaying strategies for such networks. Simulations show that optimal schedules have at most N +1 states, which we conjecture to be true in general. We prove the conjecture for N =2and in special cases for N =3. I.

We consider a wireless network with a large number of source-destination pairs distributed over a line. Under line-of-sight propagation, this network has only one degree of freedom for communication. At high SNR, this one degree of freedom can be readily achieved by multi-hop relaying between nodes. At low SNR, however, the performance is determined by the power transfer in the network. We show that none of the existing architectures can achieve optimal capacity scaling. We develop a digital hierarchical beamforming architecture and show that it is scaling optimal. This result reveals a new regime for large wireless networks, where beamforming techniques are needed to achieve capacity.

The value of relay nodes to enhance the error performance versus rate trade-off in wireless networks has been studied extensively. However, wireless nodes currently are constrained to only transmit or receive at a given frequency, i.e., half-duplex constraint. The diversity-multiplexing tradeoff (DMT) for half-duplex networks are less understood. In the special cases where the DMT is currently known, such as the relay channel and the line network, it is achieved by either dynamic decoding or a quantize-map-forward (QMF) strategy with a fixed half-duplex schedule. The main question we investigate in this paper is whether these two strategies are sufficient to achieve the DMT of half-duplex wireless networks or we need new strategies for general setups. We propose a generalization of the two existing schemes through a dynamic QMF strategy and show that in a parallel relay channel it outperforms both earlier schemes. We also establish the DMT for the relay channel with multiple relays and multiple antennas in some special cases.

We consider the N-relay Gaussian diamond network where a source node communicates to a destination node via N parallel relays. We show that several strategies can achieve the capacity of this network within O(log N) bits independent of the channel configurations and the operating SNR. The first of these strategies is partial decode-and-forward: the source node broadcasts independent messages to the relays at appropriately chosen rates, which in turn decode and forward these messages to the destination over a MAC channel. The same performance can be also achieved by compress-and-forward, quantize-map-and-forward or noisy network coding if relays quantize their observations at a decreasing resolution with N, instead of quantizing at the noise-level. The best capacity approximations currently available for this network are within O(N) bits which follow from the corresponding capacity approximations for general Gaussian relay networks.

We consider the N-relay Gaussian diamond network when the source and the destination have ns≥ 2 and nd≥ 2 antennas respectively. We show that when ns= nd= 2 and when the individual MISO channels from the source to each relay and the SIMO channels from each relay to the destination have the same capacity, there exists a two relay sub-network that achieves approximately all the capacity of the network. To prove this result, we establish a simple relation between the joint entropies of three Gaussian random variables, which is not implied by standard Shannon-type entropy inequalities.

We consider the Gaussian N-relay diamond network, where a source wants to communicate to a destination node through a layer of N-relay nodes. We investigate the following question: What fraction of the capacity can we maintain by using only k out of the N available relays? We show that in every Gaussian N-relay diamond network, there exists a subset of k relays which alone provide approximately k/k+1 of the total capacity. The result holds independent of the number of available relay nodes N, the channel configurations and the operating SNR. The result is tight in the sense that there exists channel configurations for N-relay diamond networks, where every subset of k relays can provide at most k/k+1 of the total capacity. The approximation is within 3 logN + 3k bits/s/Hz to the capacity. This result also provides a new approximation to the capacity of the Gaussian N-relay diamond network which is up to a multiplicative gap of 1/k+1 and additive gap of 3 logN + 3k. The current approximation results in the literature either aim to characterize the capacity within an additive gap by allowing no multiplicative gap or vice a versa. Our result suggests a new approximation approach where multiplicative and additive gaps are allowed simultaneously and are traded through an auxiliary parameter.

We present a structured Quantize-Map-and-Forward (QMF) scheme for cooperative communication over wireless networks, that employs LDPC ensembles for the node operations and message-passing algorithms for decoding. We demonstrate through extensive simulation results over the full-duplex parallel relay network, that our scheme, with no transmit channel state information, offers a robust performance over fading channels and achieves the full diversity order of our network at moderate SNRs.

Multi-hop is the traditional architecture for wireless adhoc networks. In this paper, we investigate the potential gains from more sophisticated cooperation in large wireless adhoc networks. While the capacity of multi-hop is limited to ⊖(√(n)) due to interference, we show that a hierarchical cooperation architecture can achieve linear capacity scaling in the number of users n. We also characterize how the cooperation gain is affected when the network is limited in either power or space.

Recently, it has been shown that a quantize-map-and-forward scheme approximately achieves (within a constant number of bits) the Gaussian relay network capacity for arbitrary topologies. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the same approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays.

In analyzing the point-to-point wireless channel, insights about two qualitatively different operating regimes-bandwidth and power-limited-have proven indispensable in the design of good communication schemes. In this paper, we propose a new scaling law formulation for wireless networks that allows us to develop a theory that is analogous to the point-to-point case. We identify fundamental operating regimes of wireless networks and derive architectural guidelines for the design of optimal schemes. Our analysis shows that in a given wireless network with arbitrary size, area, power, bandwidth, etc., there are three parameters of importance: the short-distance signal-to-noise ratio (SNR), the long-distance SNR, and the power path loss exponent of the environment. Depending on these parameters, we identify four qualitatively different regimes. One of these regimes is especially interesting since it is fundamentally a consequence of the heterogeneous nature of links in a network and does not occur in the point-to-point case; the network capacity is both power and bandwidth limited. This regime has thus far remained hidden due to the limitations of the existing formulation. Existing schemes, either multihop transmission or hierarchical cooperation, fail to achieve capacity in this regime; we propose a new hybrid scheme that achieves capacity.

Hierarchical cooperation has recently been shown to achieve better throughput scaling than classical multihop schemes under certain assumptions on the channel model in static wireless networks. However, the end-to-end delay of this scheme turns out to be significantly larger than those of multihop schemes. A modification of the scheme is proposed here that achieves a throughput-delay tradeoffD(n) = (logn)2T(n) forT(n) between¿(¿(n)/logn) and¿(n/logn), whereD(n) andT(n) are respectively the average delay per bit and the aggregate throughput in a network ofnnodes. This tradeoff complements the previous results of El Gamal et al. , which show that the throughput-delay tradeoff for multihop schemes is given byD(n) =T(n) whereT(n) lies between¿(1)and¿(¿(n).

Recent results have shown that interference alignment can achieve K/2 degrees of freedom in a K-user interference channel with time or frequency varying channel coefficients. For fixed number of users K, the number of degrees of freedom characterizes the asymptotic behavior of the performance in the high SNR limit but it does not answer the question of how the performance scales with K for any fixed SNR. In particular, it is unclear if a constant rate per user can be maintained as more users enter into the system. In this paper, we investigate the performance of the interference alignment scheme proposed in for fixed SNR. We assume that the channel coefficients between the users are of the form r ejthetaswhere r is fixed over the duration of communication and thetas is a fast fading phase. We show that for any value of the SNR and K, the aggregate rate achieved by the interference alignment scheme of is lower bounded by c1K log(1 + c2SNR) where c1and c2are positive constants independent of both SNR and K. This result establishes the linear scaling of the interference alignment scheme for the considered random phase channel model.

In analyzing the point-to-point wireless channel, insights about two qualitatively different operating regimes-bandwidth- and power-limited-have proven indispensable in the design of good communication schemes. In this paper, we propose a new scaling law formulation for wireless networks that allows us to develop a theory that is analogous to the point-to-point case. We identify fundamental operating regimes of wireless networks and derive architectural guidelines for the design of optimal schemes. Our analysis shows that in a given wireless network with arbitrary size, area, power, etc., there are three parameters of importance: the short-distance SNR, the long-distance SNR, and the power path loss exponent. Depending on these parameters we identify four qualitatively different regimes. One of these regimes is especially interesting since it is fundamentally a consequence of the heterogeneous nature of links in a network and does not occur in the point-to-point case; the network capacity is both power- and bandwidth-limited. This regime has thus far remained hidden due to the limitations of the existing formulation. Existing schemes, either multihop transmission or hierarchical cooperation, fail to achieve capacity in this regime; we propose a new hybrid scheme that achieves capacity.

n source and destination pairs randomly located in a fixed area want to communicate with each other. It is well known that classical multihop architectures that decode and forward packets can deliver at most a radicn-scaling of the aggregate throughput. The performance is limited by the mutual interference between communicating nodes. We show however that a linear scaling of the capacity with n can in fact be achieved by more intelligent node cooperation and distributed MIMO communication. The key ingredient is a hierarchical and digital architecture for nodal exchange of information for realizing the cooperation.

n source and destination pairs randomly located in an area extending linearly with n want to communicate with each other. Signals transmitted from one user to another at distance r apart are subject to a power attenuation of r-αand random phase changes. Classical multihop architectures that decode and forward packets can deliver a √n-scaling of the aggregate throughput, while recently proposed hierarchical cooperation achieves n2-α/2-scaling, which is superior to multi-hop for α4, while the moderate-attenuation regime (2 ≤ α ≤ 4) remains uncharacterized. We close this gap by deriving a tight upper bound on the scaling of the aggregate throughput, valid for all α ≥ 2. Our result shows that the mentioned schemes are scaling-optimal, namely that no other scheme can beat hierarchical cooperation when α < 3, nor can it beat classical multi-hop when α ≥ 3. The key ingredient is a careful evaluation of the scaling of the cut-set bound.

The capacity scaling of extended two-dimensional wireless networks is known in the high-attenuation regime, i.e., when the power path loss exponent alpha is greater than 4. This has been accomplished by deriving information-theoretic upper bounds for this regime that match the corresponding lower bounds. On the contrary, not much is known in the so-called low-attenuation regime when 2lesalphales4. (For one-dimensional networks, the uncharacterized regime is 1lesalphales2.5.) The dichotomy is due to the fact that while communication is highly power-limited in the first case and power-based arguments suffice to get tight upper bounds, the study of the low-attenuation regime requires a more precise analysis of the degrees of freedom involved. In this paper, we study the capacity scaling of extended wireless networks with an emphasis on the low-attenuation regime and show that in the absence of small scale fading, the low attenuation regime does not behave significantly different from the high attenuation regime.

n source and destination pairs randomly located in an area want to communicate with each other. Signals transmitted from one user to another at distance r apart are subject to a power loss of r-alphaas well as a random phase. We identify the scaling laws of the information-theoretic capacity of the network when nodes can relay information for each other. In the case of dense networks, where the area is fixed and the density of nodes increasing, we show that the total capacity of the network scales linearly with n. This improves on the best known achievability result of n2/3of Aeron and Saligrama. In the case of extended networks, where the density of nodes is fixed and the area increasing linearly with n, we show that this capacity scales as n2-alpha/2for 2lesalpha4. Thus, much better scaling than multihop can be achieved in dense networks, as well as in extended networks with low attenuation. The performance gain is achieved by intelligent node cooperation and distributed multiple-input multiple-output (MIMO) communication. The key ingredient is a hierarchical and digital architecture for nodal exchange of information for realizing the cooperation.