Estimating the true prevalence of an epidemic outbreak is a key public health problem. This is challenging because surveillance is usually resource intensive and biased. In the network setting, prior work on cost sensitive disease surveillance has focused on choosing a subset of individuals (or nodes) to minimize objectives such as probability of outbreak detection. Such methods do not give insights into the outbreak size distribution which, despite being complex and multi-modal, is very useful in public health planning. We introduce TESTPREV, a problem of choosing a subset of nodes which maximizes the mutual information with disease prevalence, which directly provides information about the outbreak size distribution. We show that, under the independent cascade (IC) model, solutions computed by all prior disease surveillance approaches are highly sub-optimal for TESTPREV in general. We also show that TESTPREV is hard to even approximate. While this mutual information objective is computationally challenging for general networks, we show that it can be computed efficiently for various network classes. We present a greedy strategy, called GREEDYMI, that uses estimates of mutual information from cascade simulations and thus can be applied on any network and disease model. We find that GREEDYMI does better than natural baselines in terms of maximizing the mutual information as well as reducing the expected variance in outbreak size, under the IC model.

Deep neural networks are vulnerable to adversarial perturbations, limiting deployment in safety-critical applications such as synthetic aperture radar (SAR) automatic target recognition (ATR). Randomized smoothing improves robustness by averaging predictions over noisy inputs, but isotropic noise often fails to preserve the semantic structure of SAR imagery. We propose semantic smoothing, a defense that replaces noised-based perturbations with structured randomized transformations generated by a novel view synthesis model. For SAR, we condition on acquisition geometry to synthesize multiple plausible radar views. Predictions across generated randomized views are aggregated to form a robust classifier. Experiments show that semantic smoothing improves robustness against standard attacks, such as FGSM and PGD, and SAR-specific attacks, such as OTSA and SMGAA, while also increasing clean classification accuracy. These results demonstrate that randomized smoothing via semantically preserving geometric transformations is a promising alternative to isotropic noise for adversarial defense in structured sensing domains.

In our previous works [1, 2, 3], we defined$(\epsilon ,\delta )$-Local Information Privacy (LIP) as a context-aware privacy notion and presented the corresponding privacy-preserving mechanism. Then we claim that the mechanism satisfies$(\epsilon ,0)$-LIP for any$\epsilon \gt 0$for arbitrary$P_{X}$. However, this claim is not completely correct. In this document, we provide a correction to the valid range of privacy parameters of our previously proposed LIP mechanism. Further, we propose efficient algorithms to expand the range of valid privacy parameters. Finally, we discuss the impact on our experimental results, the rationale of the proposed correction and corrected results. Proofs of the main results in this paper are provided in our full version [6].

We propose a new and intuitive metric for aleatoric uncertainty quantification (UQ), the prevalence of class collisions defined as the same input being observed in different classes. We use the rate of class collisions to define the collision matrix, a novel and uniquely fine-grained measure of uncertainty. For a classification problem involvingKclasses, theK×Kcollision matrixSmeasures the inherent difficulty in distinguishing between each pair of classes. We discuss several applications of the collision matrix, establish its fundamental mathematical properties, and show its relationship with existing UQ methods, including the Bayes error rate (BER). We also address the new problem of estimating the collision matrix using one-hot labeled data by proposing a series of innovative techniques to estimate S. First, we learn a pair-wise contrastive model which accepts two inputs and determines if they belong to the same class. We then show that this contrastive model (which is PAC learnable) can be used to estimate the row Gramian matrix ofS, defined asG = SST. Finally, we show that under reasonable assumptions, G can be used to uniquely recoverS, a new result on non-negative matrices which could be of independent interest. With a method to estimateSestablished, we demonstrate how this estimate ofS, in conjunction with the contrastive model, can be used to estimate the posterior class probability distribution of any point. Experimental results are also presented to validate our methods of estimating the collision matrix and class posterior distributions on several datasets.

In this work, the problem of communicating decisions of a classifier over a noisy channel is considered. With machine learning based models being used in variety of time-sensitive applications, transmission of these decisions in a reliable and timely manner is of significant importance. To this end, we study the scenario where a probability vector (representing the decisions of a classifier) at the transmitter, needs to be transmitted over a noisy channel. Assuming that the distortion between the original probability vector and the reconstructed one at the receiver is measured via f-divergence, we study the trade-off between transmission latency and the distortion. We completely analyze this trade-off using uniform, lattice, and sparse lattice-based quantization techniques to encode the probability vector by first characterizing bit budgets for each technique given a requirement on the allowed source distortion. These bounds are then combined with results from finite-blocklength literature to provide a framework for analyzing the effects of both quantization distortion and distortion due to decoding error probability (i.e., channel effects) on the incurred transmission latency. Our results show that there is an interesting interplay between source distortion (i.e., distortion for the probability vector measured via f-divergence) and the subsequent channel encoding/decoding parameters. We observe that the source distortion can be optimized for each quantization technique to attain a minimum latency. Our results also indicate that sparse lattice-based quantization is the most effective at minimizing latency for low end-to-end distortion requirements across different parameters and works best for sparse, high-dimensional probability vectors (i.e., high number of classes). To corroborate our framework, we use the quantization techniques on predictions made on real datasets and send them through a simulated channel. We use the metric of ‘relative accuracy’ to measure how often the class assigned with the highest probability by the classifier at the transmitter is correctly identified after transmission. Our results indicate that the lattice-based techniques require significantly smaller blocklengths than uniform quantization (subsequently incurring smaller latencies) but can still provide a comparable performance to uniform quantization.

Certifiable robustness gives the guarantee that small perturbations around an input to a classifier will not change the prediction. There are two approaches to provide certifiable robustness to adversarial examples– a) explicitly training classifiers with small Lipschitz constants, and b) Randomized smoothing, which adds random noise to the input to create a smooth classifier. We proposeSPLITZ, a practical and novel approach which leverages the synergistic benefits of both the above ideas into a single framework. Our main idea is tosplita classifier into two halves, constrain the Lipschitz constant of the first half, and smooth the second half via randomization. Motivation forSPLITZcomes from the observation that many standard deep networks exhibit heterogeneity in Lipschitz constants across layers.SPLITZcan exploit this heterogeneity while inheriting the scalability of randomized smoothing. We present a principled approach to trainSPLITZand provide theoretical analysis to derive certified robustness guarantees during inference. We present a comprehensive comparison of robustness-accuracy trade-offs and show thatSPLITZconsistently improves on existing state-of-the-art approaches in the MNIST, CIFAR-10 and ImageNet datasets. For instance, with ℓ2norm perturbation budget of ϵ = 1,SPLITZachieves 43.2% top-1 test accuracy on CIFAR-10 dataset compared to state-of-art top-1 test accuracy 39.8%.

High-Level Synthesis (HLS) Design Space Exploration (DSE) is a widely accepted approach for efficiently exploring Pareto-optimal and optimal hardware solutions during the HLS process. Several HLS benchmarks and datasets are available for the research community to evaluate their methodologies. Unfortunately, these resources are limited and may not be sufficient for complex, multi-component system-level explorations. Generating new data using existing HLS benchmarks can be cumbersome, given the expertise and time required to effectively generate data for different HLS designs and directives. As a result, synthetic data has been used in prior work to evaluate system-level HLS DSE. However, the fidelity of the synthetic data to real data is often unclear, leading to uncertainty about the quality of system-level HLS DSE. This paper proposes a novel approach, called Vaegan, that employs generative machine learning to generate synthetic data that is robust enough to support complex system-level HLS DSE experiments that would be unattainable with only the currently available data. We explore and adapt a Variational Autoencoder (VAE) and Generative Adversarial Network (GAN) for this task and evaluate our approach using state-of-the-art datasets and metrics. We compare our approach to prior works and show that Vaegan effectively generates synthetic HLS data that closely mirrors the ground truth’s distribution.

In this work, the problem of communicating decisions of a classifier over a noisy channel is considered. with machine learning based models being used in variety of time-sensitive applications, transmission of these decisions in a reliable and timely manner is of significant importance. To this end, we study the scenario where a probability vector (representing the decisions of a classifier) at the transmitter, needs to be transmitted over a noisy channel. Under the assumption that the distortion between the original probability vector and the reconstructed one at the receiver is measured via f-divergence, we study the trade-off between transmission latency and the distortion. We completely analyze this trade-off for the setting when uniform quantization is used to encode the probability vector, and the latency incurred is obtained via results on finite-blocklength channel capacity. Our results show that there is an interesting interplay between source distortion (i.e., distortion for the probability vector measured via f-divergence) and the subsequent channel encoding/decoding parameters; and indicate that a joint design of these parameters is crucial to navigate the latency-distortion tradeoff.

Counterfactuals, or modified inputs that lead to a different outcome, are an important tool for understanding the logic used by machine learning classifiers and how to change an undesirable classification. Even if a counterfactual changes a classifier’s decision, however, it may not affect the true underlying class probabilities, i.e. the counterfactual may act like an adversarial attack and “fool” the classifier. We propose a new framework for creating modified inputs that change the true underlying probabilities in a beneficial way which we call Trustworthy Actionable Perturbations (TAP). This includes a novel verification procedure to ensure that TAP change the true class probabilities instead of acting adversarially. Our framework also includes new cost, reward, and goal definitions that are better suited to effectuating change in the real world. We present PAC-learnability results for our verification procedure and theoretically analyze our new method for measuring reward. We also develop a methodology for creating TAP and compare our results to those achieved by previous counterfactual methods.

With the growing adoption of machine learning (ML) systems in areas like law enforcement, criminal justice, finance, hiring, and admissions, it is increasingly critical to guarantee the fairness of decisions assisted by ML. In this paper, we study the tradeoff between fairness and accuracy under the statistical notion of equalized odds. We present a new upper bound on the accuracy (that holds for any classifier), as a function of the fairness budget. In addition, our bounds also exhibit dependence on the underlying statistics of the data, labels and the sensitive group attributes. We validate our theoretical upper bounds through empirical analysis on three real-world datasets: COMPAS, Adult, and Law School. Specifically, we compare our upper bound to the tradeoffs that are achieved by various existing fair classifiers in the literature. Our results show that achieving high accuracy subject to a low-bias could be fundamentally limited based on the statistical disparity across the groups.

Publishing streaming data in a privacy-preserving manner has been a key research focus for many years. This issue presents considerable challenges, particularly due to the correlations prevalent within the data stream. Existing approaches either fall short in effectively leveraging these correlations, leading to a suboptimal utility-privacy tradeoff, or they involve complex mechanism designs that increase the computation complexity with respect to the sequence length. In this paper, we introduce Sequence Information Privacy (SIP), a new privacy notion designed to guarantee privacy for an entire data stream, taking into account the intrinsic data correlations. We show that SIP provides a similar level of privacy guarantee compared to local differential privacy (LDP), and it also enjoys a lightweight modular mechanism design. We further study two online data release models (instantaneous or batched) and propose corresponding privacy-preserving data perturbation mechanisms. We provide a numerical evaluation of how correlations influence noise addition in data streams. Lastly, we conduct experiments using real-world data to compare the utility-privacy tradeoff offered by our approaches with those from existing literature. The results reveal that our mechanisms achieve better utility-privacy tradeoff than the state-of-the-art LDP-based mechanisms. Notably, the improvements become more significant for small privacy budgets.

Machine learning based approaches are being increasingly used for designing decoders for next generation communication systems. One widely used framework is neural belief propagation (NBP), which unfolds the belief propagation (BP) iterations into a deep neural network and the parameters are trained in a data-driven manner. NBP decoders have been shown to improve upon classical decoding algorithms. In this paper, we investigate the generalization capabilities of NBP decoders. Specifically, the generalization gap of a decoder is the difference between empirical and expected bit-error-rate(s). We present new theoretical results which bound this gap and show the dependence on thedecoder complexity, in terms of code parameters (blocklength, message length, variable/check node degrees), decoding iterations, and the training dataset size. Results are presented for both regular and irregular parity-check matrices. To the best of our knowledge, this is the first set of theoretical results on generalization performance of neural network based decoders. We present experimental results to show the dependence of generalization gap on the training dataset size, and decoding iterations for different codes.

Machine learning based approaches are being increasingly used for designing decoders for next generation communication systems. One widely used framework is neural belief propagation (NBP), which unfolds the belief propagation (BP) iterations into a deep neural network and the parameters are trained in a data-driven manner. NBP decoders have been shown to improve upon classical decoding algorithms. In this paper, we investigate the generalization capabilities of NBP decoders. Specifically, the generalization gap of a decoder is the difference between empirical and expected bit-error-rate(s). We present new theoretical results which bound this gap and show the dependence on the decoder complexity, in terms of code parameters (blocklength, message length, variable/check node degrees), decoding iterations, and the training dataset size. Results are presented for both regular and irregular parity-check matrices. To the best of our knowledge, this is the first set of theoretical results on generalization performance of neural network based decoders. We present experimental results to show the dependence of generalization gap on the training dataset size, and decoding iterations for different codes.

In this paper, we consider the problem of answering count queries for genomic data subject to perfect privacy constraints. Count queries are often used in applications that collect aggregate (population-wide) information from biomedical Databases (DBs) for analysis, such as Genome-wide association studies. Our goal is to design mechanisms for answering count queries of the following form:How many users in the database have a specific set of genotypes at certain locations in their genome?At the same time, we aim to achieve perfect privacy (zero information leakage) of the sensitive genotypes at a pre-specified set of secret locations. The sensitive genotypes could indicate rare diseases and/or other health traits one may want to keep private. We present both local and central count-query mechanisms for the above problem that achieves perfect information-theoretic privacy for sensitive genotypes while minimizing the expected absolute error (or per-user error probability, depending on the setting) of the query answer. We also derived a lower bound of the per-user probability of error for an arbitrary query-answering mechanism that satisfies perfect privacy. We show that our mechanisms achieve error close to the lower bound, and match the lower bound for some special cases. We numerically show that the performance of each mechanism depends on the data prior distribution, the intersection between the queried and sensitive genotypes, and the strength of the correlation in the genomic data sequence.

The goal of community detection over graphs is to recover underlying labels/attributes of users (e.g., political affiliation) given the connectivity between users. There has been significant recent progress on understanding the fundamental limits of community detection when the graph is generated from a stochastic block model (SBM). Specifically, sharp information theoretic limits and efficient algorithms have been obtained for SBMs as a function of $p$ and $q$, which represent the intra-community and inter-community connection probabilities. In this paper, we study the community detection problem while preserving the privacy of the individual connections between the vertices. Focusing on the notion of $(\epsilon, \delta)$-edge differential privacy (DP), we seek to understand the fundamental tradeoffs between $(p, q)$, DP budget $(\epsilon, \delta)$, and computational efficiency for exact recovery of community labels. To this end, we present and analyze the associated information-theoretic tradeoffs for three differentially private community recovery mechanisms: a) stability based mechanism; b) sampling based mechanisms; and c) graph perturbation mechanisms. Our main findings are that stability and sampling based mechanisms lead to a superior tradeoff between $(p,q)$ and the privacy budget $(\epsilon, \delta)$; however this comes at the expense of higher computational complexity. On the other hand, albeit low complexity, graph perturbation mechanisms require the privacy budget $\epsilon$ to scale as $\Omega(\log(n))$ for exact recovery.

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

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

In this article, we propose local information privacy (LIP), and design LIP based mechanisms for statistical aggregation while protecting users’ privacy without relying on a trusted third party. The concept of context-awareness is incorporated in LIP, which can be viewed as exploiting of data prior (both in privatizing and post-processing) to enhance data utility. We present an optimization framework to minimize the mean square error of data aggregation while protecting the privacy of each user’s input data or a correlated latent variable by satisfying LIP constraints. Then, we study optimal mechanisms under different scenarios considering the prior uncertainty and correlation with a latent variable. Three types of mechanisms are studied in this article, including randomized response (RR), unary encoding (UE), and local hashing (LH), and we derive closed-form solutions for the optimal perturbation parameters that are prior-dependent. We compare LIP-based mechanisms with those based on LDP, and theoretically show that the former achieve enhanced utility. We then study two applications: (weighted) summation and histogram estimation, and show how proposed mechanisms can be applied to each application. Finally, we validate our analysis by simulations using both synthetic and real-world data. Results show the impact on data utility by different prior distributions, correlations, and input domain sizes. Results also show that our LIP-based mechanisms provide better utility-privacy tradeoffs than LDP-based ones.

The topological interference management (TIM) problem refers to the study of the$K$-user partially connected interference networks with no channel state information at the transmitters (CSIT), except for the knowledge of network topology. In this paper, we study the TIM problem with confidential messages (TIM-CM), where message confidentiality must be satisfied in addition to reliability constraints. In particular, each transmitted message must be decodable at its intended receiver and remain confidential at the remaining$(K-1)$receivers. Our main contribution is to present a comprehensive set of results for the TIM-CM problem by studying the symmetric secure degrees of freedom (SDoF). To this end, we first characterize necessary and sufficient conditions for feasibility of positive symmetric SDoF for any arbitrary topology. We next present two achievable schemes for the TIM-CM problem: For the first scheme, we use the concept of secure partition and, for the second one, we use the concept of secure independent sets. We also present outer bounds on symmetric SDoF for any arbitrary network topology. Using these bounds, we characterize the optimal symmetric SDoF of all$K=2$-user and$K=3$-user network topologies.

The classic wiretap channel (WTC) problem is concerned with a transmitter (Alice) that wants to send a message$W$to the intended receiver (Bob) while keeping it secret from a passive eavesdropper (Eve). However, under certain communication scenarios, the user may not be interested in hiding the entire message from the eavesdropper, but rather in hiding its most sensitive attributes. While classic wiretap coding is capable of hiding these salient message attributes, it may be too stringent and better communication rates may be achievable. Motivated by the above, in this paper, we introduce and study the latent variable wiretap channel (LV-WTC) problem. Under this setting, the transmitter is interested in sending the message$W$to the intended receiver while keeping a correlated latent variable$S$(which models privacy sensitive attributes) secret from the eavesdropper. We present a message splitting based achievable scheme for the LV-WTC problem, which adapts to the structure of the conditional distribution PS|Wto achieve higher rates compared to the classical WTC. Several open problems and future directions that originate from this new communication problem are also discussed.

In latent-variable private information retrieval (LV-PIR), a user wishes to retrieve one out of$K$messages (indexed by θ) without revealing any information about a sensitive latent attribute (modeled by a latent variable$S$correlated with θ). While conventional PIR protocols, which keep θ2private, also suffice for hiding S, they can be too costly in terms of the download overhead. In this paper, we characterize the capacity (equivalently, the optimal download cost) of LV-PIR as a function of the distribution PS|θ. We present a converse proof that yields a lower bound on the optimal download cost, and a matching achievable scheme. The optimal scheme, however, involves an exhaustive search over subset queries and over all messages, which can be computationally prohibitive. We further present two low-complexity, albeit sub-optimal, schemes that also outperform the conventional PIR solution.

In this paper, we study the problem of federated learning over a wireless channel with user sampling, modeled by a Gaussian multiple access channel, subject to central and local differential privacy (DP/LDP) constraints. It has been shown that the superposition nature of the wireless channel provides a dual benefit of bandwidth efficient gradient aggregation, in conjunction with strong DP guarantees for the users. Specifically, the central DP privacy leakage has been shown to scale as$\mathcal{O}(1/\sqrt{K})$, where$K$is the number of users. It has also been shown that user sampling coupled with orthogonal transmission can enhance the central DP privacy leakage with the same scaling behavior. In this work, we show that, by jointly incorporating both wireless aggregation and user sampling, one can obtain even stronger central DP guarantees. We propose a private wireless gradient aggregation scheme, which relies on independently randomized participation decisions by each user. The central DP leakage of our proposed scheme scales as$\mathcal{O}(1/K^{3/4})$. In addition, we show that LDP is also boosted by user sampling.

In this paper, we study the problem of federated learning over a wireless channel with user sampling, modeled by a fading multiple access channel, subject to central and local differential privacy (DP/LDP) constraints. It has been shown that the superposition nature of the wireless channel provides a dual benefit of bandwidth efficient gradient aggregation, in conjunction with strong DP guarantees for the users. Specifically, the central DP privacy leakage has been shown to scale as$\mathcal {O}(1/K^{1/2})$, where$K$is the number of users. It has also been shown that user sampling coupled with orthogonal transmission can enhance the central DP privacy leakage with the same scaling behavior. In this work, we show that, by jointly incorporating both wireless aggregation and user sampling, one can obtain even stronger privacy guarantees. We propose a private wireless gradient aggregation scheme, which relies on independently randomized participation decisions by each user. The central DP leakage of our proposed scheme scales as$\mathcal {O}(1/K^{3/4})$. In addition, we show that LDP is also boosted by user sampling. We also present analysis for the convergence rate of the proposed scheme and study the tradeoffs between wireless resources, convergence, and privacy theoretically and empirically for two scenarios when the number of sampled participants are$(a)$known, or$(b)$unknown at the parameter server.

In this paper, we study Local Information Privacy (LIP). As a context-aware privacy notion, LIP relaxes the de facto standard privacy notion of local differential privacy (LDP) by incorporating prior knowledge and therefore achieving better utility. We study the relationships between LIP and some of the representative privacy notions including LDP, mutual information and maximal leakage. We show that LIP provides strong instance-wise privacy protection compared to other context-aware privacy notions. Moreover, we present some useful properties of LIP, including post-processing, linkage, composability, transferability and robustness to imperfect prior knowledge. Then we study a general utility-privacy tradeoff framework, under which we derive LIP based privacy-preserving mechanisms for both discrete and continuous-valued data. Three types of perturbation mechanisms are studied in this paper: 1) randomized response (RR), 2) random sampling (RS) and 3) additive noise (AN) (e.g., Gaussian mechanism). Our privacy mechanisms incorporate the prior knowledge into the perturbation parameters so as to enhance utility. Finally, we present a comprehensive set of experiments on real datasets to illustrate the advantage of context-awareness and compare the utility-privacy tradeoffs provided by different mechanisms.

Information-theoretic formulations of the private information retrieval (PIR) problem have been investigated under a variety of scenarios. Symmetric private information retrieval (SPIR) is a variant where a user is able to privately retrieve one out of K messages from N non-colluding replicated databases without learning anything about the remaining K-1 messages. However, the goal of perfect privacy can be too taxing for certain applications. In this paper, we investigate if the information-theoretic capacity of SPIR (equivalently, the inverse of the minimum download cost) can be increased by relaxing both user and DB privacy definitions. Such relaxation is relevant in applications where privacy can be traded for communication efficiency. We introduce and investigate the Asymmetric Leaky PIR (AL-PIR) model with different privacy leakage budgets in each direction. For user privacy leakage, we bound the probability ratios between all possible realizations of DB queries by a function of a non-negative constant ϵ. For DB privacy, we bound the mutual information between the undesired messages, the queries, and the answers, by a function of a non-negative constant δ. We propose a general AL-PIR scheme that achieves an upper bound on the optimal download cost for arbitrary ϵ and δ. We show that the optimal download cost of AL-PIR is upper-bounded as D*(ϵ,δ) ≤ 1+\frac 1N-1-\frac δeϵNK-1-1. Second, we obtain an information-theoretic lower bound on the download cost as D*(ϵ,δ) ≥ 1+\frac 1Neϵ-1-\frac δ(Neϵ)K-1-1. The gap analysis between the two bounds shows that our AL-PIR scheme is optimal when ϵ = 0, i.e., under perfect user privacy and it is optimal within a maximum multiplicative gap of \frac N-e-ϵN-1 for any ϵ > 0 and δ > 0.

In this work, we study the problem of federated learning (FL), where distributed users aim to jointly train a machine learning model with the help of a parameter server (PS). In each iteration of FL, users compute local gradients, followed by transmission of the quantized gradients for subsequent aggregation and model updates at PS. One of the challenges of FL is that of communication overhead due to FL's iterative nature and large model sizes. One recent direction to alleviate communication bottleneck in FL is to let users communicate simultaneously over a multiple access channel (MAC), possibly making better use of the communication resources. In this paper, we consider the problem of FL over a MAC. We focus on the design of digital gradient transmission schemes over a MAC, where gradients at each user are first quantized, and then transmitted over a MAC to be decoded individually at the PS. When designing digital FL schemes over MACs, there are new opportunities to assign different amount of resources (e.g., rate or bandwidth) to different users based on a) the informativeness of the gradients at users, and b) the underlying channel conditions. We propose a stochastic gradient quantization scheme, where the quantization parameters are optimized based on the capacity region of the MAC. We show that such channel aware quantization for FL outperforms uniform quantization, particularly when users experience different channel conditions, and when have gradients with varying levels of informativeness.

The topological interference management (TIM) problem is a framework for studying partially connected interference networks with no channel state information at transmitters (CSIT), except network topology. TIM is a more pragmatic setting as CSIT is often available imperfectly, or may not be available at all. In this paper, we study the TIM problem with confidential messages, denoted in short by the secure TIM (STIM) problem. More specifically, we focus on the STIM problem for half-rate-feasible (HRF) networks. Half-rate-feasible networks are a class of partially connected interference networks whose sum degrees of freedom (DoF) have been characterized by K/2, without any secrecy constraints. The main contribution of this paper is as follows: We design achievable schemes for HRF networks subject to secrecy constraints, and present a lower bound on the secure degrees of freedom (SDoF). To this end, we first show the necessity of classifying HRF networks into two sub-categories based on some properties of the underlying network topology. As it turns out, the division of HRF networks into these sub-categories is critical for the design of secure transmission schemes. We then leverage the underlying topological properties along with ideas from secure interference alignment (SIA) in order to design achievable schemes for both subclasses of HRF networks.

We provide unsupervised machine learning (ML) schemes based on autoencoders for unconstrained beamforming (BF) and hybrid BF in millimeter-waves (mmWaves). An autoencoder is a powerful unsupervised ML model, and it is used to reconstruct the input with a minimal error by finding a low-dimensional representation of the input. In this paper, we present a linear autoencoder for finding the beamformers at the transmitter (Tx) and receiver (Rx), which maximize the achieved rates over the mmWave channel. Since the autoencoder has a close relationship with the singular value decomposition (SVD), we first study autoencoders for unconstrained BF based on SVD. In hybrid BF, beamformers are designed by using finite-precision phase shifters in the radio frequency (RF) domain along with power constraints. Therefore, we propose a hybrid BF algorithm based on autoencoders, which incorporates these constraints. We present our simulation results for both unconstrained BF as well as hybrid BF, and compare their performance with state-of-the-art. By using the stochastic and NYUSIM channel models, we achieve 30 - 40% and 60 - 70% gains in rates with the proposed autoencoder based approach compared to the supervised hybrid BF with the stochastic and NYUSIM channel models, respectively.

In this paper, we analyze the regret bound of Multi-armed Bandit (MAB) algorithms under the setting where the payoffs of an arbitrary-size cluster of arms are observable in each round. Compared to the well-studied bandit or full feedback setting, where the payoffs of the selected arm or all the arms are observable, the clustered feedback setting can be viewed as a generalization and a connection. We focus on two most representative MAB algorithms: Upper Confidence Bound and Thompson sampling, and adapt them into the clustered feedback setting. Then, we theoretically derive the regret bound for each of them considering the general type of payoffs (value comes from continuous domains). We show that the regret bounds of these two algorithms with clustered information feedback depend only on the number of clusters. Finally, we simulate both synthetic data and real-world data to compare the performance of these algorithms with different numbers of observable payoffs in each round, the results validate our analysis.

In many applications, content accessed by users (movies, videos, news articles, etc.) can leak sensitive latent attributes, such as religious and political views, sexual orientation, ethnicity, gender, and others. To prevent such information leakage, the goal of classical PIR is to hide the identity of the content/message being accessed, which subsequently also hides the latent attributes. This solution, while private, can be too costly, particularly, when perfect (information-theoretic) privacy constraints are imposed. For instance, for a single database holding K messages, privately retrieving one message is possible if and only if the user downloads the entire database of K messages. Retrieving content privately, however, may not be necessary to perfectly hide the latent attributes.Motivated by the above, we formulate and study the problem of latent-variable private information retrieval (LV-PIR), which aims at allowing the user efficiently retrieve one out of K messages (indexed by θ) without revealing any information about the latent variable (modeled by S). We focus on the practically relevant setting of a single database and show that one can significantly reduce the download cost of LV-PIR (compared to the classical PIR) based on the correlation between θ and S. We present a general scheme for LV-PIR as a function of the statistical relationship between θ and S, and also provide new results on the capacity/download cost of LV-PIR. Several open problems and new directions are also discussed.

In this paper, we study the problem of federated learning (FL) over a wireless channel, modeled by a Gaussian multiple access channel (MAC), subject to local differential privacy (LDP) constraints. We show that the superposition nature of the wireless channel provides a dual benefit of bandwidth efficient gradient aggregation, in conjunction with strong LDP guarantees for the users. We propose a private wireless gradient aggregation scheme, which shows that when aggregating gradients from K users, the privacy leakage per user scales as O(1/√K) compared to orthogonal transmission in which the privacy leakage scales as a constant. We also present analysis for the convergence rate of the proposed private FL aggregation algorithm and study the tradeoffs between wireless resources, convergence, and privacy.

In this paper, we propose a new approach to design finite alphabet iterative decoders (FAIDs) for Low-Density Parity Check (LDPC) codes over binary symmetric channel (BSC) via recurrent quantized neural networks (RQNN). We focus on the linear FAID class and use RQNNs to optimize the message update look-up tables by jointly training their message levels and RQNN parameters. Existing neural networks for channel coding work well over Additive White Gaussian Noise Channel (AWGNC) but are inefficient over BSC due to the finite channel values of BSC fed into neural networks. We propose the bit error rate (BER) as the loss function to train the RQNNs over BSC. The low precision activations in the RQNN and quantization in the BER cause a critical issue that their gradients vanish almost everywhere, making it difficult to use classical backward propagation. We leverage straight-through estimators as surrogate gradients to tackle this issue and provide a joint training scheme. We show that the framework is flexible for various code lengths and column weights. Specifically, in high column weight case, it automatically designs low precision linear FAIDs with superior performance, lower complexity, and faster convergence than the floating-point belief propagation algorithms in waterfall region.

We investigate the secure degrees of freedom (SDoF) of the multiple-input multiple-output (MIMO) wiretap channel with intersymbol interference (ISI) in the presence of a multi-antenna cooperative jammer. We focus on the practically relevant setting with no channel state information at the transmitters (CSIT). More specifically, the legitimate transmitter and the cooperative jammer only have statistical knowledge of the channel in terms of the effective number of ISI channel taps, i.e., channel impulse response (CIR) lengths, toward the legitimate receiver and the eavesdropper. Our main contribution is to show that in the absence of CSIT, positive SDoF can be achieved by carefully exploiting: 1) the heterogeneity of the CIR lengths toward both receivers and 2) the relative number of antennas at the four terminals. To achieve secrecy, we propose a scheme in which the transmitter strategically sends a mixture of information and artificial noise symbols in a way that exploits the heterogeneity of CIR lengths. Additionally, the cooperative jammer transmits artificial noise symbols in a way that completely masks all the information symbols that are received at the eavesdropping node. Under the proposed scheme, positive SDoF can be achieved, even when the number of antennas at the legitimate receiver is less than the number of antennas at the eavesdropper.

Private information retrieval (PIR) allows a user to retrieve a desired message from a set of databases without revealing the identity of the desired message. The replicated database scenario, where N databases store each of the K messages was considered by Sun and Jafar, and the optimal download cost was characterized as (1+ 1/N+1/N2+ ⋯ + 1/NK-1). In this work, we consider the problem of PIR from uncoded storage constrained databases. Each database has a storage capacity of μKL bits, where L is the size of each message in bits, and μ ∈ [1/N, 1] is the normalized storage. The novel aspect of this work is to characterize the optimum download cost of PIR from uncoded storage constrained databases for any “normalized storage” value in the range μ ∈ [1/N, 1]. In particular, for any (N, K), we show that the optimal trade-off between normalized storage, μ, and the download cost, D(μ), is a piece-wise linear function given by the lower convex hull of the N pairs (t/N,(1 + 1/t + 1/t2+ ⋯ + 1/tK-1))for t=1,2,...,N. To prove this result, we first present a storage constrained PIR scheme for any (N, K). Next, we obtain a general lower bound on the download cost for PIR, which is valid for any arbitrary storage architecture. The uncoded storage assumption is then applied which allows us to express the lower bound as a linear program (LP). Finally, we solve the LP to obtain tight lower bounds on the download cost for different regimes of storage, which match the proposed storage constrained PIR scheme.

Hybrid beamforming (BF), which divides BF operation into radio frequency (RF) and baseband (BB) domains, will play a critical role in MIMO communication at millimeter-wave (mmW) frequencies. In principle, we can obtain unconstrained (optimum) beamformers of a transceiver, which approach the maximum achievable data rates, through its singular value decomposition (SVD). Due to the use of finite-precision phase shifters, combined with power constraints, additional challenges are imposed on the problem of designing hybrid beamformers. Motivated by the recent success of machine learning (ML) techniques, particularly in areas such as computer vision and speech recognition, we explore if ML techniques can be effectively used for SVD and hybrid BF. To this end, we first present a data-driven approach to compute the SVD. We propose three deep neural network (DNN) architectures to approximate the SVD, with varying levels of complexity. The methodology for training these DNN architectures is inspired by the fundamental property of SVD, i.e., it can be used to obtain low-rank approximations. We next explicitly take the constraints of hybrid BF into account (such as quantized phase shifters, power constraints), and propose a novel DNN based approach for the design of hybrid BF systems. To validate the DNN based approach, we present simulation results for both approximating the SVD as well as for hybrid BF. Our results show that DNNs can be an attractive and efficient solution for estimating SVD in a data-driven manner. For the simulations of hybrid BF, we first consider the geometric channel model. We show that the DNN based hybrid BF improves rates by up to 50 - 70% compared to conventional hybrid BF algorithms and achieves 10 - 30% gain in rates compared with the state-of-art ML-aided hybrid BF algorithms. We also discuss the impact of the choice of hyperparameters, such as the number of hidden layers, mini-batch size, and training iterations on the accuracy of DNNs. Furthermore, we provide time complexity and memory requirement analyses for the proposed approach and state-of-the-art approaches.

In this paper, we introduce a method of using quantized neural networks (QNN) to design finite alphabet message passing decoders (FAID) for Low-Density Parity Check (LDPC) codes. Specifically, we construct a neural network with low precision activations to optimize a FAID over Additive White Gaussian Noise Channel (AWGNC). The low precision activations cause a critical issue that their gradients vanish almost everywhere, making it difficult to use classical backward propagation. We introduce straight-through estimators (STE) to avoid this problem, by replacing zero derivatives of quantized activations with surrogate gradients in the chain rules. We present a systematic approach to train such networks while minimizing the bit error rate, which is a widely used and accurate metric to measure the performance of iterative decoders. Examples and simulations show that by training a QNN, a FAID with 3-bit of message and 4-bit of channel output can be obtained, which performs better than the more complex floating-point minsum decoding algorithm. This methodology is promising in the sense that it facilitates designing low-precision FAID for LDPC codes while maintaining good error performance in a flexible and efficient manner.

Matrix multiplication is a fundamental building block for large scale computations arising in various applications, including machine learning. There has been significant recent interest in using coding to speed up distributed matrix multiplication, that are robust to stragglers (i.e., machines that may perform slower computations). In many scenarios, instead of exact computation, approximate matrix multiplication, i.e., allowing for a tolerable error is also sufficient. Such approximate schemes make use of randomization techniques to speed up the computation process. In this paper, we initiate the study of approximate coded matrix multiplication, and investigate the joint synergies offered by randomization and coding. Specifically, we propose two coded randomized sampling schemes that use (a) codes to achieve a desired recovery threshold and (b) random sampling to obtain approximation of the matrix multiplication. Tradeoffs between the recovery threshold and approximation error obtained through random sampling are investigated for a class of coded matrix multiplication schemes.

A localized privacy protection notion: local information privacy (LIP) is studied in this paper. As a context-aware notion that considers prior knowledge, the LIP notion is shown to provide increased utility than local differential privacy (LDP). Within the scope of LIP, we further consider scenarios with uncertainty on the prior knowledge, i.e., the prior is bounded within a certain range or the prior is arbitrary. The former case is defined as bounded-prior LIP (BP-LIP), and the latter as worst-case LIP (WC-LIP). The contributions of this paper are three-fold: We first provide theoretical results which show the connections of these new definitions with LDP; Secondly, we present an optimization framework for privacy-preserving data collection, with the goal of minimizing the expected squared error while satisfying BP-LIP and WC-LIP privacy constraints. Utility-privacy tradeoffs are obtained in closed-form. At last, we validate our conclusions by numerical analysis and real-world data simulation. Our results show that the notion of bounded-prior LIP can achieve better utility-privacy tradeoff compared to context free notion of LDP.

We consider the problem of K-user interference channel with confidential messages (IC-CM) with intersymbol interference (ISI). The main contribution of this paper is to show that sum-secure degrees of freedom (SDoF) can be made to linearly increase with the number of users K in the absence of channel state information at the transmitters (CSIT). The proposed scheme entails three main ingredients : a) leveraging the simple channel matrix structures resulting from the orthogonal frequency division multiplexing (OFDM) type transmission technique in order to eliminate interference and allow coherent decoding of each message at its respectively intended receiver. b) exploiting the inherent heterogeneity in channel impulse response (CIR) lengths between the transmitters and the receivers (which results from the wireless multipath propagation), and c) injection of artificial noise into the transmitted signal from a strategically chosen small number of transmitters J that act as cooperative jammers in order to preserve full confidentiality of the messages at the unintended receivers. This is the first work showing that the SDoF of the K-user IC-CM with ISI can linearly increase with the number of users without CSIT.

Private information retrieval (PIR) allows users to retrieve data from databases without revealing the identity of that data. An extensive body of works has investigated efficient schemes to achieve computational and information-theoretic privacy. The latter guarantees that no information is revealed to the databases, irrespective of their computational power. Although information-theoretic PIR (IT-PIR) provides a strong privacy guarantee, it can be too taxing for certain applications. In this paper, we initiate the study of leaky private information retrieval (L-PIR), where a bounded amount of privacy leakage is allowed and measured through a parameter ε. The classical IT-PIR formulation is obtained by setting ε = 0, and for ε > 0, we explore the opportunities offered for reducing the download cost. We derive new upper and lower bounds on the download cost of L-PIR for any arbitrary ε, any number of messages K, and for N = 2 databases.

In this paper, we study the problem of secure and private distributed matrix multiplication. Specifically, we focus on a scenario where a user wants to compute the product of a confidential matrix A, with a matrix Bθ, where θ ∈ {1,..., M}. The set of candidate matrices {B1,..., BM} are public, and available at all the N servers. The goal of the user is to distributedly compute ABθ, such that (a) no information is leaked about the matrix A to any server; and (b) the index θ is kept private from each server. Our goal is to understand the fundamental tradeoff between the upload vs download cost for this problem. Our main contribution is to show that the lower convex hull of following (upload, download) pairs: (U,D) = (N/(K - 1), (K/(K - 1)) (1 + (K/N) + ··· + (K/N)M-1)) for K = 2, ..., N is achievable. The scheme improves upon state-of-the-art existing schemes for this problem, and leverages ideas from secret sharing and coded private information retrieval.

In this paper, we consider the problem of designing additive noise mechanisms for data release subject to a local information privacy constraint. While there has been significant prior work on devising additive noise mechanisms for differential privacy (such as Laplacian and Gaussian mechanisms), for the notion of information privacy, which accounts for prior-knowledge about the data, there are no such general purpose additive noise mechanisms. To this end, we devise a prior-aware Laplacian noise mechanism, which satisfies local information privacy. We show that adding context awareness (i.e., via the knowledge of prior of the data) improves the tradeoff between utility and privacy when compared to context-unaware mechanisms.

We consider the problem of protecting individual user's location privacy at the trace-level and study the privacy-utility trade-off, which has key applications in privacy-preserving location-based service. Existing works on Location Privacy Protection Mechanisms (LPPMs) have mainly focused on protecting single location, without taking into account the temporal correlations among locations within the trace, which can lead to higher privacy leakage when considering the whole trace. However, to date, there lacks a formal framework to quantify the trace-level location privacy leakage, and a practical mechanism to release location traces in an optimal and online manner. In this paper, we endeavor to solve this problem using an information-theoretic approach. We first propose a location trace privacy metric based on the mutual information between the original and released trace in an offline setting, and formulate the optimal location trace release problem that minimizes trace-level privacy leakage given a utility constraint. We also propose a privacy metric to capture trace-level privacy leakage in an online setting. As directly computing these metrics incur exponential complexity w.r.t. the trace length, we obtain upper and lower bounds on the trace-level privacy leakage by exploiting the Markov structure of the temporal location correlations, which are efficiently computable. The proposed upper bounds enable us to derive efficient online solutions (i.e., LPPMs) by modifying Blahut-Arimoto algorithm in rate-distortion theory. Then we validate the proposed upper and lower bounds and the actual leakage of our LPPM through extensive experiments over both synthetic and real-world location data sets. Our results show the superiority of our LPPM over existing LPPMs in terms of trace-level privacy-utility tradeoff, which is more conspicuous when the location trace is more correlated.

Data shuffling between distributed cluster of nodes is one of the critical steps in implementing large-scale learning algorithms. Randomly shuffling the data-set among a cluster of workers allows different nodes to obtain fresh data assignments at each learning epoch. This process has been shown to provide improvements in the learning process (via testing and training error). However, the statistical benefits of distributed data shuffling come at the cost of extra communication overhead from the master node to worker nodes, and can act as one of the major bottlenecks in the overall time for computation. There has been significant recent interest in devising approaches to minimize this communication overhead. One approach is to provision for extra storage at the computing nodes. The other emerging approach is to leverage coded communication to minimize the overall communication overhead. The focus of this work is to understand the fundamental tradeoff between the amount of storage and the communication overhead for distributed data shuffling. In this paper, we first present an information theoretic formulation for the data shuffling problem, accounting for the underlying problem parameters (number of workers, K, number of data points, N, and available storage, and S per node). We then present an information theoretic lower bound on the communication overhead for data shuffling as a function of these parameters. We next present a novel coded communication scheme and show that the resulting communication overhead of the proposed scheme is within a multiplicative factor of at most K-1 from the lower bound (which is upper bounded by 2 for K/K ≥ 2). Furthermore, we present new results towards closing this gap through a novel coded communication scheme, which we call the aligned coded shuffling. This scheme is inspired by the ideas of coded shuffling and interference alignment. In particular, we show that the aligned scheme achieves the optimal storage vs communication trade-off for K <; 5, and further reduces the K-1 maximum multiplicative gap down to K-1/3/k-1, for K ≥ 5.

Matrix multiplication is one of the key operations in various engineering applications. Outsourcing large-scale matrix multiplication tasks to multiple distributed servers or cloud is desirable to speed up computation. However, security becomes an issue when these servers are untrustworthy. In this paper, we study the problem of secure distributed matrix multiplication from distributed untrustworthy servers. This problem falls in the category of secure function computation and has received significant attention in the cryptography community. However, characterizing the fundamental limits of information-theoretically secure matrix multiplication remain an open problem. We focus on information-theoretically secure distributed matrix multiplication with the goal of characterizing the minimum communication overhead. The capacity of secure matrix multiplication is defined as the maximum possible ratio of the desired information and the total communication received from N distributed servers. In particular, we study the following two models where we want to multiply two matrices A ∈ \mathbbFm×nand B ∈ \mathbbFn×p: (a) one-sided secure matrix multiplication with l colluding servers, in which B is a public matrix available at all servers and A is a private matrix. (b) fully secure matrix multiplication with l colluding servers, in which both A and B are private matrices. The goal is to securely multiply A and B when any l servers can collude. For model (a), we characterize the capacity as Cone-sided(l)= (N-l)/N by providing a secure matrix multiplication scheme and a matching converse. For model (b), we propose a novel scheme that lower bounds the capacity, i.e., Cfuly ≥ (√N-l)2/(√N-l+l)2.

The radio frequency spectrum is occupied with authorized and unauthorized user activities which might include noise and interference. Detection of signals-of-interest (SOI) and differentiation from non-signals-of-interest (NSOI) are therefore crucial for frequency use management. There is a wide variety of signals in a desired radio spectrum band, which leads to the application of Signal Intelligence (SIGINT) to detect and identify signals in real-time. In this paper, we study the problem of non-Gaussian signal detection when the receivers are configured with a large number of antennas (or the massive antenna regime). First, we investigate the performance of signal detection with massive MIMO when the transmitted signals are generated from a Gaussian distribution. For the detection of Gaussian signals, we consider the Neyman-Pearson (NP) detector. Then, we focus on the performance of non-Gaussian signal detection with massive MIMO, which is one of the main objectives of this paper. We show that the NP detector gives poor performance for non-Gaussian signals in low signal-to- noise-ratio (SNR). Therefore, we propose to use a bispectrum detector, which contains the Gaussian noise and reveals the non-Gaussian information that exists in the signal. We present the theoretical analysis for asymptotic behavior of Probability of False Alarm (PFA) and Probability of Detection (PD) when the transmitter sends Gaussian and non-Gaussian signals. We show the performance of signal detection (for both Gaussian and non-Gaussian signals) as a function of the number of antennas and sampling rate. We also obtain the scaling behavior of the performance in the massive antenna regime.

We study the impact of untrusted relays on the degrees of freedom of multi-antenna multi-hop networks. In par- ticular, we consider the two user two-hop interference network, where two source nodes want to send independent messages securely to their designated receivers through the help of two untrusted relays. The relays are considered untrusted in terms of eavesdropping the messages sent by the sources. Moreover, we also assume that the messages are confidential, i.e., each receiver must not be able to decode the information meant for the other receiver. We assume that all the terminals (i.e., sources, relays, and the receivers) are equipped with multiple number of antennas. The goal of this work is to understand the secure degrees of freedom (SDoF) region of this multi-hop MIMO network under the two constraints of a) untrusted relays; and b) confidential messages. To cope with the untrusted nature of relays, we present achievable schemes in which both sources mix their information symbols with artificial noises so that the signals at each relay are completely immersed in the artificial noises space. However, this mixing must be done carefully, so as to ensure the feasibility of interference neutralization in the second hop to allow successful decoding at the respective destination. To this end, we devise transmission schemes based on interference alignment and interference neutralization techniques. The main contributions of this work are as follows: a) we present an upper bound on the SDoF region as a function of the number of antennas at the terminals, b) we present two achievable schemes, the first scheme is based on secure interference alignment and neutralization and is shown to be information theoretically optimal when all terminals have the same number of antennas; and a second scheme, based on secure sub-space alignment and neutralization, which is shown to be optimal for another specific antenna configuration. To the best of our knowledge, these are the first results on multi-hop MIMO relay networks with untrusted relays and confidential messages.

Private information retrieval (PIR) allows a user to retrieve a desired message out of K possible messages from N databases without revealing the identity of the desired message. There has been significant recent progress on understanding fundamental information-theoretic limits of PIR, and in particular the download cost of PIR for several variations. Majority of existing works however, assume the presence of replicated databases, each storing all the K messages. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of μKL bits, where K is the number of messages, L is the size of each message in bits, and μ ∈ [1/N, 1] is the normalized storage. In the storage constrained PIR problem, there are two key design questions: a) how to store content across each database under storage constraints; and b) construction of schemes that allow efficient PIR through storage constrained databases. The main contribution of this work is a general achievable scheme for PIR from storage constrained databases for any value of storage. In particular, for any (N, K), with normalized storage μ = t/N, where the parameter t can take integer values t ∈ {1, 2, ..., N}, we show that our proposed PIR scheme achieves a download cost of (1 + 1/t + 1/2 + ⋯ + 1/tK-1). The extreme case when μ = 1 (i.e., t = N) corresponds to the setting of replicated databases with full storage. For this extremal setting, our scheme recovers the information-theoretically optimal download cost characterized by Sun and Jafar as (1 + 1/N + ⋯ +1/NK-1). For the other extreme, when μ = 1/N (i.e., t = 1), the proposed scheme achieves a download cost of K. The most interesting aspect of the result is that for intermediate values of storage, i.e., 1/N <; μ <; 1, the proposed scheme can strictly outperform memory-sharing between extreme values of storage.

Private information retrieval (PIR) allows a user to retrieve a desired message out of$K$possible messages from$N$databases (DBs) without revealing the identity of the desired message. In this work, we consider the problem of PIR from uncoded storage constrained DBs. Each DB has a storage capacity of$\mu KL$bits, where$L$is the size of each message in bits, and$\mu\in[1/N,\ 1]$is the normalized storage. In the storage constrained PIR problem, there are two key challenges: a) construction of communication efficient schemes through storage content design at each DB that allow download efficient PIR; and b characterizing the optimal download cost via information-theoretic lower bounds. The novel aspect of this work is to characterize the optimum download cost of PIR with storage constrained DBs for any value of storage. In particular, for any$(N,\ K)$, we show that the optimal tradeoff between storage$(\mu)$and the download cost$(D(\mu))$is given by the lower convex hull of the pairs$(\frac{t}{N}(1+\frac{1}{t}+\frac{1}{t^{2}}+\cdots+\frac{1}{t^{K-1}}))$for$t$= 1,2, …, N. The main contribution of this paper is the converse proof, i.e., obtaining lower bounds on the download cost for PIR as a function of the available storage.

Data shuffling between distributed workers is one of the critical steps in implementing large-scale learning algorithms. The focus of this work is to understand the fundamental trade-off between the amount of storage and the communication overhead for distributed data shuffling. We first present an information theoretic formulation for the data shuffling problem, accounting for the underlying problem parameters (i.e., number of workers, K, number of data points, N, and the available storage, S per node). Then, we derive an information theoretic lower bound on the communication overhead for data shuffling as a function of these parameters. Next, we present a novel coded communication scheme and show that the resulting communication overhead of the proposed scheme is within a multiplicative factor of at most 2 from the lower bound. Furthermore, we introduce an improved aligned coded shuffling scheme, which achieves the optimal storage vs communication trade-off for K <; 5, and further reduces the maximum multiplicative gap down to 7/6, for K ≥ 5.

In this paper, the K-user interference channel with confidential messages is considered with delayed channel state information at transmitters (CSIT). We propose a novel secure transmission scheme in which the transmitters carefully mix information symbols with artificial noises to ensure confidentiality. Achieving confidentiality is challenging due to the delayed nature of CSIT, and the distributed nature of the transmitters. Our scheme works over two phases: phase one in which each transmitter sends information symbols mixed with artificial noises, and repeats such transmission over multiple rounds. In the next phase, each transmitter uses delayed CSIT of the previous phase and sends a function of the net interference and artificial noises (generated in previous phase), which is simultaneously useful for all receivers. These phases are designed to ensure the decodability of the desired messages while satisfying the confidentiality constraints. The proposed scheme achieves a sum secure degrees of freedom (SDoF) of at least [1/2](√K-6). To the best of our knowledge, this is the first result on the K-user interference channel with confidential messages and delayed CSIT that achieves a SDoF which scales with K -.

Fog radio access network (F-RAN) architectures can leverage both cloud processing and edge caching for content delivery to the users. To this end, F-RAN utilizes caches at the edge nodes (ENs) and fronthaul links connecting a cloud processor to ENs. Assuming time-invariant content popularity, existing information-theoretic analyses of content delivery in F-RANs rely on offline caching with separate content placement and delivery phases. In contrast, this paper focuses on the scenario in which the set of popular content is time-varying, hence necessitating the online replenishment of the ENs' caches along with the delivery of the requested files. The analysis is centered on the characterization of the long-term normalized delivery time (NDT), which captures the temporal dependence of the coding latencies accrued across multiple time slots in the high signal-to-noise ratio regime. Online edge caching and delivery schemes are investigated for both serial and pipelined transmission modes across fronthaul and edge segments. Analytical results demonstrate that, in the presence of a time-varying content popularity, the rate of fronthaul links sets a fundamental limit on the long-term NDT of F-RAN system. Analytical results are further verified by numerical simulation, yielding important design insights.

This paper considers a K-cell multiple access channel with inter-symbol interference. The primary finding of this paper is that, without instantaneous channel state information at the transmitters, interference-free degrees-of-freedom (DoF) per cell is achievable, provided that the delay spread of the desired links is significantly longer than that of the interfering links when the number of user per cell is sufficiently large. This achievability is shown by a blind interference management method that exploits the relativity in delay spreads between desired and interfering links. In this method, all inter-cell-interference signals are aligned-and-cancelled by using discrete-Fourier-transform-based precoding and combining, both depend only on the lengths of channel-impulse-response. In addition to the DoF analysis, the achievable rate of the proposed method is characterized in a closed-form expression. Some illustrative examples are presented to show an additional sum-DoF gain obtained by exploiting propagation delay in the interfering links or the heterogeneity of the channel coherence time between the desired and interfering links.

RF front-end nonlinearity makes receivers vulnerable to adjacent channel interference that significantly impacts receiver performance. Next generation (5G) wireless networks will see unprecedented diversity across receiver and radio technologies accessing the same band of spectrum in spatio-temporal vicinity. Ensuring adjacent channel co-existence is of prime importance for successful deployment and operations of 5G systems. In this paper, we develop a fundamental framework to analyze the adjacent channel co-existence by quantifying the impact of receiver RF front-end nonlinearity on performance. We develop novel tractable discrete representation of third order intermodulation, cross-modulation, and compressive distortion of the receiver front end to describe adjacent channel interference using unit basis vectors. We further analyze the impact of nonlinearity on receiver performance by evaluating the limits on achievable rate accounting for RF front-end nonlinearity. Based on this analysis we provide a framework to compare disparate receivers by forming generalized metrics. We then use these metrics to quantify the performance detriment for a reference input spectrum. We illustrate the importance of the proposed frameworks and the ensuing rate analysis for reference inputs for adjacent channel co-existence analysis and quantifying receiver performance.

Radio frequency (RF) front-end nonlinearity significantly impairs receiver performance in non-intuitive ways. Receivers are susceptible to harmful adjacent channel interference, especially in next-generation networks with diverse radio access technologies, co-existing in space, time, and frequency. Vulnerabilities of receiver front-ends can have a severe detrimental effect on network performance and spectrum co-existence. In this paper, we propose centralized controller-based receiver-centric framework for spectrum access that accounts for receiver front-end nonlinearity, pre-selector filter bandwidth, and transmitter out-of-band emission characteristics for networks with diverse RF-layer characteristics. Furthermore, we propose computationally efficient algorithms to optimize the receiver-centric framework and examine network level performance. We demonstrate through extensive network simulations that the proposed receiver-centric framework provides substantially higher spectrum efficiency gains over receiver-agnostic spectrum access and improves co-existence in dense and diverse next-generation wireless networks. We further demonstrate through simulations that the proposed algorithms achieve close to optimal solutions for receiver-centric network optimization.

We investigate secure degrees of freedom (SDoF) of a single-input single-output (SISO) wiretap channel with a single helper without channel state information at the transmitters (CSIT). Wireless communication systems inherently suffer from intersymbol interference (ISI) due to channel dispersion. In this paper, we propose a novel blind cooperative jamming scheme that exploits the ISI heterogeneity to achieve positive SDoF, even without any CSIT. In order to achieve positive SDoF, the proposed approach only requires statistical properties of the ISI channel. In particular, we show that if LB is the effective ISI channel multipath link length towards the legitimate receiver (Bob) and LE is the link length towards the eavesdropper (Eve), a positive SDoF of LB-LE is achievable. To the best of our 2(LB -1) knowledge, this is the first work that exploits ISI link length heterogeneity to achieve positive secure degrees of freedom.

In this work, we focus on the partially connected interference network with confidential messages, and study the secure degrees of freedom with no channel state information at the transmitters (CSIT). Prior works on fully connected interference networks with full CSIT have shown that the secure degrees of freedom scales linearly with the number of users. With no CSIT, however, the secure degrees of freedom of fully connected networks collapses to zero. In this work, we show that partial connectivity, a widely prevalent property of wireless networks, can be leveraged to provide secrecy even with no CSIT. We present a systematic approach to first understand the feasibility of secure communication in a partially connected network and develop achievable schemes for a class of regular partially connected networks. Finally, we also provide novel information theoretic outer bounds on the secure degrees of freedom for this class of regular partially connected networks, and approximately characterize the secure degrees of freedom.

Adjacent channel interference caused by intermodulation distortion adversely affects the network operations in next generation heterogeneous and dynamic spectrum access networks. Multitudes of radio access technologies make the receivers susceptible to harmful interference due to nonlinear RF front ends. In this paper we analyze the intermodulation distortion arising from pairwise interactions of adjacent channel signals from a spectrum centric point of view and develop frameworks to ascertain the adjacent channel signals causing interference at a given desired channel. We further propose achievable schemes for interference avoidance and assess the scalability of the next generation Nonlinear Adjacent Channel Interference Networks. We further propose schemes for complete interference protection of incumbents with sensitive receiver requirements from secondary operations in adjacent channels in the spatio-temporal vicinity. This paper presents valuable insights on scalability and schemes for nonlinear adjacent channel interference avoidance in next generation shared spectrum networks.

In a Fog Radio Access Network (F-RAN) architecture, edge nodes (ENs), such as base stations, are equipped with limited-capacity caches, as well as with fronthaul links that can support given transmission rates from a cloud processor. Existing information-theoretic analyses of content delivery in F-RANs have focused on offline caching with separate content placement and delivery phases. In contrast, this work considers an online caching set-up, in which the set of popular files is time-varying and both cache replenishment and content delivery can take place in each time slot. The analysis is centered on the characterization of the long-term Normalized Delivery Time (NDT), which captures the temporal dependence of the coding latencies accrued across multiple time slots in the high signal-to-noise ratio regime. Online caching and delivery schemes based on reactive and proactive caching are investigated, and their performance is compared to optimal offline caching schemes both analytically and via numerical results.

This paper considers a K-cell multiple access channel with inter-symbol interference (ISI). The primary finding of this paper is that, without instantaneous channel state information at a transmitter, the interference-free sum degrees of freedom of K is asymptotically achievable when the number of users per cell is sufficiently large, and also when the number of channel-impulse-response taps of desired links is greater than that of interfering links. This achievability is shown by a blind interference management method that exploits the relativity in delay spreads between desired and interfering links.

In this paper, we investigate the total delivery latency across the fronthaul and wireless segments of a Fog Radio Access Network (F-RAN) under the assumption that cloud processor and edge nodes (ENs) are connected by a multicast fronthaul link. The total delivery latency is assessed via the Normalized Delivery Time (NDT) metric which provides a high signal-to- noise ratio (SNR) measure of the relative delivery worst-case latency with respect to an interference-free system. We derive upper and lower bounds on the achievable NDT for a F-RAN with two ENs and two users as a function of cache and fronthaul resources. The upper bound is obtained by studying the NDT achieved by delivery strategies that encompass both coded and uncoded multicast strategies on the fronthaul. The lower bound is instead derived by leveraging information theoretic converse arguments. Upper and lower bounds are shown to coincide, hence characterizing the minimum NDT, for a large range of problem parameters. Among the conclusions of this study, we demonstrate that coded multicasting is not useful for reducing the NDT for the mentioned range of parameters.

The increase in data storage and power consumption at data-centers has made it imperative to design energy efficient distributed storage systems (DSS). The energy efficiency of DSS is strongly influenced not only by the volume of data, frequency of data access and redundancy in data storage, but also by the heterogeneity exhibited by the DSS in these dimensions. To this end, we propose and analyze the energy efficiency of a heterogeneous distributed storage system in which$n$storage servers (disks) store the data of$R$distinct classes. Data of class$i$is encoded using a$(n,k_{i})$erasure code and the (random) data retrieval requests can also vary across classes. We show that the energy efficiency of such systems is closely related to the average latency and hence motivates us to study the energy efficiency via the lens of average latency. Through this connection, we show that erasure coding serves the dual purpose of reducing latency and increasing energy efficiency. We present a queuing theoretic analysis of the proposed model and establish upper and lower bounds on the average latency for each data class under various scheduling policies. Through extensive simulations, we present qualitative insights which reveal the impact of coding rate, number of servers, service distribution and number of redundant requests on the average latency and energy efficiency of the DSS.

Caching at the network edge has emerged as a viable solution for alleviating the severe capacity crunch in modern content centric wireless networks by leveraging network load-balancing in the form of localized content storage and delivery. In this paper, we consider a cache-aided network, where the cache storage phase is assisted by a central server and users can demand multiple files at each transmission interval. To service these demands, we consider two delivery models: (1) centralized content delivery, where user demands at each transmission interval are serviced by the central server via multicast transmissions; and (2) device-to-device assisted distributed delivery, where users multicast to each other in order to service file demands. For such cache-aided networks, we present new results on the fundamental cache storage versus transmission rate tradeoff. Specifically, we develop a new technique for characterizing information theoretic lower bounds on the storage-rate tradeoff and show that the new lower bounds are strictly tighter than cut-set bounds from literature. Furthermore, using the new lower bounds, we improve the constant factor approximation of the optimal storage-rate tradeoff for cache-aided systems under both delivery models.

The two user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM) is studied, in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form Ii, i = 1, 2 where I1, I2∈ {P, D, N}, and the forms P, D, and N correspond to perfect and instantaneous, completely delayed, and no CSIT, respectively. Thus, the overall CSIT can alternate between nine possible states corresponding to all possible values of I1I2, with each state occurring for λI1I2fraction of the total duration. We assume that perfect and instantaneous CSI is available at the all receivers. The main contribution of this paper is to establish the secure degrees of freedom (s.d.o.f.) region of the MISO BCCM with alternating CSIT with the symmetry assumption, where λI1I2= λI2I1. The main technical contributions include developing 1) novel achievable schemes for MISO BCCM with alternating CSIT with security constraints, which also highlight the synergistic benefits of inter-state coding for secrecy; 2) new converse proofs via local statistical equivalence and channel enhancement; and 3) showing the interplay between various aspects of channel knowledge and their impact on s.d.o.f.

A fog-aided wireless network architecture is studied in which edge nodes (ENs), such as base stations, are connected to a cloud processor via dedicated fronthaul links while also being endowed with caches. Cloud processing enables the centralized implementation of cooperative transmission strategies at the ENs, albeit at the cost of an increased latency due to fronthaul transfer. In contrast, the proactive caching of popular content at the ENs allows for the low-latency delivery of the cached files, but with generally limited opportunities for cooperative transmission among the ENs. The interplay between cloud processing and edge caching is addressed from an information-theoretic viewpoint by investigating the fundamental limits of a high signal-to-noise-ratio metric, termed normalized delivery time (NDT), which captures the worst case coding latency for delivering any requested content to the users. The NDT is defined under the assumptions of either serial or pipelined fronthaul-edge transmission, and is studied as a function of fronthaul and cache capacity constraints. Placement and delivery strategies across both fronthaul and wireless, or edge, segments are proposed with the aim of minimizing the NDT. Information-theoretic lower bounds on the NDT are also derived. Achievability arguments and lower bounds are leveraged to characterize the minimal NDT in a number of important special cases, including systems with no caching capabilities, as well as to prove that the proposed schemes achieve optimality within a constant multiplicative factor of 2 for all values of the problem parameters.

Data shuffling is one of the fundamental building blocks for distributed learning algorithms, that increases the statistical gain for each step of the learning process. In each iteration, different shuffled data points are assigned by a central node to a distributed set of workers to perform local computation, which leads to communication bottlenecks. The focus of this paper is on formalizing and understanding the fundamental information-theoretic tradeoff between storage (per worker) and the worst-case communication overhead for the data shuffling problem. We completely characterize the information theoretic tradeoff for K = 2, and K = 3 workers, for any value of storage capacity, and show that increasing the storage across workers can reduce the communication overhead by leveraging coding. We propose a novel and systematic data delivery and storage update strategy for each data shuffle iteration, which preserves the structural properties of the storage across the workers, and aids in minimizing the communication overhead in subsequent data shuffling iterations.

Caching of popular multimedia content at small-cell base stations (BSs) is a promising solution to reduce the traffic load of macro-BSs without relying on a high-speed backhaul architecture. While most prior work analyzed the effect of smallcell caching, or femto-caching, under the assumption of negligible interference between macro-BS and small-cell BS, this paper contributes to a more recent line of work in which the benefits of caching are reconsidered in the presence of interference on the downlink channel. In particular, a binary fading one-sided interference channel is considered in which the small-cell BS, whose transmission is interfered by the macro-BS, has a limitedcapacity cache. An information-theoretic metric that captures the delivery latency is defined and fully characterized through information-theoretic achievability and converse arguments as a function of the cache capacity, as well as of the capacity of the backhaul link connecting cloud and small-cell BS.

Fog Radio Access Network (F-RAN) is an emerging wireless network architecture that leverages caching capabilities at the wireless edge nodes, as well as edge connectivity to the cloud via fronthaul links. This paper aims at providing a latency-centric analysis of the degrees of freedom of an F-RAN by accounting for the total content delivery delay across the fronthaul and wireless segments of the network. The main goal of the analysis is the identification of optimal caching, fronthaul and edge transmission policies. The study is based on the introduction of a novel performance metric, referred to as the Normalized Delivery Time (NDT), which measures the total delivery latency as compared to an ideal interference-free system. An information-theoretically optimal characterization of the trade-off between NDT, on the one hand, and fronthaul and caching resources, on the other, is derived for a class of F-RANs with two edge nodes and two users. Using these results, the interplay between caching and cloud connectivity is highlighted, as well as the impact of both caching and fronthaul resources on the delivery latency.

We study the impact of heterogeneity of channel-state-information available at the transmitters (CSIT) on the capacity of broadcast channels with a multiple-antenna transmitter and k single-antenna receivers (MISO BC). In particular, we consider the k-user MISO BC, where the CSIT with respect to each receiver can be either instantaneous/perfect, delayed, or not available; and we study the impact of this heterogeneity of CSIT on the degrees-of-freedom (DoFs) of such network. We first focus on the three-user MISO BC, and we completely characterize the DoF region for all possible heterogeneous CSIT configurations, assuming linear encoding strategies at the transmitters. The result shows that the state-of-the-art achievable schemes in the literature are indeed sum-DoF optimal, when restricted to linear encoding schemes. To prove the result, we develop a novel bound, called interference decomposition bound, which provides a lower bound on the interference dimension at a receiver which supplies delayed CSIT based on the average dimension of constituents of that interference, thereby decomposing the interference into its individual components. Furthermore, we extend our outer bound on the DoF region to the general k-user MISO BC, and demonstrate that it leads to an approximate characterization of linear sum-DoF to within an additive gap of 0.5 for a broad range of CSIT configurations. Moreover, for the special case where only one receiver supplies delayed CSIT, we completely characterize the linear sum-DoF.

Distributed storage systems (DSSs) in the presence of an external wiretapper are considered. A DSS is parameterized by (n, k, d), in which the data are stored across n nodes (each with storage capacity α), and must be recoverable by accessing the contents stored on any k out of n nodes. If a node fails, any d ≥ k out of (n - 1) nodes help in the repair (regeneration) of the failed node (by sending dβ units of repair data, where β ≤ α), so that the data can still be recovered from the DSS. For such a (n, k, d)-DSS, security from the two types of wiretappers is investigated: 1) Type-I (node data) wiretapper, which can read the data stored on any ℓ <; k nodes and 2) Type-II (repair data) wiretapper, which can read the data that is used to repair a set of ℓ failed nodes. The focus of this paper is on the optimal tradeoff between the storage (α) and the repair bandwidth (dβ) in presence of a Type-I/Type-II wiretapper and the practically relevant constraint of exact repair in which a failed node must be replaced by its exact replica. In this paper, several new results and outer bounds for the storage-versus-exact-repair-bandwidth tradeoff(s) are obtained for the Type-I and Type-II security problems. Furthermore, new outer bounds are presented for the Type-II problem, which hold for general (n, k, d, ℓ) parameters. It is shown that these outer bounds strictly improve upon the existing cutset-based outer bounds. The key technical contribution of this paper is in developing novel information theoretic converse proofs for these problems. From our optimal characterization results, we show that in a Type-II setting, the only efficient point in the storage-versus-exact-repair-bandwidth tradeoff is the minimum bandwidth regenerating (MBR) point corresponding to α = dβ. This is in sharp contrast to the Type-I setting in which the optimal tradeoff allows a spectrum of operating points beyond the MBR point.

In recent years, the amount of information shared (both implicit and explicit) between traditional news media and social media sources like Twitter has grown at a prolific rate. Traditional news media is dependent on social media to help identify emerging developments; social media is dependent on news media to supply information in certain categories. In this paper, we present a principled framework for understanding their symbiotic relationship, with the goal of (1) understanding the type of information flow between news articles and the Twitterverse by classifying it into four states; (2) chaining similar news articles together to form story chains and extracting interaction patterns for each story chain in terms of interaction states of news articles in the story chain, and (3) identifying major interaction patterns by clustering story chains and understanding their differences by identifying main topics of interest within such clusters.

We consider 2-user symmetric interference channels with confidential messages. For the linear deterministic model of this channel, we develop inner and outer bounds for the symmetric secure rate, which are shown to match and characterize the symmetric secure capacity for a wide range of channel parameters. For the achievability, we present a cooperative jamming scheme based on interference alignment principle, which is optimal for all regimes where the symmetric secure capacity is established. For the converse, a tighter outer bound than all previously existing ones is provided for the regime where the symmetric secure capacity is still open.

RF front-end characteristics significantly impact the performance of the receiver. Receivers are vulnerable to harmful adjacent channel interference, especially in shared spectrum environments, which allow a free-style of spectrum access with diverse receiver technologies accessing the same band of spectrum. Channel assignments agnostic to receiver characteristics can have a severe detrimental effect on network level performance of a wireless network. In this paper, we develop a novel dynamic channel assignment framework which accounts for the vulnerabilities posed by RF front end, in particular, receiver pre-selector bandwidth and front-end nonlinearity. We further propose an approximate, heuristic, greedy algorithm for channel assignment which is computationally efficient and provides a near-optimal solution. We demonstrate through simulations that the developed framework of receiver characteristics aware dynamic channel assignment will substantially improve the network-wide data rate, and thereby the overall spectrum efficiency of the wireless network. We further demonstrate that the approximate algorithm provides a near-optimal solution for channel assignment in the statistical sense.

We study the impact of heterogeneity of channel state information available to the transmitters (CSIT) on the performance of multi-antenna multi-user wireless networks. More specifically, we consider the 3-user multiple-input single-output (MISO) broadcast channel, where the available CSIT with respect to each receiver can be instantaneous (P), delayed (D), or none (N); and we characterize the extent to which such heterogeneity of CSIT impacts its linear degrees of freedom (LDoF). In particular, we completely characterize the DoF region for all possible CSIT configurations, assuming linear encoding strategies at the transmitters. The converse, which is the main contribution of the paper, is based on a novel lemma, called Interference Decomposition Bound, which provides a lower bound on the interference dimension at a receiver with delayed CSIT, based on the dimension of constituents of that interference, thereby decomposing the interference into its individual components.

The two-user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM) is studied in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form Ii, i = 1, 2 where I1; I2∈ {P;D;N}, and the forms P, D and N correspond to perfect and instantaneous, completely delayed, and no CSIT, respectively. Thus, the overall CSIT can alternate over time between 9 possible states corresponding to all possible values of I1I2, with each state occurring for λI1I2fraction of the total duration. The main contribution of this paper is to establish the secure degrees of freedom (s.d.o.f.) region of the MISO BCCM with alternating CSIT with the symmetry assumption λI1I2= λI2I1. The results highlight the synergistic benefits of coding across CSIT states for secrecy and the interplay between various aspects of channel knowledge and its impact on s.d.o.f.

Characterizing the exact repair storage-vs-repair bandwidth tradeoff for distributed storage systems remains an open problem for more than four storage nodes. Motivated by the prevalence and practical applicability of linear codes, the exact repair problem when restricted to linear codes is considered. The main result of this paper is a new approach to develop bounds for exact repair distributed storage systems with linear codes (LDSS). Using this approach, the exact repair region for the (k + 1, k, k) LDSS is completely characterized. The new approach utilizes the properties of linear codes together with the exact repair constraints. These constraints are formally captured through an optimization problem with a recursive structure, and its solution finally yields the new bounds for the LDSS. These bounds together with recent code constructions characterize the exact repair region for (k + 1, k, k) LDSS.

Real-time data-driven systems often utilize discrete valued time series data and their functionality is highly dependent on the accuracy of such data. In order to improve the performance of these systems, an important pre-processing step is the denoising of data before performing any action (e.g. forecasting or control activities). Existing algorithms have primarily focused on the offline denoising problem, which requires the entire data to be collected before the denoising process. In this paper, the problem of online discrete denoising is considered. The online denoising problem is motivated by real-time applications, where the data must be utilizable soon after it is collected. Three online denoising algorithms are proposed which can strike a tradeoff between delay and accuracy of denoising. It is also shown that the proposed online algorithms asymptotically converge to a class of optimal offline block denoisers.

We study the impact of heterogeneity of channel-state-information available at the transmitters (CSIT) on the capacity of broadcast channels with a multiple-antenna transmitter and k single-antenna receivers (MISO BC). In particular, we consider the k-user MISO BC, where the CSIT with respect to each receiver can be either instantaneous/perfect (P), delayed (D), or not available (N); and we study the impact of this heterogeneity of CSIT on the degrees-of-freedom (DoF) of such network. We develop a general outer bound on the DoF region of k-user MISO BC for all possible heterogeneous CSIT configurations, assuming linear encoding strategies at the transmitter. The outer bound leads to an approximate linear sum-DoF characterization to within 0.5 for a broad range of CSIT configurations. It also leads to an exact characterization of linear sum-DoF for some specific CSIT configurations. Our proof of the outer bound relies on the development of a novel lemma, called Interference Decomposition Bound, which lower bounds the interference dimension at a receiver which supplies delayed CSIT based on the average dimension of constituents of that interference, thereby decomposing it into its components.

The exact-repair problem for distributed storage systems is considered. Characterizing the optimal storage-vs-repair bandwidth tradeoff for such systems remains an open problem for more than four storage nodes. A new family of information theoretic bounds is provided for the storage-vs-repair bandwidth tradeoff for all (n, k, d) systems. The proposed bound readily recovers Tian's result for the (4, 3, 3) system, and hence suffices for exact characterization for this system. In addition, the bound improves upon the existing bounds for the (5, 4, 4) system. More generally, it is shown that this bound characterizes the optimal boundary of the exact repair tradeoff for all distributed storage systems, with (n, k, d) = (n, n-1; n-1) when β ≤ 2α/k.

We consider the two-user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM), in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form P, D and N, corresponding to perfect and instantaneous, completely delayed, and no CSIT, respectively. We focus on the cases with heterogeneous CSIT from the users, that is, the states PD, PN and DN. The main contribution of this paper is to establish the exact secure degrees of freedom (s.d.o.f.) regions of the MISO BCCM in all of these three heterogeneous states. The results highlight the impact of availability of CSIT on the s.d.o.f. region.

Caching is a viable solution for alleviating the severe capacity crunch in modern content centric wireless networks. Parts of popular files are pre-stored in users' cache memories such that at times of heavy demand, users can be served locally from their cache content thereby reducing the peak network load. In this work, we consider a central server assisted caching network where files are jointly delivered to users through multicast transmissions. For such a network, we develop a new information theoretic lower bound on the fundamental cache storage vs. transmission rate tradeoff, which strictly improves upon the best known existing bounds. The new bounds are used to establish the approximate storage vs. rate tradeoff of centralized caching to within a constant multiplicative factor of 8.

Caching is emerging as a vital tool for alleviating the severe capacity crunch in modern content-centric wireless networks. The main idea behind caching is to store parts of the popular content in end-users' memory and leverage the locally stored content to reduce peak data rates. By jointly designing content placement and delivery mechanisms, recent works have shown order-wise reduction in transmission rates in contrast to traditional methods. In this paper, we consider the secure caching problem with the additional goal of minimizing information leakage to an external wiretapper. The fundamental cache memory versus transmission rate tradeoff for the secure caching problem is characterized. Rather surprisingly, these results show that security can be introduced at a negligible cost, particularly for large number of files and users. It is also shown that the rate achieved by the proposed caching scheme with secure delivery is within a constant multiplicative factor from the information-theoretic optimal rate for almost all parameter values of practical interest.

Recent results have shown that feedback can significantly increase the capacity of interference networks. This paper considers the impact of noise on such gains due to feedback. In particular, this paper considers the two-user linear deterministic interference channel with noisy feedback, as a stepping stone to characterize the approximate capacity region for the two-user Gaussian interference channel with noisy feedback. First, the capacity region for the symmetric linear deterministic interference channel with noisy feedback is obtained. It is shown that noisy feedback enlarges the capacity region if and only if the number of feedback bits l is greater than a certain threshold l*. It is found that, excluding the regime (1/2) ≤ α ≤ 2, where α is the normalized interference level, in which even full feedback does not increase symmetric capacity, this threshold l* is equal to the per-user symmetric capacity without feedback. One of the key ideas is a novel converse outer bounding technique for the weighted sum rates 2R1+ R2and R1+ 2R2. These results and the techniques developed for the linear deterministic model are then applied to characterize inner bounds and outer bounds for the symmetric Gaussian interference channel with noisy feedback. The outer bounds are shown to be at most 4.7 b/s/Hz away from the achievable rate region. As a corollary, the generalized-degrees-of-freedom region, which approximates the capacity region of the symmetric Gaussian interference channel at high SNR, is found.

In this paper, the η-Nash equilibrium (η-NE) region of the two-user Gaussian interference channel (IC) with perfect output feedback is approximated to within 1 bit/s/Hz and η arbitrarily close to 1 bit/s/Hz. The relevance of the η-NE region is that it provides the set of rate pairs that are achievable and stable in the IC when both transmitter-receiver pairs autonomously tune their own transmit-receive configurations seeking an η-optimal individual transmission rate. Therefore, any rate tuple outside the η-NE region is not stable as there always exists one link able to increase by at least η bits/s/Hz its own transmission rate by updating its own transmit-receive configuration. The main insights that arise from this paper are as follows. First, the η-NE region achieved with feedback is larger than or equal to the η-NE region without feedback. More importantly, for each rate pair achievable at an η-NE without feedback, there exists at least one rate pair achievable at an η-NE with feedback that is weakly Pareto superior. Second, there always exists an η-NE transmit-receive configuration that achieves a rate pair that is at most 1 bit/s/Hz per user away from the outer bound of the capacity region.

This paper proposes an interference alignment method with distributed and delayed channel state information at the transmitter (CSIT) for a class of interference networks. The core idea of the proposed method is to align interference signals over time at the unintended receivers in a distributed manner. With the proposed method, achievable tradeoffs between the sum of degrees of freedom (sum-DoF) and feedback delay of CSI are characterized in both the X-channel and three-user interference channel to reveal the impact on how the CSI feedback delay affects the sum-DoF of the interference networks. A major implication of derived results is that distributed and moderately delayed CSIT is useful to strictly improve the sum-DoF over the case of no CSI at the transmitter in a certain class of interference networks. For a class of X-channels, the results show how to optimally use distributed and moderately delayed CSIT to yield the same sum-DoF as instantaneous and global CSIT. Furthermore, leveraging the proposed transmission method and the known outer bound results, the sum-capacity of the two-user X-channel with a particular set of channel coefficients is characterized within a constant number of bits.

Multi-tenant distributed storage systems (DSS) exhibit heterogeneity in several dimensions such as fault tolerance requirements, nature of job requests etc. However the primary focus in literature has been on homogenous models for DSS. In this paper, we investigate the impact of heterogeneity on the latency performance of multi-tenant distributed storage systems. Heterogeneity across multiple tenants is modeled via potentially different fault tolerance requirements and different job arrival rates. We consider a heterogeneous multi-tenant DSS with n servers that store the data of R distinct traffic classes. The data of each traffic class i is stored in the DSS using a different (n, fc¿) Maximum-Distance-Separable (MDS) code. Depending upon the traffic class, the data may be frequently or infrequently accessed and is modeled using different job arrival rates for the traffic classes. We then present a queuing theoretic analysis of the proposed model and establish upper and lower bounds on the average latency for each traffic class for various scheduling policies. Using simulations, we verify the accuracy of the derived bounds and present qualitative insights on the impact of heterogeneity and scheduling policies on the mean latency of different classes.

Distributed storage systems (DSS) in the presence of a passive eavesdropper are considered in this paper. A typical DSS is characterized by 3 parameters (n, k, d) where, a file is stored in a distributed manner across n nodes and can be recovered entirely from any k out of n nodes. Whenever a node fails, d ∈ [k, n) nodes help in repairing the failed node. The focus of this work is on the exact repair capabilities of a DSS, where a failed node is replaced with an identical node. Securing this DSS from passive eavesdropping attacks is studied in this paper. The eavesdropper is capable of wiretapping the repair process of a subset of nodes in the storage system. The main contribution of this paper is the optimal characterization of the secure storage-vs-exact-repair-bandwidth tradeoff region which prior to this work was unknown. We focus on the simplest nontrivial instances of this problem, namely (n, k, d) = (3, 2, 2) and (4, 3, 3), and present novel information-theoretic converse proofs that validate these optimal tradeoff regions.

The 3-user multiple-input single-output (MISO) broadcast channel (BC) with hybrid channel state information at the transmitter (CSIT) is considered. In this framework, there is perfect and instantaneous CSIT from a subset of users and delayed CSIT from the remaining users. We present new results on the sum degrees of freedom (DoF) of the 3-user MISO BC with hybrid CSIT. In particular, for the case of 2 transmit antennas, we show that with perfect CSIT from one user and delayed CSIT from the remaining two users, the optimal sum DoF is 5/3. For the case of 3 transmit antennas and the same hybrid CSIT setting, it is shown that a higher sum DoF of 9/5 is achievable and this result improves upon the best known bound. Furthermore, with 3 transmit antennas, and the hybrid CSIT setting in which there is perfect CSIT from two users and delayed CSIT from the third one, a novel scheme is presented which achieves 9/4 sum DoF. Our results also reveal new insights on how to utilize hybrid channel knowledge for multi-user scenarios.

We study the two-user multiple-input single-output (MISO) broadcast channel with confidential messages under the assumption of alternating channel state information at the transmitter (CSIT). We consider two alternating states: PD and DP which occur for an equal fraction of time. In state PD, the CSIT of the channel to the first receiver is available perfectly without delay (P) while that of the second receiver is available with a delay of one channel use (D); in state DP, the roles of the receivers are reversed. We characterize the exact secure degrees of freedom (s.d.o.f.) region of this system, and show as a corollary that the sum s.d.o.f. is 3/2. We observe that this sum s.d.o.f. is the same as what can be achieved by the states PP and DD occurring for equal fraction of time. Though the s.d.o.f. of the system in the states PD and DP is not known individually, we are able to establish the s.d.o.f. region when the two states alternate and occur for an equal fraction of the time.

In this paper, all the rate-pairs that are achievable at a Nash equilibrium (NE) in the two-user linear deterministic symmetric decentralized interference channel (LD-S-DIC) with noisy feedback are identified. More specifically, the Nash region (NR) of the LD-S-DIC with noisy feedback is fully characterized. The relevance of these rate-pairs is that once they are achieved by using NE transmit-receive configurations, none of the transmitter-receiver pairs can increase their individual rates by unilaterally changing their configurations. More importantly, it is shown that the NR of the LD-S-DIC with noisy feedback is larger than the NR of the LD-S-DIC without feedback only in certain cases. When interference is stronger than the desired signals, a larger NR is observed only if the signal to noise ratios (SNRs) of the feedback links are higher than the SNRs of the direct links. Conversely, when desired signals are stronger than interference, a larger NR is observed only if the SNRs of the feedback links are higher than both the signal to interference ratios (SIRs) and the interference to noise ratios (INRs) of the direct links. Previous results, namely the NE region of the two-user LD-S-DIC without feedback and with perfect output feedback are obtained as special cases of the results presented in this contribution.

Caching has emerged as a vital tool in modern communication systems for reducing peak data rates by allowing popular fles to be pre-fetched and stored locally at end users' devices. In this paper, the concept of information theoretic security for content delivery with decentralized caching is introduced. The proposed secure caching scheme allows users to cache content in a decentralized manner and reduces the peak rate by leveraging local and global caching gains, while securely delivering requested content to the users. The analysis of the secure decentralized caching problem is presented which shows that the proposed scheme introduces security at a negligible cost in terms of achievable rate when compared to insecure decentralized caching schemes, particularly for large number of fles and users. It is also shown that the rate of the proposed secure scheme is within a constant multiplicative factor from the information theoretic optimal rate for feasible values of problem parameters.

The multiple-input single-output (MISO) wiretap channel with K legitimate single-antenna receivers, one single-antenna eavesdropper in presence of delayed channel state information at the transmitter (CSIT) is considered. The transmitter is equipped with (K+1) antennas and has independent messages intended for each one of the K legitimate receivers. While for the case of a single receiver wiretap channel, i.e., K = 1, the optimal secure degrees of freedom (SDoF) with delayed CSIT was recently characterized in [1] and shown to be 2/3, the extension to the multi-receiver case (K > 1) is far from straightforward. We present new results and insights for the simplest non-trivial extension of this problem, i.e., for the case of K = 2 receiver MISO wiretap channel with delayed CSIT. The contribution of this paper is two fold: a) an asymptotic achievable scheme is presented for the case of two legitimate receivers which achieves a sum-SDoF of 36/37 and b) a novel converse proof is presented which shows that the sum-SDoF is upper bounded by 16/15.

Jamming attacks can significantly impact the performance of wireless communication systems. In addition to reducing the capacity, such attacks may lead to insurmountable overhead in terms of retransmissions and increased power consumption. In this paper, we consider the multiple-input single-output (MISO) broadcast channel (BC) in the presence of a jamming attack in which a subset of the receivers can be jammed at any given time. Further, countermeasures for mitigating the effects of such jamming attacks are presented. The effectiveness of these antijamming countermeasures is quantified in terms of the degrees-of-freedom (DoF) of the MISO BC under various assumptions regarding the availability of the channel state information (CSIT) and the jammer state information at the transmitter (JSIT). The main contribution of this paper is the characterization of the DoF region of the two user MISO BC under various assumptions on the availability of CSIT and JSIT. Partial extensions to the multiuser broadcast channels are also presented.

Jamming attacks can significantly impact the performance of wireless communication systems, and lead to insurmountable overhead in terms of re-transmissions and increased power consumption. In this paper, we consider the multi-user multiple-input single-output (MISO) broadcast channel (BC) in the presence of jamming attacks in which a subset of the users can be selectively jammed at any given time. We present countermeasures for mitigating the effects of such jamming attacks. The effectiveness of these anti-jamming countermeasures is quantified in terms of the degrees-of-freedom (DoF) of the MISO BC under various assumptions regarding the availability of the channel state information (CSIT) and the jammer state information at the transmitter (JSIT).

The degrees of freedom (DoF) of the two-user multiple-input single-output (MISO) broadcast channel (BC) are studied under the assumption that the form, Ii, i = 1, 2, of the channel state information at the transmitter (CSIT) for each user's channel can be either perfect (P), delayed (D) or not available (N), i.e., I1, I2ϵ {P, N, D}, and therefore the overall CSIT can alternate between the 9 resulting states I1I2. The fraction of time associated with CSIT state I1I2is denoted by the parameter λI1I2and it is assumed throughout that λI1I2= λI2I1, i.e., λPN= λNP, λPD= λDP, λDN= λND. Under this assumption of symmetry, the main contribution of this paper is a complete characterization of the DoF region of the two user MISO BC with alternating CSIT. The results highlight the synergistic benefits of alternating CSIT and the tradeoffs between various forms of CSIT for any given DoF value.

In lossy source coding with side information at the decoder (i.e., the Wyner–Ziv problem), the estimate of the source obtained at the decoder cannot be generally reproduced at the encoder, due to its dependence on the side information. In some applications, this may be undesirable, and a common reconstruction (CR) requirement, whereby one imposes that the encoder and decoder be able to agree on the decoder's estimate, may be instead in order. The rate-distortion function under the CR constraint has been derived recently for a point-to-point (Wyner–Ziv) problem. In this paper, this result is extended to three multiterminal settings with three nodes, namely the Heegard–Berger (HB) problem, its variant with cooperating decoders, and the cascade source coding problem. The HB problem consists of an encoder broadcasting to two decoders with respective side information. The cascade source coding problem is characterized by a two-hop system with side information available at the intermediate and final nodes. For the HB problem with the CR constraint, the rate-distortion function is derived under the assumption that the side information sequences are (stochastically) degraded. The rate-distortion function is also calculated explicitly for three examples, namely Gaussian source and side information with quadratic distortion metric, and binary source and side information with erasure and Hamming distortion metrics. The rate-distortion function is then characterized for the HB problem with cooperating decoders and (physically) degraded side information. For the cascade problem with the CR constraint, the rate-distortion region is obtained under the assumption that side information at the final node is physically degraded with respect to that at the intermediate node. For the latter two cases, it is worth emphasizing that the corresponding problem without the CR constraint is still open. Outer and inner bounds on the rate-distortion region are also obtained for the cascade problem under the assumption that the side information at the intermediate node is physically degraded with respect to that at the final node. For the three examples mentioned above, the bounds are shown to coincide. Finally, for the HB problem, the rate-distortion function is obtained under the more general requirement of constrained reconstruction, whereby the decoder's estimate must be recovered at the encoder only within some distortion.

The symmetricK-user interference channel with fully connected topology is considered, in which 1) each receiver suffers interference from all other (K-1) transmitters, and 2) each transmitter has causal and noiseless feedback from its respective receiver. The number of generalized degrees of freedom (\ssrGDoF) is characterized in terms of α, where the interference-to-noise ratio (\ssrINR) is given by \ssrINR= \ssrSNRα. It is shown that the per-user \ssrGDoFof this network is the same as that of the two-user interference channel with feedback, except for α = 1, for which existence of feedback does not help in terms of \ssrGDoF. The coding scheme proposed for this network, termed cooperative interference alignment, is based on two key ingredients, namely, interference alignment and interference decoding. Moreover, an approximate characterization is provided for the symmetric feedback capacity of the network, when the \ssrSNRand \ssrINRare far apart from each other.

The degrees of freedom (DoFs) of the two-user multiple-input single-output (MISO) broadcast channel (BC) are studied under the assumption that the form,$I_{i},\;i=1, 2$, of the channel state information at the transmitter (CSIT) for each user's channel can be either perfect$(P)$, delayed$(D)$, or not available$(N)$, i.e.,$I_{1},I_{2} \in \{P,N,D\}$, and therefore, the overall CSIT can alternate between the nine resulting states$I_{1}I_{2}$. The fraction of time associated with CSIT state$I_{1}I_{2}$is denoted by the parameter$\lambda_{I_{1}I_{2}}$and it is assumed throughout that$\lambda_{I_{1}I_{2}} = \lambda_{I_{2}I_{1}}$, i.e.,$\lambda_{PN} = \lambda_{NP}, \lambda_{PD}=\lambda_{DP}, \lambda_{DN}=\lambda_{ND}$. Under this assumption of symmetry, the main contribution of this paper is a complete characterization of the DoF region of the two-user MISO BC with alternating CSIT. Surprisingly, the DoF region is found to depend only on the marginal probabilities$(\lambda_{P}, \lambda_{D},\lambda_{N})=\left(\sum_{I_{2}}\lambda_{PI_{2}},\sum_{I_{2}}\lambda_{DI_{2}}, \sum_{I_{2}}\lambda_{NI_{2}}\right)$,$I_{2} \in \{P,D,N\}$, which represent the fraction of time that any given user (e.g., user 1) is associated with perfect, delayed, or no CSIT, respectively. As a consequence, the DoF region with all nine CSIT states,${\cal {D}}(\lambda_{I_{1}I_{2}}:I_{1},I_{2} \in \{P,D,N\})$, is the same as the DoF region with only three CSIT states${\cal {D}}(\lambda_{PP}, \lambda_{DD}, \lambda_{NN})$, under the same marginal distribution of CSIT states, i.e.,$(\lambda_{PP}, \lambda_{DD},\lambda_{NN})=(\lambda_{P},\lambda_{D},\lambda_{N})$. The sum-DoF value can be expressed as${\rm DoF}=\min \left({{4+2\lambda_{P}} \over {3}}, 1+\lambda_{P}+\lambda_{D}\right)$, from which one can uniquely identify the minimum required marginal CSIT fractions to achieve any target DoF value as$(\lambda_{P},\lambda_{D})_{\min}=\left({{3} \over {2}} {\rm DoF}-2,1- {{1} \over {2}} {\rm DoF}\right)$when${\rm DoF} \in \big [{{4} \over {3}},2\big]$and$(\lambda_{P},\lambda_{D})_{\min}=(0,({\rm DoF}-1)^{+})$when${\rm DoF} \in \big [0, {{4} \over {3}}\big)$. The results highlight the synergistic benefits of alternating CSIT and the tradeoffs between various forms of CSIT for any given DoF value. Partial results are also presented for the multiuser MISO BC with$M$transmit antennas and$K$single antenna users. For this problem, the minimum amount of perfect CSIT required per user to achieve the maximum DoFs of$\min (M,K)$is characterized. By the minimum amount of CSIT per user, we refer to the minimum fraction of time that the transmitter has access to perfect and instantaneous CSIT from a user. Through a novel converse proof and an achievable scheme, it is shown that the minimum fraction of time perfect CSIT is required per user in order to achieve the DoF of$\min (M,K)$is given by$\min (M,K)/K$.

TheK-user cyclic Z-interference channel models a situation in which thekth transmitter causes interference only to the (k-1)th receiver in a cyclic manner, e.g., the first transmitter causes interference only to theKth receiver. The impact of noiseless feedback on the capacity of this channel is studied by focusing on the Gaussian cyclic Z-interference channel. To this end, the symmetric feedback capacity of the linear shift deterministic cyclic Z-interference channel is completely characterized for all interference regimes. Using insights from the linear deterministic channel model, the symmetric feedback capacity of the Gaussian cyclic Z-interference channel is characterized up to within a constant number of bits. As a byproduct of the constant gap result, the symmetric generalized degrees of freedom with feedback for the Gaussian cyclic Z-interference channel are also characterized. These results highlight that the symmetric feedback capacities for both linear and Gaussian channel models are in general functions ofK, the number of users. Furthermore, the capacity gain obtained due to feedback decreases asKincreases.

The two-user multiple-input multiple-output (MIMO) interference channel (IC) with arbitrary numbers of antennas at each terminal is considered and the degrees of freedom (DoF) region is characterized in the presence of noiseless channel output feedback from each receiver to its respective transmitter and availability of delayed channel state information at the transmitters (CSIT). It is shown that having output feedback and delayed CSIT can strictly enlarge the DoF region of the MIMO IC when compared to the case in which only delayed CSIT is present. The proposed coding schemes that achieve the corresponding DoF region with feedback and delayed CSIT utilize both resources, i.e., feedback and delayed CSIT in a nontrivial manner. It is also shown that the DoF region with local feedback and delayed CSIT is equal to the DoF region with global feedback and delayed CSIT, i.e., local feedback and delayed CSIT is equivalent to global feedback and delayed CSIT from the perspective of the DoF region. The converse is proved for a stronger setting in which the channels to the two receivers need not be statistically equivalent.

A lossy source coding problem is studied in which a source encoder communicates with two decoders, one with and one without correlated side information with an additional constraint on the privacy of the side information at the uninformed decoder. Two cases of this problem arise depending on the availability of the side information at the encoder. The set of all feasible rate-distortion-equivocation tuples is characterized for each case. The difference between the informed and uninformed cases and the advantages of encoder side information for enhancing privacy are highlighted for a binary symmetric source with erasure side information and Hamming distortion.

We consider a secure lossless source coding problem with a rate-limited helper. In particular, Alice observes an independent and identically distributed (i.i.d.) sourceXnand wishes to transmit this source losslessly to Bob over a rate-limited link of capacity not exceedingRx. A helper, say Helen, observes an i.i.d. correlated sourceYnand can transmit information to Bob over another link of capacity not exceedingRy. A passive eavesdropper (say Eve) can observe the coded output of Alice, i.e., the link from Alice to Bob is public. The uncertainty about the sourceXnat Eve (denoted by Δ) is measured by the conditional entropy [(H(Xn|Jx))/(n)] , whereJxis the coded output of Alice andnis the block length. We completely characterize the rate-equivocation region for this secure source coding model, where we show that Slepian-Wolf binning ofXnwith respect to the coded side information received at Bob is optimal. We next consider a modification of this model in which Alice also has access to the coded output of Helen. We call this model as the two-sided helper model. For the two-sided helper model, we characterize the rate-equivocation region. While the availability of side information at Alice does not reduce the rate of transmission from Alice, it significantly enhances the resulting equivocation at Eve. In particular, the resulting equivocation for the two-sided helper case is shown to be min(H(X),Ry), i.e., one bit from the two-sided helper provides one bit of uncertainty at Eve. From this result, we infer that Slepian-Wolf binning ofXis suboptimal and one can further decrease the information leakage to the eavesdropper by utilizing the side information at Alice. We, finally, generalize both of these results to the case in which there is additional uncoded side informationWnavailable at Bob and characterize the rate-equivocation regions under the assumption thatYn→Xn→Wnforms a Markov chain.

The degrees of freedom (DoF) region of the two-user MIMO interference channel (IC) is completely characterized in the presence of noiseless channel output feedback from each receiver to its respective transmitter and with the assumption of delayed channel state information (CSI) at the transmitters. It is shown that having output feedback and delayed CSI at the transmitters can strictly enlarge the DoF region when compared to the case in which only delayed CSI is available at the transmitters. Furthermore, cases are identified in which output feedback and delayed CSI alone are sufficient to achieve the DoF region achievable with perfect, instantaneous CSI.

In lossy source coding with side information at the decoder (i.e., the Wyner-Ziv problem), the estimate of the source obtained at the decoder cannot be generally reproduced at the encoder, due to its dependence on the side information. In some applications this may be undesirable, and a Common Reconstruction (CR) requirement, whereby one imposes that encoder and decoder be able to agree on the decoder's estimate, may be instead in order. The rate-distortion function under the CR constraint has been recently derived for the point-to-point (Wyner-Ziv) problem. In this paper, this result is extended to the Heegard-Berger (HB) problem and to its variant with cooperating decoders. Specifically, for the HB problem, the ratedistortion function is derived under the assumption that the side information sequences at the two decoders are stochastically degraded. The rate-distortion function is also calculated explicitly for the special case of binary source and erased side information with Hamming distortion metric. The rate-distortion function is then characterized also for the HB problem with cooperating decoders and physically degraded side information.

The linear deterministic interference channel (LD-IC) with partial feedback is considered. Partial feedback for the LD-IC models a scenario in which the top l most-significant-bits of the channel output of receiver j are received as feedback at transmitter j, for j = 1, 2. The rationale for studying the LD-IC with partial feedback comes from the fact that it is a good approximation to the Gaussian interference channel with output feedback corrupted by additive white Gaussian noise (commonly referred to as noisy feedback). The main contribution of this paper is a characterization of the sum-capacity of the symmetric LD-IC with partial feedback. The differences between the models of partial feedback and rate-limited feedback are emphasized and highlighted by comparing the corresponding sum-capacities, which are shown to differ in general.

The symmetric K user interference channel with fully connected topology is considered, in which (a) each receiver suffers interference from all other K - 1 transmitters, and (b) each transmitter has causal and noiseless feedback from its respective receiver. The number of generalized degrees of freedom (GDoF) is characterized in terms of α, where the interference-to-noise ratio (INR) is given by INR = SNRα. It is shown that the number of per-user GDoF of this network is the same as that of the 2-user interference channel with feedback, except for α = 1, for which existence of feedback does not help in terms of GDoF. The coding scheme proposed for this network, termed cooperative interference alignment, is based on two key ingredients, namely, interference alignment and interference decoding.

The problem of multiple descriptions for a Gaussian source is considered, in which all the decoders have access to correlated Gaussian side-information. Two variations of this problem are studied. First, the rate-distortion tradeoff is characterized under the assumption of a common reconstruction constraint, in which the estimate produced at each of the decoders is also exactly recoverable at the encoder. Secondly, a generalization of this setup is studied in which possibly different distortions are tolerable between the estimates at the encoder and the respective estimates at each of the decoders.

The sum degrees of freedom (DoF) of the two-user MIMO X-channel is characterized in the presence of output feedback and delayed channel state information (CSI). The number of antennas at each transmitters is assumed to be M and the number of antennas at each of the receivers is assumed to be N. It is shown that the sum DoF of the two-user MIMO X-channel is the same as the sum DoF of a two-user MIMO broadcast channel with 2M transmit antennas, and N antennas at each receiver. Hence, for this symmetric antenna configuration, there is no performance loss in the sum degrees of freedom due to the distributed nature of the transmitters. This result highlights the usefulness of feedback and delayed CSI for the MIMO X-channel. The K-user X-channel with a single antenna at each transmitter and each receiver is also studied. In this network, each transmitter has a message intended for each receiver. For this network, it is shown that the sum DoF with partial output feedback alone is at least 2K/(K + 1). This lower bound is strictly better than the best lower bound known for the case of delayed CSI assumption for all values of K.

The Heegard-Berger problem models a case in which encoding at a source has to account for two decoders, one with and one without correlated side information when the same information is not available at the encoder. The Heegard-Berger encoding scheme is proved to be rate-optimal even when an additional constraint on the privacy of side information is imposed at the uninformed decoder. The results are illustrated for a binary source with erasure side information and Hamming distortion, a result which is also of independent interest.

This paper considers distributed detection over a noisy network, in which each connected sensor pair can communicate over an additive noise channel. With non-identically distributed generic sensor observations, a mixed time scale recursive algorithm for binary hypothesis testing over such networks is proposed. Under some mild assumptions on network connectivity and global detectability (the positivity of the global or centralized Kullback-Liebler divergence), this algorithm yields asymptotically zero probabilities of Type-I and Type-II errors (henceforth referred to as probabilities of error). When sensor observations are identically distributed, a simplified single time scale version of the proposed algorithm is shown to achieve asymptotically zero probabilities of error. Convergence rate guarantees in terms of asymptotic normality of certain scaled decision variables are provided for this simplified procedure. As an example, a practical Gaussian sensor network is considered, for which the error decay exponents are explicitly characterized in terms of the network and noise parameters.

A cascade lossy source coding problem with one encoder and two decoders is considered. All variations of this problem are studied by varying the availability of correlated side information at the encoder/decoder(s). The set of achievable rate-distortion triples is characterized for three instances of this problem when the encoder is interested in transmission of a memoryless equiprobable binary source X subject to Hamming distortion and the side information Y is an erased version of X.

The problem of preserving privacy when a multi-variate source is required to be revealed partially to multiple users is modeled as a Gray-Wyner source coding problem with K correlated sources at the encoder and K decoders in which the kthdecoder, k = 1, 2, ..., K, losslessly reconstructs the kthsource via a common link of rate R0and a private link of rate Rk. The privacy requirement of keeping each decoder oblivious of all sources other than the one intended for it is introduced via an equivocation constraint Ekat decoder k such that the total equivocation summed over all decoders E ≥ Δ. The set of achievable ({Rk}Kk=1,R0,Δ) rates-equivocation (K + 2)-tuples is completely characterized. Using this characterization, two different definitions of common information are presented and are shown to be equivalent.

We obtain new outer bounds on the capacity regions of the two-user multiple access channel with generalized feedback (MAC-GF) and the two-user interference channel with generalized feedback (IC-GF). These outer bounds are based on the idea of dependence balance which was proposed by Hekstra and Willems. To illustrate the usefulness of our outer bounds, we investigate three different channel models.

We consider diamond channels with a general broadcast channel p(y, z|x), with outputs Z and Y at relays 1 and 2, respectively, and where the relays 1 and 2 have noiseless links of capacities Rzand Ry, respectively, to the decoder. For the case when Y and Z are deterministic functions of X, we establish the capacity. We next give an upper bound for the capacity of the class of diamond channels with a physically degraded broadcast channel, i.e., when X → Y → Z forms a Markov chain. We show that this upper bound is tight, if in addition to X → Y → Z, the output of relay 2, i.e., Y, is a deterministic function of X. We finally consider the diamond channel with partially separated relays, i.e., when the output of relay 2 is available at relay 1. We establish the capacity for this model in two cases, a) when the broadcast channel is physically degraded, i.e., when X → Y → Z forms a Markov chain, and b) when the broadcast channel is semi-deterministic, i.e, when Y = f(X). For both of these cases, we show that the capacity is equal to the cut-set bound. This final result shows that even partial feedback from the decoder to relays strictly increases the capacity of the diamond channel.

We provide a new outer bound on the capacity region of the two-user Gaussian multiple access channel (MAC) with AWGN-corrupted feedback. Our outer bound is based on the idea of dependence balance due to Hekstra and Willems. Evaluating our outer bound is non-trivial as it involves taking a union over joint densities of three random variables, one of which is an auxiliary random variable. We resolve this difficulty by proving that it is sufficient to consider jointly Gaussian random variables when evaluating our outer bound. As the feedback noise variances become large, our outer bound collapses to the capacity region of the Gaussian MAC without feedback, thereby yielding the first non-trivial result for a Gaussian MAC with noisy feedback. Furthermore, as the feedback noise variances tend to zero, our outer bound collapses to the capacity region of the Gaussian MAC with noiseless feedback, which was established by Ozarow. For all non-zero, finite values of the feedback noise variances, our outer bound strictly improves upon the cutset outer bound.

We obtain a dependence balance based outer bound on the capacity region of the two-user multiple access channel with generalized feedback (MAC-GF). We investigate a Gaussian MAC with user-cooperation (MAC-UC), where each transmitter receives an additive white Gaussian noise corrupted version of the channel input of the other transmitter. For all non-zero values of cooperation noise variances, our outer bound strictly improves upon the cut-set outer bound. Moreover, as the variances of the cooperation noises become large, our outer bound collapses to the capacity region of the Gaussian MAC without cooperation.

We study a rate-limited version of the well known problem of coding for channels with random parameters which was studied by Gelfand and Pinsker [1]. In particular, we consider a state-dependent channel when the transmitter is supplied with the state information at a rate Re. We obtain a new upper bound on the capacity, C(Re), for this channel. We explicitly evaluate this upper bound for the rate-limited dirty paper coding (DPC) problem and show that it strictly improves upon the DPC capacity for certain values of Re.

We obtain a new outer bound on the capacity region of the two-user interference channel with generalized feedback (IC-GF). This outer bound is based on the idea of dependence balance which was proposed by Hekstra and Willems. We explicitly evaluate our outer bound for the Gaussian IC with user-cooperation (IC-UC), where each transmitter receives an additive white Gaussian noise corrupted version of the channel input of the other transmitter. We show that for all non-zero values of cooperation noise variances, our outer bound strictly improves upon the cut-set outer bound.

We use the idea of dependence balance to obtain a new outer bound for the capacity region of the discrete memoryless multiple-access channel with noiseless feedback (MAC-FB). We consider a binary additive noisy MAC-FB whose feedback capacity is not known. The binary additive noisy MAC considered in this paper can be viewed as the discrete counterpart of the Gaussian MAC-FB. Ozarow established that the capacity region of the two-user Gaussian MAC-FB is given by the cut-set bound. Our result shows that for the discrete version of the channel considered by Ozarow, this is not the case. Direct evaluation of our outer bound is intractable due to an involved auxiliary random variable whose large cardinality prohibits an exhaustive search. We overcome this difficulty by using a composite function and its properties to explicitly evaluate our outer bound. Our outer bound is strictly less than the cut-set bound at all points on the capacity region where feedback increases capacity. In addition, we explicitly evaluate the Cover-Leung achievable rate region for the binary additive noisy MAC-FB in consideration. Furthermore, using the tools developed for the evaluation of our outer bound, we also explicitly characterize the boundary of the feedback capacity region of the binary erasure MAC, for which the Cover-Leung achievable rate region is known to be tight. This last result confirms that the feedback strategies developed by Kramer for the binary erasure MAC are capacity achieving.

We use the idea of dependence balance to obtain the first improvement over the cut-set bound for the discrete memoryless multiple access channel with noiseless feedback (MAC-FB). More specifically, we consider a binary additive noisy MAC-FB whose capacity does not coincide with the Cover-Leung achievable rate region. Evaluating the dependence balance bound is difficult due to an involved auxiliary random variable. We overcome this difficulty by using functional analysis to explicitly evaluate our upper bound for the binary additive noisy MAC-FB and show that it is strictly less than the cut-set bound for the symmetric-rate point on the capacity region.