Statistical heterogeneity of clients’ local data is an important characteristic in federated learning, motivating personalized algorithms tailored to local data statistics. Though there has been a plethora of algorithms proposed for personalized supervised learning, discovering the structure of local data through personalized unsupervised learning is less explored. We initiate a systematic study of such personalized unsupervised learning by developing algorithms based on optimization criteria inspired by a hierarchical Bayesian statistical framework. We develop adaptive algorithms that discover the balance between using limited local data and collaborative information. We do this in the context of two unsupervised learning tasks: personalized dimensionality reduction (ADEPT-PCA and ADEPT-AE) and personalized diffusion models (ADEPT-DGM). We develop convergence analyses for our adaptive algorithms which illustrate the dependence on problem parameters (e.g., heterogeneity, local sample size). We also develop a theoretical framework for personalized diffusion models, which shows the benefits of collaboration even under heterogeneity. We finally evaluate our proposed algorithms using synthetic and real data, demonstrating the effective sample amplification for personalized tasks, induced through collaboration, despite data heterogeneity.

Quantifying the common information between continuous random sources is fundamental to various applications in machine learning and information theory. Recent work introduced the notion of common information dimension (CID) to measure this. In this paper, we propose a new notion, discrete-to-continuous common information dimension (D2CCID), which characterizes the growth rate of the common information between successively finer quantized sources. As compared to existing CID notions, the proposed notion can be easier to approximate, and is well aligned with common practice in information theory to measure information dimensions. We prove that the proposed measure coincides with existing CID measures for two Gaussian random sources.

Federated learning with heterogeneous data and personalization has received significant recent attention. Separately, robustness to corrupted data in the context of federated learning has also been studied. In this paper we explore combining personalization for heterogeneous data with robustness, where a constant fraction of the clients are corrupted. Motivated by this broad problem, we formulate a simple instantiation which captures some of its difficulty. We focus on the specific problem of personalized mean estimation where the data is drawn from a Gaussian mixture model. We give an algorithm whose error depends almost linearly on the ratio of corrupted to uncorrupted samples, and show a lower bound with the same behavior, albeit with a gap of a constant factor.

We study personalized heterogeneous mean estimation under user-level local differential privacy (LDP), which protects the privacy of local datasets with multiple samples. We consider a distributed environment with$n$users, each associated with one of$k$clusters. Our goal is to estimate the mean of each cluster while preserving the privacy of users' local datasets. Focusing on the scalar case, we propose algorithms that handle scenarios with (unknown) equal and unequal variance proxies (spans of the clusters), and even the number of clusters. Our methods identify the clusters via private frequency estimation and subsequently perform private mean estimation for each cluster. Theoretical guarantees on the trade-off between user-level local differential privacy guarantees and performance are provided.

Standard multimodal self-supervised learning (SSL) algorithms regard cross-modal synchronization as implicit supervisory labels during pretraining, thus posing high requirements on the scale and quality of multimodal samples. These constraints significantly limit the performance of sensing intelligence in IoT applications, as the heterogeneity and the non-interpretability of time-series signals result in abundant unimodal data but scarce high-quality multimodal pairs. This paper proposes InfoMAE, a cross-modal alignment framework that tackles the challenge of multimodal pair efficiency under the SSL setting by facilitating efficient cross-modal alignment of pretrained unimodal representations. InfoMAE achieves efficient cross-modal alignment with limited data pairs through a novel information theory-inspired formulation that simultaneously addresses distribution-level and instance-level alignment. Extensive experiments on two real-world IoT applications are performed to evaluate InfoMAE's pairing efficiency to bridge pretrained unimodal models into a cohesive joint multimodal model. InfoMAE enhances downstream multimodal tasks by over 60% with significantly improved multimodal pairing efficiency. It also improves unimodal task accuracy by an average of 22%.

Quantifying the common information between random variables is a fundamental problem with a long history in information theory. Traditionally, common information is measured in number of bits and thus such measures are mostly informative when the common information is finite. However, the common information between continuous variables can be infinite; in such cases, a real-valued random vectorWmay be needed to represent the common information, and to be used for instance for distributed simulation. In this paper, we propose the concept of Common Information Dimension (CID) and three variants. We compute the common information dimension for jointly Gaussian random vectors in a closed form. Moreover, we analytically prove, under two different formulations, that the growth rate of common information in the nearly infinite regime is determined by the common information dimension, for the case of two Gaussian vectors.

In this paper, we are interested in the regime where the common information between two Gaussian random vectors$(X, Y)$can be (or can approach) infinity. We ask two main questions: what is the rate of growth for common information from a finite to an infinite number of bits, as the dependency between the variables increases? and how well can we “approximately” simulate a pair of random variables$(X, Y)$with infinite common information using a finite number of shared bits? We analytically prove that the answer to both of these questions depends on the common information dimension$d(X, Y)$between$X$and$Y$, that we introduced in our recent work [1]. Our work characterizes in a closed form the asymptotic behaviors, by building a connection to singular values associated with the covariance matrix$\Sigma$of$(X, Y)$. We conclude the paper by providing numerical evaluation results that indicate fast convergence to the asymptotic regime.

We consider personalized estimation for heterogeneous data under communication constraints. In many applications, distributed users have heterogeneous local data with distinct statistics, and want to estimate individual (personalized) properties of the local data. However, they have limited local data and we explore how collaboration (even over communication-limited links) can enable better personalized estimation. We study this for the Gaussian Bayesian model for heterogeneity with unknown parameters and a worst-case total regret criterion. We characterize (order-wise) the worst-case regret for personalized mean estimation by devising novel lower bounds and achievability schemes, which also demonstrates the value of collaboration.

The exact common information between a set of random variables X1,…, Xnis defined as the minimum entropy of a shared random variable that allows for the exact distributive simulation of X1,…, Xn. It has been established that, in certain instances, infinite entropy is required to achieve distributive simulation, suggesting that continuous random variables may be needed in such scenarios. However, to date, there is no established metric to characterize such cases. In this paper, we propose the concept of Common Information Dimension (CID) with respect to a given class of functions ℱ, defined as the minimum dimension of a random variable W required to distributively simulate a set of random variables X1,…, Xn, such that W can be expressed as a function of X1,⋯, Xnusing a member of ℱ. Our main contributions include the computation of the common information dimension for jointly Gaussian random vectors in a closed form, with ℱ being the linear functions class.

As the high dimensional data generation/storage shifts from data centers to millions of edge devices, PCA algorithms also need to adapt to federated systems to reveal insights about the distributed data. One of the prominent challenges in Federated Learning (FL) is that each edge device has a limited number of samples, and therefore collaboration among clients is necessary for learning tasks. Another challenge is heterogeneous distribution of data across devices, which necessitates careful design of algorithms that enable collaboration of devices with different data distributions. While many such federated supervised learning algorithms were proposed in recent years, heterogeneity for unsupervised FL algorithms (such as PCA) has received less attention. In this work, our goal is to enable collaborations of heterogeneous clients in learning personalized Principal Components (PCs). To this end, we develop a hierarchical Bayesian framework for discovering individual PCs; and inspired by this, we formulate an optimization problem related to maximum likelihood estimation of the PCs. To solve the optimization problem, we propose an alternating Stiefel gradient descent algorithm. Analytically, we prove the convergence result for our proposed algorithm; and empirically, we show that our method outperforms local and global estimation of PCs in various heterogeneous settings in terms of the reconstruction error.

In this paper, we consider the problem of learning a linear regression model on a data domain of interest (target) given few samples. To aid learning, we are provided with a set of pre-trained regression models that are trained on potentially different data domains (sources). Assuming a representation structure for the data generating linear models at the sources and the target domains, we propose a representation transfer based learning method for constructing the target model. The proposed scheme is comprised of two phases: (i) utilizing the different source representations to construct a representation that is adapted to the target data, and (ii) using the obtained model as an initialization to a fine-tuning procedure that re-trains the entire (over-parameterized) regression model on the target data. For each phase of the training method, we provide excess risk bounds for the learned model compared to the true data generating target model. The derived bounds show a gain in sample complexity for our proposed method compared to the baseline method of not leveraging source representations when achieving the same excess risk, therefore, theoretically demonstrating the effectiveness of transfer learning for linear regression.

This paper proposes a novel contrastive learning framework, called FOCAL, for extracting comprehensive features from multimodal time-series sensing signals through self-supervised training. Existing multimodal contrastive frameworks mostly rely on the shared information between sensory modalities, but do not explicitly consider the exclusive modality information that could be critical to understanding the underlying sensing physics. Besides, contrastive frameworks for time series have not handled the temporal information locality appropriately. FOCAL solves these challenges by making the following contributions: First, given multimodal time series, it encodes each modality into a factorized latent space consisting of shared features and private features that are orthogonal to each other. The shared space emphasizes feature patterns consistent across sensory modalities through a modal-matching objective. In contrast, the private space extracts modality-exclusive information through a transformation-invariant objective. Second, we propose a temporal structural constraint for modality features, such that the average distance between temporally neighboring samples is no larger than that of temporally distant samples. Extensive evaluations are performed on four multimodal sensing datasets with two backbone encoders and two classifiers to demonstrate the superiority of FOCAL. It consistently outperforms the state-of-the-art baselines in downstream tasks with a clear margin, under different ratios of available labels. The code and self-collected dataset are available at https://github.com/tomoyoshki/focal.

MOTIVATION: Detection of structural variants (SVs) from the alignment of sample DNA reads to the reference genome is an important problem in understanding human diseases. Long reads that can span repeat regions, along with an accurate alignment of these long reads play an important role in identifying novel SVs. Long-read sequencers, such as nanopore sequencing, can address this problem by providing very long reads but with high error rates, making accurate alignment challenging. Many errors induced by nanopore sequencing have a bias because of the physics of the sequencing process and proper utilization of these error characteristics can play an important role in designing a robust aligner for SV detection problems. In this article, we design and evaluate HQAlign, an aligner for SV detection using nanopore sequenced reads. The key ideas of HQAlign include (i) using base-called nanopore reads along with the nanopore physics to improve alignments for SVs, (ii) incorporating SV-specific changes to the alignment pipeline, and (iii) adapting these into existing state-of-the-art long-read aligner pipeline, minimap2 (v2.24), for efficient alignments. RESULTS: We show that HQAlign captures about 4%-6% complementary SVs across different datasets, which are missed by minimap2 alignments while having a standalone performance at par with minimap2 for real nanopore reads data. For the common SV calls between HQAlign and minimap2, HQAlign improves the start and the end breakpoint accuracy by about 10%-50% for SVs across different datasets. Moreover, HQAlign improves the alignment rate to 89.35% from minimap2 85.64% for nanopore reads alignment to recent telomere-to-telomere CHM13 assembly, and it improves to 86.65% from 83.48% for nanopore reads alignment to GRCh37 human genome. AVAILABILITY AND IMPLEMENTATION: https://github.com/joshidhaivat/HQAlign.git.

Distributed machine learning is envisioned as the bedrock of future intelligent networks, where agents exchange information with each other to train models collaboratively without uploading data to a central processor. Despite its broad applicability, a downside of distributed learning is the need for iterative information exchange between agents, which may lead to high communication overhead unaffordable in many practical systems with limited communication resources. To resolve this communication bottleneck, we need to devise communication-efficient distributed learning algorithms and protocols that can reduce the communication cost and simultaneously achieve satisfactory learning/optimization performance. Accomplishing this goal necessitates synergistic techniques from a diverse set of fields, including optimization, machine learning, wireless communications, game theory, and network/graph theory. This Special Issue is dedicated to communication-efficient distributed learning from multiple perspectives, including fundamental theories, algorithm design and analysis, and practical considerations.

Distributed learning is envisioned as the bedrock of next-generation intelligent networks, where intelligent agents, such as mobile devices, robots, and sensors, exchange information with each other or a parameter server to train machine learning models collaboratively without uploading raw data to a central entity for centralized processing. By utilizing the computation/communication capability of individual agents, the distributed learning paradigm can mitigate the burden at central processors and help preserve data privacy of users. Despite its promising applications, a downside of distributed learning is its need for iterative information exchange over wireless channels, which may lead to high communication overhead unaffordable in many practical systems with limited radio resources such as energy and bandwidth. To overcome this communication bottleneck, there is an urgent need for the development of communication-efficient distributed learning algorithms capable of reducing the communication cost and achieving satisfactory learning/optimization performance simultaneously. In this paper, we present a comprehensive survey of prevailing methodologies for communication-efficient distributed learning, including reduction of the number of communications, compression and quantization of the exchanged information, radio resource management for efficient learning, and game-theoretic mechanisms incentivizing user participation. We also point out potential directions for future research to further enhance the communication efficiency of distributed learning in various scenarios.

We study stochastic gradient descent (SGD) with local iterations in the presence of Byzantine clients, motivated by federated learning. The clients, instead of communicating with the server in every iteration, maintain their local models, which they update by taking several SGD iterations based on their own datasets and then communicate the net update with the server, thereby achieving communication efficiency. Furthermore, only a subset of clients communicates with the server at synchronization times. The Byzantine clients may collude and send arbitrary vectors to the server to disrupt the learning process. To combat the adversary, we employ an efficient high-dimensional robust mean estimation algorithm at the server to filter-out corrupt vectors; and to analyze the outlier-filtering procedure, we develop a novel matrix concentration result that may be of independent interest. We provide convergence analyses for both strongly-convex and non-convex smooth objectives in the heterogeneous data setting. We believe that ours is the first Byzantine-resilient local SGD algorithm and analysis with non-trivial guarantees. We corroborate our theoretical results with experiments for neural network training.

Group testing is a technique that can reduce the number of tests needed to identify infected members in a population, by pooling together multiple diagnostic samples. Despite the variety and importance of prior results, traditional work on group testing has typically assumed independent infections. However, contagious diseases among humans, like SARS-CoV-2, have an important characteristic: infections are governed by community spread, and are therefore correlated. In this paper, we explore this observation and we argue that taking into account the community structure when testing can lead to significant savings in terms of the number of tests required to guarantee a given identification accuracy. To show that, we start with a simplistic (yet practical) infection model, where the entire population is organized in (possibly overlapping) communities and the infection probability of an individual depends on the communities (s)he participates in. Given this model, we compute new lower bounds on the number of tests for zero-error identification and design community-aware group testing algorithms that can be optimal under assumptions. Finally, we demonstrate significant benefits over traditional, community-agnostic group testing via simulations using both noiseless and noisy tests. Shorter versions of this article, which contained a subset of the material, were presented in the work by Nikolopoulos et al. (2021, 2021).

We consider the problem of estimating the orientation of a 3D object with the assistance of configurable backscatter tags. We explore the idea of designing tag response codes to improve the accuracy of orientation estimation. To minimize the difference between the true and estimated orientation, we propose two code design criteria. We also derive a lower bound on the worst-case error using Le Cam’s method and provide simulation results for multiple scenarios including line-of-sight only and multipath, comparing the theoretical bounds to those achieved by the designs.

Traditionally, an item-level differential privacy framework has been studied for applications in distributed learning. However, when a client has multiple data samples, and might want to also hide its potential participation, a more appropriate notion is that of user-level privacy [1]. In this paper, we develop a distributed private optimization framework that studies the trade-off between user-level local differential privacy guarantees and performance. This is enabled by a novel distributed user-level private mean estimation algorithm using distributed private heavy-hitter estimation. We use this result to develop the privacy-performance trade-off for distributed optimization.

We consider a distributed detection problem where sensors observe dependent observations. We ask, if we can allow the sensors to locally exchange a few bits with each other, whether we can use these bits to "break" the dependency of the sensor observations, and thus reduce the dependent detection problem to the much better-studied and understood case of conditionally independent observations. To this end, we propose an optimization problem that we prove is equivalent to minimizing the dependency between the sensor observations. This problem is in general NP-hard, however, we show that for at least some cases of Gaussian distributions it can be solved efficiently. For general distributions, we propose to use alternating minimization and derive a constant factor approximation algorithm. Numerical evaluations indicate that our approach can offer significant improvement in detection accuracy over alternative schemes.

We consider the problem of estimating the orientation of a 3D object with the assistance of configurable backscatter tags. We explore the idea of designing tag response codes to improve the accuracy of orientation estimation. To minimize the difference between the true and estimated orientation, we propose two code design criteria. We also derive a lower bound on the worst-case error using Le Cam’s method and provide simulation results for multiple scenarios including perfect and imperfect channel knowledge, comparing the performance of various coding methods against the suggested designs.

We study the problem of group testing with non-identical, independent priors. So far, the pooling strategies that have been proposed in the literature take the following approach: a hand-crafted test design along with a decoding strategy is proposed, and guarantees are provided on how many tests are sufficient in order to identify all infections in a population. In this paper, we take a different, yet perhaps more practical, approach: we fix the decoder and the number of tests, and we ask, given these, what is the best test design one could use? We explore this question for the Definite Non-Defectives (DND) decoder. We formulate a (non-convex) optimization problem, where the objective function is the expected number of errors for a particular design. We find approximate solutions via gradient descent, which we further optimize with informed initialization. We illustrate through simulations that our method can achieve significant performance improvement over traditional approaches.

In this paper, we introduce a "discrete-time SIR stochastic block model" that also allows for group testing and interventions on a daily basis. Our model can be regarded as a discrete version of the well-known continuous-time SIR stochastic network model [1] and relies on a specific type of weighted graph to capture the underlying community spread. Given that infection model, we then formulate a dynamic group-testing problem by asking: (a) what is the minimum number of tests needed everyday to identify all infections? and (b) are there nonadaptive group testing strategies that achieve this with vanishing error probability? Our results show that one can leverage the knowledge of the community infection model to compute a lower bound on the number of tests and also inform nonadaptive group testing algorithms, so that they can achieve (almost) the same performance as complete individual testing with a much smaller number of tests. Moreover, these algorithms are order-optimal, under specific conditions.

We derive information theoretic generalization bounds for supervised learning algorithms based on a new measure of leave-one-out conditional mutual information (loo-CMI). In contrast to other CMI bounds, which may be hard to evaluate in practice, our loo-CMI bounds are easier to compute and can be interpreted in connection to other notions such as classical leave-one-out cross-validation, stability of the optimization algorithm, and the geometry of the loss-landscape. It applies both to the output of training algorithms as well as their predictions. We empirically validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning. In particular, our bounds are non-vacuous on image-classification tasks.

We study the generalized degrees of freedom (gDoF) of the block-fadingnoncoherent2-user interference channel (IC) with a coherence time of$T$symbol durations and symmetric fading statistics. We demonstrate that a standard training-based scheme for the noncoherent IC is suboptimal in several regimes. We study and analyze several alternate schemes: the first is a new noncoherent scheme using rate-splitting. We also consider a scheme that treats interference-as-noise (TIN) and a time division multiplexing (TDM) scheme. We show that a standard training-based scheme for the noncoherent IC is outperformed by one of these schemes in several regimes: our results demonstrate that in the very weak interference regime, the TIN scheme is the best; in the strong interference regime, the TDM scheme and the noncoherent rate-splitting scheme give better performance; in other cases either of the TIN, TDM or noncoherent rate-splitting scheme could be preferred. We also study the noncoherent IC with feedback and propose another noncoherent rate-splitting scheme. Again for the feedback case, our results demonstrate that a standard training-based scheme can be outperformed by other schemes.

We consider a distributed empirical risk minimization (ERM) optimization problem with communication efficiency and privacy requirements, motivated by the federated learning (FL) framework. We propose a distributed communication-efficient and local differentially private stochastic gradient descent (CLDP-SGD) algorithm and analyze its communication, privacy, and convergence trade-offs. Since each iteration of the CLDP-SGD aggregates the client-side local gradients, we develop (optimal) communication-efficient schemes for mean estimation for several $\ell_p$ spaces under local differential privacy (LDP). To overcome performance limitation of LDP, CLDP-SGD takes advantage of the inherent privacy amplification provided by client subsampling and data subsampling at each selected client (through SGD) as well as the recently developed shuffled model of privacy. For convex loss functions, we prove that the proposed CLDP-SGD algorithm matches the known lower bounds on the \textit{centralized} private ERM while using a finite number of bits per iteration for each client, \emph{i.e.,} effectively getting communication efficiency for “free”. We also provide preliminary experimental results supporting the theory.

In this paper, we propose algorithms that leverage a known community structure to make group testing more efficient. We consider a population organized in disjoint communities: each individual participates in a community, and its infection probability depends on the community (s)he participates in. Use cases include families, students who participate in several classes, and workers who share common spaces. Group testing reduces the number of tests needed to identify the infected individuals by pooling diagnostic samples and testing them together. We show that if we design the testing strategy taking into account the community structure, we can significantly reduce the number of tests needed for adaptive and non-adaptive group testing, and can improve the reliability in cases where tests are noisy.

The central question studied in this paper is Rényi Differential Privacy (RDP) guarantees for general discrete local randomizers in the shuffle privacy model. In the shuffle model, each of the n clients randomizes its response using a local differentially private (LDP) mechanism and the untrusted server only receives a random permutation (shuffle) of the client responses without association to each client. The principal result in this paper is the first direct RDP bounds for general discrete local randomization in the shuffle privacy model, and we develop new analysis techniques for deriving our results which could be of independent interest. In applications, such an RDP guarantee is most useful when we use it for composing several private interactions. We numerically demonstrate that, for important regimes, with composition our bound yields an improvement in privacy guarantee by a factor of $8\times$ over the state-of-the-art approximate Differential Privacy (DP) guarantee (with standard composition) for shuffle models. Moreover, combining with Poisson subsampling, our result leads to at least $10\times$ improvement over subsampled approximate DP with standard composition.

In this paper, we propose algorithms that leverage a known community structure to make group testing more efficient. We consider a population organized in connected communities: each individual participates in one or more communities, and the infection probability of each individual depends on the communities (s)he participates in. Use cases include students who participate in several classes, and workers who share common spaces. Group testing reduces the number of tests needed to identify the infected individuals by pooling diagnostic samples and testing them together. We show that making testing algorithms aware of the community structure, can significantly reduce the number of tests needed both for adaptive and non-adaptive group testing.

We study stochastic gradient descent (SGD) with local iterations in the presence of Byzantine clients, motivated by the federated learning. The clients, instead of communicating with the server in every iteration, maintain their local models, which they update by taking several SGD iterations based on their own datasets and then communicate the net update with the server, thereby achieving communication-efficiency. Furthermore, only a subset of clients communicates with the server at synchronization times. The Byzantine clients may collude and send arbitrary vectors to the server to disrupt the learning process. To combat the adversary, we employ an efficient high-dimensional robust mean estimation algorithm at the server to filter-out corrupt vectors; and to analyze the outlier-filtering procedure, we develop a novel matrix concentration result that may be of independent interest. We provide convergence analyses for both strongly-convex and non-convex smooth objectives in the heterogeneous data setting. We believe that ours is the first Byzantine-resilient local SGD algorithm and analysis with non-trivial guarantees. We corroborate our theoretical results with preliminary experiments for neural network training.

We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our heterogeneous data setting where workers compute stochastic gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly-convex and non-convex objectives and show that our convergence rates match that of vanilla SGD in the Byzantine-free setting. In order to bound the heterogeneity, we assume that the gradients at different workers have bounded deviation from each other, and we also provide concrete bounds on this deviation in the statistical heterogeneous data model.

This paper studies a distributed optimization problem in the federated learning (FL) framework under differential privacy constraints, whereby a set of clients having local samples are connected to an untrusted server, who wants to learn a global model while preserving the privacy of clients' local datasets. We propose a new client sampling called self-sampling that reflects the random availability of clients in the learning process in FL. We analyze the differential privacy of the SGD with client self-sampling by composing amplification by sub-sampling along with amplification by shuffling. Furthermore, we analyze the convergence of the proposed SGD algorithm showing that we can get a reasonable learning performance while preserving the privacy of clients' data even with client self-sampling.

In this paper, we propose and analyze SQuARM-SGD, a communication-efficient algorithm for decentralized training of large-scale machine learning models over a network. In SQuARM-SGD, each node performs a fixed number of local SGD steps using Nesterov’s momentum and then sends sparsified and quantized updates to its neighbors regulated by a locally computable triggering criterion. We provide convergence guarantees of our algorithm for general (non-convex) and convex smooth objectives, which, to the best of our knowledge, is the first theoretical analysis for compressed decentralized SGD with momentum updates. We show that the convergence rate of SQuARM-SGD matches that of vanilla SGD. We empirically show that including momentum updates in SQuARM-SGD can lead to better test performance than the current state-of-the-art which does not consider momentum updates.

SIR (Susceptible, Infected or Recovered) stochastic network models are commonly used to describe the progression of epidemics inside a network. A task of interest in epidemiology is to use these models to estimate the state evolution, both at an individual as well as a population level. In this paper, we propose using continual testing to improve the state estimation at the individual level. Our testing is inspired from entropy reduction principles and requires only a small number of tests.

We study privacy in a distributed learning framework, where clients collaboratively build a learning model iteratively throughinteractions with a server from whom we need privacy. Motivated by stochastic optimization and the federated learning (FL) paradigm, we focus on the case where a small fraction of data samples are randomly sub-sampled in each round to participate in the learning process, which also enables privacy amplification. To obtain even stronger local privacy guarantees, we study this in the shuffle privacy model, where each client randomizes its response using a local differentially private (LDP) mechanism and the server only receives a random permutation (shuffle) of the clients' responses without theirassociation to each client. The principal result of this paper is a privacy-optimization performance trade-off for discrete randomization mechanisms in this sub-sampled shuffle privacy model. This is enabledthrough a new theoretical technique to analyze the Renyi Differential Privacy (RDP) of the sub-sampled shuffle model. We numerically demonstrate that, for important regimes, with composition our boundyields significant improvement in privacy guarantee over the state-of-the-art approximate Differential Privacy (DP) guarantee (with strong composition) for sub-sampled shuffled models. We also demonstrate numerically significant improvement in privacy-learning performance operating point using real data sets. Despite these advances, an open question is to bridge the gap between lower and upper privacy bounds in our RDP analysis.

Traditionally, federated learning (FL) aims to train a single global model while collaboratively using multiple clients and a server. Two natural challenges that FL algorithms face are heterogeneity in data across clients and collaboration of clients with diverse resources. In this work, we introduce a quantized and personalized FL algorithm QuPeD that facilitates collective (personalized model compression) training via knowledge distillation (KD) among clients who have access to heterogeneous data and resources. For personalization, we allow clients to learn compressed personalized models with different quantization parameters and model dimensions/structures. Towards this, first we propose an algorithm for learning quantized models through a relaxed optimization problem, where quantization values are also optimized over. When each client participating in the (federated) learning process has different requirements of the compressed model (both in model dimension and precision), we formulate a compressed personalization framework by introducing knowledge distillation loss for local client objectives collaborating through a global model. We develop an alternating proximal gradient update for solving this compressed personalization problem, and analyze its convergence properties. Numerically, we validate that QuPeD outperforms competing personalized FL methods, FedAvg, and local training of clients in various heterogeneous settings.

MOTIVATION: Efficient and accurate alignment of DNA/RNA sequence reads to each other or to a reference genome/transcriptome is an important problem in genomic analysis. Nanopore sequencing has emerged as a major sequencing technology and many long-read aligners have been designed for aligning nanopore reads. However, the high error rate makes accurate and efficient alignment difficult. Utilizing the noise and error characteristics inherent in the sequencing process properly can play a vital role in constructing a robust aligner. In this article, we design QAlign, a pre-processor that can be used with any long-read aligner for aligning long reads to a genome/transcriptome or to other long reads. The key idea in QAlign is to convert the nucleotide reads into discretized current levels that capture the error modes of the nanopore sequencer before running it through a sequence aligner. RESULTS: We show that QAlign is able to improve alignment rates from around 80% up to 90% with nanopore reads when aligning to the genome. We also show that QAlign improves the average overlap quality by 9.2, 2.5 and 10.8% in three real datasets for read-to-read alignment. Read-to-transcriptome alignment rates are improved from 51.6% to 75.4% and 82.6% to 90% in two real datasets. AVAILABILITY AND IMPLEMENTATION: https://github.com/joshidhaivat/QAlign.git. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We study distributed optimization in the presence of Byzantine adversaries, where both data and computation are distributed among$m$worker machines,$t$of which may be corrupt. The compromised nodes may collaboratively and arbitrarily deviate from their pre-specified programs, and a designated (master) node iteratively computes the model/parameter vector forgeneralized linear models. In this work, we primarily focus on two iterative algorithms:Proximal Gradient Descent(PGD) andCoordinate Descent(CD). Gradient descent (GD) is a special case of these algorithms. PGD is typically used in the data-parallel setting, where data is partitioned across different samples, whereas, CD is used in the model-parallelism setting, where data is partitioned across the parameter space. At the core of our solutions to both these algorithms is a method for Byzantine-resilient matrix-vector (MV) multiplication; and for that, we propose a method based on data encoding and error correction over real numbers to combat adversarial attacks. We can tolerate up to$t\leq \lfloor \frac {m-1}{2}\rfloor $corrupt worker nodes, which is information-theoretically optimal. We give deterministic guarantees, and our method does not assume any probability distribution on the data. We develop asparseencoding scheme which enables computationally efficient data encoding and decoding. We demonstrate a trade-off between the corruption threshold and the resource requirements (storage, computational, and communication complexity). As an example, for$t\leq \frac {m}{3}$, our scheme incurs only aconstantoverhead on these resources, over that required by the plain distributed PGD/CD algorithms which provide no adversarial protection. To the best of our knowledge, ours is the first paper that connects MV multiplication with CD and designs a specific encoding matrix for MV multiplication whose structure we can leverage to make CD secure against adversarial attacks. Our encoding scheme extendsefficientlyto(i)the data streaming model, in which data samples come in an online fashion and are encoded as they arrive, and(ii)makingstochastic gradient descent(SGD) Byzantine-resilient. In the end, we give experimental results to show the efficacy of our proposed schemes.

Recent advances in DNA sequencing technology and DNA storage systems have rekindled the interest in deletion channels. Multiple recent works have looked at variants of sequence reconstruction over a single and over multiple deletion channels, a notoriously difficult problem due to its highly combinatorial nature. Although works in theoretical computer science have provided algorithms which guarantee perfect reconstruction with multiple independent observations from the deletion channel, they are only applicable in the large blocklength regime and more restrictively, when the number of observations is also large. Indeed, with only a few observations, perfect reconstruction of the input sequence may not even be possible in most cases. In such situations, maximum likelihood (ML) and maximum aposteriori (MAP) estimates for the deletion channels are natural questions that arise and these have remained open to the best of our knowledge. In this work, we take steps to answer the two aforementioned questions. Specifically: 1. We show that solving for the ML estimate over the single deletion channel (which can be cast as a discrete optimization problem) is equivalent to solving its relaxation, a continuous optimization problem; 2. We exactly compute the symbolwise posterior distributions (under some assumptions on the priors) for both the single as well as multiple deletion channels. As part of our contributions, we also introduce tools to visualize and analyze error events, which we believe could be useful in other related problems concerning deletion channels.

In this paper, we consider the problem of estimating the orientation of an object that has been custom-"painted" by an array of backscatter tags. We pose the problem as a coding matrix design with the objective of minimizing orientation estimation error. We show that it is only necessary to consider a subset of code configurations and provide a tractable linear program to find the optimal coding strategy. We provide simulation results using an icosahedral tag arrangement.

We study stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. Building upon the recent advances in algorithmic high-dimensional robust statistics, in each SGD iteration, master employs a non-trivial decoding to estimate the true gradient from the unbiased stochastic gradients received from workers, some of which may be corrupt. We provide convergence analyses for both strongly-convex and non-convex smooth objectives under standard SGD assumptions. We can control the approximation error of our solution in both these settings by the mini-batch size of stochastic gradients; and we can make the approximation error as small as we want, provided that workers use a sufficiently large mini-batch size. Our algorithm can tolerate less than 1/3 fraction of Byzantine workers. It can approximately find the optimal parameters in the strongly-convex setting exponentially fast, and reaches to an approximate stationary point in the non-convex setting with linear speed, i.e., with a rate of 1/T, thus, matching the convergence rates of vanilla SGD in the Byzantine-free setting.

In this paper, we study an estimation problem under the local differential privacy (LDP) framework: There is an ordered list of d values (e.g., real numbers); a set of n users, where each user observes an element from this list and each value in the list is observed by at least one user; and an untrusted server, who wants to estimate the values that the users possess, without learning (in the sense of LDP) the actual value that each user has and its corresponding index in the list. Towards this, we propose two LDP estimation schemes: The first one is under the assumption that the server knows the number of users that observe each value; and the second one is for the general scenario, in which the server does not have this prior information. We show that the minimax risk decreases with the total number of users under a very mild condition on the number of users observing each value.

Maximum likelihood (ML) and symbolwise maximum aposteriori (MAP) estimation for discrete input sequences play a central role in a number of applications that arise in communications, information and coding theory. Many instances of these problems are proven to be intractable, for example through reduction to NP-complete integer optimization problems. In this work, we prove that the ML estimation of a discrete input sequence (with no assumptions on the encoder/channel used) is equivalent to the solution of a continuous non-convex optimization problem, and that this formulation is closely related to the computation of symbolwise MAP estimates. This equivalence is particularly useful in situations where a function we term the expected likelihood is efficiently computable. In such situations, we give a ML heuristic and show numerics for sequence estimation over the deletion channel.

Lightweight cryptography has become more and more important in recent years because of the rise of the Internet of Things (IoT) and usage of smart mobile devices. In this paper, we propose a novel secure lightweight entity authentication hardware primitive called SLATE, where its area is about 50% to more than 3X smaller than existing lightweight ciphers and strong physical unclonable functions (PUFs), respectively. Even though the authentication of SLATE is done through challenge response pair (CRP) verification similar to strong PUFs, the source of the key for SLATE must be coming from any existing secret key storage used for any ciphers. A main advantage of SLATE over most existing strong PUFs being an entity authentication primitive is that SLATE is resistant to known attacks to strong PUFs or logic obfuscations, such as model building attacks and Boolean satisfiability (SAT) attacks. Furthermore, we show that the implementation cost of SLATE with a 176-bit key and 244 CRPs is only 663 gate equivalents (GEs). Compared with lightweight ciphers and existing secure strong PUFs, we show that SLATE is a practical security primitive for resource constrained systems for its extremely small footprint and security. Finally, we show that SLATE is information theoretically secure when valid CRPs are communicated through insecure channels.

We study the generalized degrees of freedom (gDoF) of block-fading noncoherent multiple input multiple output (MIMO) channels with asymmetric distributions of link strengths and a coherence time of T symbol durations. We derive the optimal signaling structure for communication for the asymmetric MIMO channel, which is distinct from that for the MIMO channel with independent and identically distributed (i.i.d.) links. We extend the existing results for the single input multiple output (SIMO) channel with i.i.d. links to the asymmetric case, proving that selecting the statistically best antenna is gDoFoptimal. Using the gDoF result for the SIMO channel, we prove that for T = 1, the gDoF is zero for MIMO channels with arbitrary link strengths. We show that selecting the statistically best antenna is gDoF-optimal for the multiple input single output (MISO) channel. We also derive the gDoF for the 2 x 2 MIMO channel with different exponents in the direct and cross links. In this setting, we show that it is always necessary to use both the antennas to achieve the gDoF, in contrast to the results for the 2 x 2 MIMO channel with i.i.d. links. We show that having weaker crosslinks, gives gDoF gain compared to the case with i.i.d. links. For the noncoherent MIMO channel with i.i.d. links, the traditional method of training each transmit antenna independently is degrees of freedom (DoF) optimal, whereas we observe that for the asymmetric 2 x 2 MIMO channel, the traditional training is not gDoF-optimal. We extend this observation to a larger MxM MIMO channel by demonstrating a strategy that can achieve larger gDoF than a traditional trainingbased method.

We study the generalized degrees of freedom (gDoF) of the noncoherent diamond (parallel relay) wireless network with asymmetric distributions of link strengths. We use the noncoherent block-fading model introduced by Marzetta and Hochwald, where no channel state information is available at the transmitters or at the receivers and the channels remain constant for a coherence time of T symbol durations. We first derive an upper bound for the capacity of this channel and then derive the optimal structure for the solution of the upper bound optimization problem. Using the optimal structure, we solve the upper bound optimization problem in terms of its gDoF. Using insights from our upper bound signaling solution, we devise an achievability strategy based on a novel scheme that we call train-scale quantize-map-forward (TS-QMF). This scheme uses training in the links from the source to the relays, scaling and quantizing at the relays combined with nontraining-based schemes. We show the optimality of this scheme by comparing it to the upper bound in terms of the gDoF. In noncoherent point-to-point multiple-input-multiple-output (MIMO) channels, where the fading realization is unknown to the transmitter and the receiver, an important tradeoff between communication and channel learning was revealed by Zheng and Tse, by demonstrating that not all the available antennas might be used, as it is suboptimal to learn all their channel parameters. Our results in this paper for the diamond network demonstrate that in certain regimes of relative channel strengths, the gDoF-optimal scheme uses a subnetwork, demonstrating a similar tradeoff between channel learning and communication. In some regimes, it is gDoF-optimal to do relay selection, i.e., use a part of the network. In the other regimes, even when it is essential to use the entire network, it is suboptimal to learn the channel states for all the links in the network, i.e., traditional training-based schemes are suboptimal in these regimes.

We study distributed coordinate descent (CD) in the master-worker architecture under adversarial attacks, where the data is partitioned (across the parameter space) and distributed among m worker nodes (t of which can be maliciously corrupt), which update some coordinates of their part of the parameter vector, in parallel and iteratively, using CD updates, with the help of the master. We propose a method based on data encoding and real error correction to combat the adversary. Our method can tolerate up to ⌈m-1/2⌉ corrupt nodes, which is information-theoretically optimal. Our design gives a trade-off between the resiliency t, the required redundancy, and the computation at master and worker nodes. For example, with constant overhead in the storage and computational complexity over that required by the plain distributed CD, we can tolerate up to m/3 corrupt nodes. We design a sparse encoding scheme, which yields low encoding complexity.

We consider distributed gradient computation, where both data and computation are distributed among m worker machines, t of which can be Byzantine adversaries, and a designated (master) node computes the model/parameter vector for generalized linear models, iteratively, using proximal gradient descent (PGD), of which gradient descent (GD) is a special case. The Byzantine adversaries can (collaboratively) deviate arbitrarily from their gradient computation. To solve this, we propose a method based on data encoding and (real) error correction to combat the adversarial behavior. We can tolerate up to t ≤ [m-1/2] corrupt worker nodes, which is information-theoretically optimal. Our method does not assume any probability distribution on the data. We develop a sparse encoding scheme which enables computationally efficient data encoding. We demonstrate a trade-off between the number of adversaries tolerated and the resource requirement (storage and computational complexity). As an example, our scheme incurs a constant overhead (storage and computational complexity) over that required by the distributed PGD algorithm, without adversaries, for t ≤ m/3 . Our encoding works as efficiently in the streaming data etting as it does in the

In many machine learning applications, once we have learned a classifier, in order to apply it, we may still need to gather features from distributed sensors over communication constrained channels. In this paper, we propose a polynomial complexity algorithm for feature quantization tailored to minimizing the classification error of a linear classifier. Our scheme produces scalar quantizers that are well-tailored to delay-sensitive applications, operates on the same training data used to learn the classifier, and allows each distributed sensor to operate independently of each other. Numerical evaluation indicates up to 65% benefits over alternative approaches. Additionally, we provide an example where, jointly designing the linear classifier and the quantization scheme, can outperform sequential designs.

We consider the problem of reconstructing a sequence from fixed number of deleted versions of itself (also called traces). The problem is motivated from recent developments in de novo DNA sequencing technologies. The main contribution of this work is to provide a polynomial time algorithm for symbolwise MAP decoding with multiple traces. The algorithm leverages a dynamic program on the edit graph. We also develop a heuristic with reduced time complexity using similar ideas and provide preliminary numerical evaluations.

Communication bottleneck has been identified as a significant issue in distributed optimization of large-scale learning models. Recently, several approaches to mitigate this problem have been proposed, including different forms of gradient compression or computing local models and mixing them iteratively. In this paper we propose Qsparse-local-SGD algorithm, which combines aggressive sparsification with quantization and local computation along with error compensation, by keeping track of the difference between the true and compressed gradients. We propose both synchronous and asynchronous implementations of Qsparse-local-SGD. We analyze convergence for Qsparse-local-SGD in the distributed case, for smooth non-convex and convex objective functions. We demonstrate that Qsparse-local-SGD converges at the same rate as vanilla distributed SGD for many important classes of sparsifiers and quantizers. We use Qsparse-local-SGD to train ResNet-50 on ImageNet, and show that it results in significant savings over the state-of-the-art, in the number of bits transmitted to reach target accuracy.

Performance of distributed optimization and learning systems is bottlenecked by “straggler” nodes and slow communication links, which significantly delay computation. We propose a distributed optimization framework where the dataset is “encoded” to have an over-complete representation with built-in redundancy, and the straggling nodes in the system are dynamically treated as missing, or as “erasures” at every iteration, whose loss is compensated by the embedded redundancy. For quadratic loss functions, we show that under a simple encoding scheme, many optimization algorithms (gradient descent, L-BFGS, and proximal gradient) operating under data parallelism converge to an approximate solution even when stragglers are ignored. Furthermore, we show a similar result for a wider class of convex loss functions when operating under model parallelism. The applicable classes of objectives covers several popular learning problems such as linear regression, LASSO, support vector machine, collaborative filtering, and generalized linear models including logistic regression. These convergence results are deterministic, i.e., they establish sample path convergence for arbitrary sequences of delay patterns or distributions on the nodes, and are independent of the tail behavior of the delay distribution. We demonstrate that equiangular tight frames have desirable properties as encoding matrices, and propose efficient mechanisms for encoding large-scale data. We implement the proposed technique on Amazon EC2 clusters, and demonstrate its performance over several learning problems, including matrix factorization, LASSO, ridge regression and logistic regression, and compare the proposed method with uncoded, asynchronous, and data replication strategies.

The vision of an Internet-of-Things calls for combining the increasing connectivity of devices at the edge with the ability to compute either at the edge or on more powerful servers in the network. There is great interest in exploring the feasibility of these ideas when devices such as quadcopters or ground robots at the edge are controlled over the cloud, i.e., by leveraging computational power available elsewhere in the network. One of the main difficulties, especially in the context of the Internet-of-Battlefield- Things is the need to keep the data private. In this paper we propose a solution to this problem by extending previous results by the authors from a single system controlled over the cloud to networks of systems that are controlled and coordinated over the cloud. We propose a noncryptographic lightweight encoding scheme that ensures the privacy of the data exchanged by all the participating parties.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

Data privacy is an important concern in machine learning, and is fundamentally at odds with the task of training useful learning models, which typically require acquisition of large amounts of private user data. One possible way of fulfilling the machine learning task while preserving user privacy is to train the model on a transformed, noisy version of the data, which does not reveal the data itself directly to the training procedure. In this work, we analyze the privacy-utility tradeoff of two such schemes for the problem of linear regression: additive noise, and random projections. In contrast to previous work, we consider a recently proposed notion of differential privacy that is based on conditional mutual information (MI-DP), which is stronger than the conventional (ε,δ) -differential privacy, and use relative objective error as the utility metric. We find that projecting the data to a lower-dimensional subspace before adding noise attains a better trade-off in general. We also make a connection between privacy problem and (non-coherent) SIMO, which has been extensively studied in wireless communication, and use tools from there for the analysis. We present numerical results demonstrating the performance of the schemes.

The problem of reconstructing a sequence when observed through multiple looks over deletion channels occurs in “de novo” DNA sequencing. The DNA could be sequenced multiple times, yielding several “looks” of it, but each time the sequencer could be noisy with (independent) deletion impairments. The main goal of this paper is to develop reconstruction algorithms for a sequence observed through the lens of a fixed number of deletion channels. We use the probabilistic model of the deletion channels to develop both symbol-wise and sequence maximum likelihood decoding criteria, and algorithms motivated by them. Numerical evaluations demonstrate improvement in terms of edit distance error, over earlier algorithms.

We study the caching problem when we are allowed to match each user to one of a subset of caches after its request is revealed. We focus on non-uniformly popular content, specifically when the file popularities obey a Zipf distribution. We study two extremal schemes: one focusing on coded server transmissions while ignoring matching capabilities and the other focusing on adaptive matching while ignoring potential coding opportunities. We derive the rates achieved by these schemes and characterize the regimes in which one outperforms the other. We also compare them to information-theoretic outer bounds and finally propose a hybrid scheme that generalizes ideas from the two schemes and performs at least as well as either of them in most memory regimes.

We develop a characterization of fading models, which assigns a number called logarithmic Jensen's gap to a given fading model. We show that as a consequence of a finite logarithmic Jensen's gap, an approximate capacity region can be obtained for fast fading interference channels (FF-ICs) for several scenarios. We illustrate three instances where a constant capacity gap can be obtained as a function of the logarithmic Jensen's gap. First, for an FF-IC with neither feedback nor instantaneous channel state information at transmitter (CSIT), if the fading distribution has finite logarithmic Jensen's gap, we show that a rate-splitting scheme based on the average interference-to-noise ratio can achieve its approximate capacity. Second, we show that a similar scheme can achieve the approximate capacity of FF-IC with feedback and delayed CSIT, if the fading distribution has finite logarithmic Jensen's gap. Third, when this condition holds, we show that point-to-point codes can achieve approximate capacity for a class of FF-ICs with feedback. We prove that the logarithmic Jensen's gap is finite for common fading models, including Rayleigh and Nakagami fading, thereby obtaining the approximate capacity region of FF-IC with these fading models.

The lack of stability is one of the limitations that constrain physical unclonable function (PUF) from being put in widespread practical use. In this paper, we propose a weak PUF and a strong PUF that are both completely stable. These PUFs are called locally enhanced defectivity physical unclonable function (LEDPUF). An LEDPUF is a pure functional PUF that does not require any kinds of correction schemes as conventional parametric PUFs do. The source of randomness of an LEDPUF is extracted from locally enhance defectivity without affecting other parts of the chip. In this paper, we construct a weak LEDPUF by forming arrays of directed self-assembly random connections, and the strong LEDPUF is implemented by using the weak LEDPUF as the key of a keyed-hash message authentication code. Our simulation and statistical results show that the entropy of the weak LEDPUF bits is close to ideal, and the inter-chip Hamming distances of both weak and strong LEDPUFs are about 50%, which means that these LEDPUFs are not only stable but also unique. We develop a new unified framework for evaluating the security of PUFs, based on password security, by using information theoretic tools of guesswork. The guesswork model allows us to quantitatively compare, with a single unified metric, PUFs with varying levels of stability, bias, and available side information. In addition, it generalizes other measures to evaluate the security level, such as min-entropy and mutual information. We evaluate the guesswork-based security of some measured static random access memory and ring oscillator PUFs as an example and compare them with an LEDPUF to show that the stability has a more severe impact on the PUF security than biased responses. Furthermore, we find the guesswork of two new problems: guesswork under the probability of attack failure and the guesswork of strong PUFs that are used for authentication.

We study the role of caches in wireless interference networks. We focus on content caching and delivery across a Gaussian interference network, where both transmitters and receivers are equipped with caches. We provide a constant-factor approximation of the system's degrees of freedom (DoF), for arbitrary number of transmitters, number of receivers, content library size, receiver cache size, and transmitter cache size (as long as the transmitters combined can store the entire content library among them). We demonstrate approximate optimality with respect to information-theoretic bounds that do not impose any restrictions on the caching and delivery strategies. Our characterization reveals three key insights. First, the approximate DoF is achieved using a strategy that separates the physical and network layers. This separation architecture is thus approximately optimal. Second, we show that increasing transmitter cache memory beyond what is needed to exactly store the entire library between all transmitters does not provide more than a constant-factor benefit to the DoF. A consequence is that transmit zero-forcing is not needed for approximate optimality. Third, we derive an interesting tradeoff between the receiver memory and the number of transmitters needed for approximately maximal performance. In particular, if each receiver can store a constant fraction of the content library, then only a constant number of transmitters are needed. Our solution to the caching problem requires formulating and solving a new communication problem, the symmetric multiple multicast X-channel, for which we provide an exact DoF characterization.

Nanopore sequencing is an emerging new technology for sequencing Deoxyribonucleic acid (DNA), which can read long fragments of DNA (~50000 bases), in contrast to most current short-read sequencing technologies which can only read hundreds of bases. While nanopore sequencers can acquire long reads, the high error rates (20%-30%) pose a technical challenge. In a nanopore sequencer, a DNA is migrated through a nanopore, and current variations are measured. The DNA sequence is inferred from this observed current pattern using an algorithm called a base-caller. In this paper, we propose a mathematical model for the “channel” from the input DNA sequence to the observed current, and calculate bounds on the information extraction capacity of the nanopore sequencer. This model incorporates impairments, such as (non-linear) intersymbol interference, deletions, and random response. These information bounds have two-fold application: 1) The decoding rate with a uniform input distribution can be used to calculate the average size of the plausible list of DNA sequences given an observed current trace. This bound can be used to benchmark existing base-calling algorithms, as well as serving a performance objective to design better nanopores. 2) When the nanopore sequencer is used as a reader in a DNA storage system, the storage capacity is quantified by our bounds.

We study the coded caching problem when we are allowed to match users to caches based on their requested files. We focus on the case where caches are divided into clusters and each user can be assigned to a unique cache from a specific cluster. We show that neither the coded delivery strategy (approximately optimal when the user-cache assignment is pre-fixed) nor the uncoded replication strategy (approximately optimal when all caches belong to a single cluster) is sufficient for all memory regimes. We propose a hybrid solution that combines ideas from both schemes and that performs at least as well as either strategy in most memory regimes. Finally, we show that this hybrid strategy is approximately optimal in most memory regimes.

Today, many real-world machine learning and data analytics problems are of a scale that requires distributed optimization; unlike in centralized computing, these systems are vulnerable to network and node failures. Recently, coding-theoretic ideas have been applied to mitigate node failures in such distributed computing networks. Relaxing the exact recovery requirement of such techniques, we propose a novel approach for adding redundancy in large-scale convex optimization problems, making solvers more robust against sudden and persistent node failures and loss of data. This is done by linearly encoding the data variables; all other aspects the computation operate as usual. We show that under moderate amounts of redundancy, it is possible to recover a close approximation to the solution under node failures. In particular, we show that encoding with (equiangular) tight frames result in bounded objective error, and obtain an explicit error bound for a specific construction that uses Paley graphs. We also demonstrate the performance of the proposed technique for three specific machine learning problems, (two using real world datasets) namely ridge regression, binary support vector machine, and low-rank approximation.

Nanopore sequencing is an emerging new technology for sequencing DNA, which can read long fragments of DNA (~50,000 bases) unlike most current sequencers which can only read hundreds of bases. While nanopore sequencers can acquire long reads, the high error rates (≈ 30%) pose a technical challenge. In a nanopore sequencer, a DNA is migrated through a nanopore and current variations are measured. The DNA sequence is inferred from this observed current pattern using an algorithm called a base-caller. In this paper, we propose a mathematical model for the “channel” from the input DNA sequence to the observed current, and calculate bounds on the information extraction capacity of the nanopore sequencer. This model incorporates impairments like inter-symbol interference, deletions, as well as random response. The practical application of such information bounds is two-fold: (1) benchmarking present base-calling algorithms, and (2) offering an optimization objective for designing better nanopore sequencers.

We study the generalized degrees of freedom (gDoF) of the block-fading noncoherent MIMO channel with asymmetric distributions of link strengths, and a coherence time of T symbol durations. We first derive the optimal signaling structure for communication over this channel, which is distinct from that for the i.i.d MIMO setting. We prove that for T = 1, the gDoF is zero for MIMO channels with arbitrary link strength distributions, extending the result for MIMO with i.i.d links. We then show that selecting the statistically best antenna is gDoF-optimal for both Multiple Input Single Output (MISO) and Single Input Multiple Output (SIMO) channels. We also derive the gDoF for the 2×2 MIMO channel with different exponents in the direct and cross links. In this setting, we show that it is always necessary to use both antennas to achieve the optimal gDoF, in contrast to the results for 2 × 2 MIMO with identical link distributions. We also show that having weaker crosslinks gives gDoF gain compared to the case with identically distributed links.

Eavesdropping attacks in inference systems aim to learn not the raw data, but the system inferences to predict and manipulate system actions. We argue that conventional information security measures can be ambiguous on the adversary's estimation abilities, and adopt instead a distortion based framework that enables to operate over a metric space. We show that requiring perfect distortion-based security is more frugal than requiring perfect information-theoretic secrecy even for block length one codes, offering in some cases unbounded gains. Within this framework, we design algorithms that enable to efficiently use shared randomness, and show that each bit of shared random key is exponentially useful in security.

In this work we analyze the average guesswork for the problem of hashed password cracking (i.e., finding a password that has the same hash value as the actual password), when averaging over all hash functions whose effective distribution is i.i.d. Bernoulli(p) for any strategy of guessing passwords one by one (i.e., the fractions of passwords that are hashed to any bin, correspond to a probability mass function, which is i.i.d. Bernoulli(p)). We analyze the average guesswork under both online and offline attacks by deriving upper and lower bounds on the average guesswork as a function of the bins to which passwords are hashed, along with the most likely average guesswork, that is, the average guesswork of the most likely set of bins. Furthermore, we provide a concentration result that shows for this problem, that the probability mass function of guesswork is concentrated around its mean value. These results give quantifiable bounds for the effect of bias as well as the number of users on the average guesswork of a hash function, and show that increasing the number of users has a far worse effect than bias in terms of the average guesswork. However, when there exists a backdoor mechanism that enables “beamforming” certain passwords to the least likely bins, bias can in fact increase the average guesswork.

We study the caching problem when we are allowed to match each user to one of a subset of caches after its request is revealed. We focus on non-uniformly popular content, specifically when the file popularities obey a Zipf distribution. We study two extremal schemes, one focusing on coded server transmissions while ignoring matching capabilities, and the other focusing on adaptive matching while ignoring potential coding opportunities. We derive the rates achieved by these schemes and characterize the regimes in which one outperforms the other. We also compare them to information-theoretic outer bounds, and finally propose for certain cases a hybrid scheme that generalizes ideas from the two schemes and performs at least as well as either of them in most memory regimes.

Slow running or straggler tasks can significantly reduce computation speed in distributed computation. Recently, coding-theory-inspired approaches have been applied to mitigate the effect of straggling, through embedding redundancy in certain linear computational steps of the optimization algorithm, thus completing the computation without waiting for the stragglers. In this paper, we propose an alternate approach where we embed the redundancy directly in the data itself, and allow the computation to proceed completely oblivious to encoding. We propose several encoding schemes, and demonstrate that popular batch algorithms, such as gradient descent and L-BFGS, applied in a coding-oblivious manner, deterministically achieve sample path linear convergence to an approximate solution of the original problem, using an arbitrarily varying subset of the nodes at each iteration. Moreover, this approximation can be controlled by the amount of redundancy and the number of nodes used in each iteration. We provide experimental results demonstrating the advantage of the approach over uncoded and data replication strategies.

We consider a group of m trusted and authenticated nodes that aim to create a shared secret key K over a wireless channel in the presence of an eavesdropper Eve. We assume that there exists a state-dependent wireless broadcast channel from one of the honest nodes to the rest of them including Eve. All of the trusted nodes can also discuss over a cost-free, noiseless and unlimited rate public channel which is also overheard by Eve. For this setup, we develop an information-theoretically secure secret key agreement protocol. We show the optimality of this protocol for “linear deterministic” wireless broadcast channels. This model generalizes the packet erasure model studied in the literature for wireless broadcast channels. Here, the main idea is to convert a deterministic channel into multiple independent erasure channels by using superposition coding. For “state-dependent Gaussian” wireless broadcast channels, by using insights from the deterministic problem, we propose an achievability scheme based on a multi-layer wiretap code. By using the wiretap code, we can mimic the phenomenon of converting the wireless channel into multiple independent erasure channels. Then, finding the best achievable secret key generation rate leads to solving a non-convex power allocation problem over these channels (layers). We show that using a dynamic programming algorithm, one can obtain the best power allocation for this problem. Moreover, we prove the optimality of the proposed achievability scheme for the regime of high-SNR and large-dynamic range over the channel states in the (generalized) degrees of freedom sense.

To address the exponentially rising demand for wireless content, the use of caching is emerging as a potential solution. It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. Coded caching is well suited to emerging heterogeneous wireless architectures which consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). This enables design of coded caching-and-delivery schemes that equip APs with storage, and place content in them in a way that creates coded-multicast opportunities for combining with macro-cell broadcast to satisfy users even with different demands. Such coded-caching schemes have been shown to be order-optimal with respect to the BS transmission rate, for a system with single-level content, i.e., one where all content is uniformly popular. In this paper, we consider a system with non-uniform popularity content which is divided into multiple levels, based on varying degrees of popularity. The main contribution of this paper is the derivation of an order-optimal scheme which judiciously shares cache memory among files with different popularities. To show order-optimality we derive new information-theoretic lower bounds, which use a sliding-window entropy inequality, effectively creating a non-cut-set bound. We also extend the ideas to when users can access multiple caches along with the broadcast. Finally, we consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup), and demonstrate a dichotomy in the order-optimal strategies for these two extreme cases.

In this paper, we study the problem of obtaining 1-of-2 string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users' inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice-Bob and Alice-Eve), we derive the 1-of-2 string OT capacity for both 2-privacy (when Eve can collude with either Alice or Bob) and 1-privacy (when no such collusion is allowed). We generalize these capacity results to 1-of-N string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice-Bob and Alice-Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice-Bob and Bob-Eve) and 1-of-2 string OT is desired between Alice and Bob with 1-privacy. For this setup, we derive an upper and lower bound on the 1-of-2 string OT capacity which match in one of two possible parameter regimes.

We study parallel two-user interference channels when the interference is bursty and feedback is available from the respective receivers. Presence of interference in each subcarrier is modeled as a memoryless Bernoulli random state. The states across subcarriers are drawn from an arbitrary joint distribution with the same marginal probability for each subcarrier and instantiated independent and identically distributed (i.i.d.) over time. For the linear deterministic setup with symmetric interference in each subcarrier, we give a complete characterization of the capacity region. For the analogous setup with Gaussian noise, we give outer bounds and a tight generalized degrees of freedom characterization. We propose a novel helping mechanism, which enables subcarriers in very strong interference regime to help in recovering interfered signals for subcarriers in strong and weak interference regimes. Depending on the interference and burstiness regime, the inner bounds either employ the proposed helping mechanism to code across subcarriers or treat the subcarriers separately. The outer bounds demonstrate a connection to a subset entropy inequality by Madiman and Tetali.

We investigate whether uncoded schemes are optimal for Gaussian sources on multiuser Gaussian channels. Particularly, we consider two problems: the first is to send correlated Gaussian sources on a Gaussian broadcast channel where each receiver is interested in reconstructing only one source component (or one specific linear function of the sources) under the mean squared error distortion measure; the second is to send correlated Gaussian sources on a Gaussian multiple-access channel, where each transmitter observes a noisy combination of the sources, and the receiver wishes to reconstruct the individual source components (or individual linear functions) under the mean squared error distortion measure. It is shown that when the channel parameters satisfy certain general conditions, the induced distortion tuples are on the boundary of the achievable distortion region, and thus optimal. Instead of following the conventional approach of attempting to characterize the achievable distortion region, we ask the question whether and how a match can be effectively determined. This decision problem formulation helps to circumvent the difficult optimization problem often embedded in region characterization problems, and it also leads us to focus on the critical conditions in the outer bounds that make the inequalities become equalities, which effectively decouple the overall problem into several simpler sub-problems. Optimality results previously unknown in the literature are obtained using this novel approach. Explicit and novel outer bounds are derived for the two problems as the byproducts of our investigation.

We propose a cellular architecture that combines multiuser MIMO downlink with opportunistic use of unlicensed Industrial, Scientific, and Medical Radio (ISM) bands to establish device-to-device (D2D) cooperation. The architecture consists of a physical-layer cooperation scheme based on forming downlink virtual MIMO channels through D2D relaying, and a novel resource allocation strategy for such D2D-enabled networks. We prove the approximate optimality of the physical-layer scheme, and demonstrate that such cooperation boosts the effective SNR of the weakest user in the system, especially in the many-user regime, due to multiuser diversity. To harness this physical-layer scheme, we formulate the cooperative user scheduling and the relay selection problem using the network utility maximization framework. For such a cooperative network, we propose a novel utility metric that jointly captures fairness in throughput and the cost of relaying in the system. We propose a joint user scheduling and relay selection algorithm, which we prove to be asymptotically optimal. We study the architecture through system-level simulations over a wide range of scenarios. The highlight of these simulations is an approximately 6× improvement in data rate for cell-edge (bottom fifth-percentile) users (over the state-of-the-art) while still improving the overall throughput, and considering various system constraints.

Recent work has studied the benefits of caching in the interference channel, particularly by placing caches at the transmitters. In this paper, we study the two-user Gaussian interference channel in which caches are placed at both the transmitters and the receivers. We propose a separation strategy that divides the physical and network layers. While a natural separation approach might be to abstract the physical layer into several independent bit pipes at the network layer, we argue that this is inefficient. Instead, the separation approach we propose exposes interacting bit pipes at the network layer, so that the receivers observe related (yet not identical) quantities. We find the optimal strategy within this layered architecture, and we compute the degrees-of-freedom it achieves. Finally, we show that separation is optimal in regimes where the receiver caches are large.

Motivated by the ability of modern terminals to receive simultaneously from multiple networks (e.g., WLAN and Cellular), we extend the single shared link network with caching at the user nodes to the case of r parallel partially shared links, where users in different classes receive from the server simultaneously and in parallel through different set of links. For this setting, we give an order-optimal rate and (maximal) delay region characterization for the case of r = 2 links with two classes of users, one receiving only from link 1 and the other from both links 1 and 2. We also extend these results to r = 3 with three classes of users, receiving from link 1, from links 1 and 2, and from links 1 and 3, respectively.

Superposition codes with rate-splitting have been used for all approximately optimal strategies for the interference channel, with and without feedback. As rate-splitting requires fore-knowledge of channel parameters or statistics, in this paper we explore schemes for the interference channel (with feedback) that do not use superposition or rate-splitting. We demonstrate that point-to-point codes designed for inter-symbol-interference channels, along with time-sharing can approximately achieve the entire rate region of the interference channel with feedback. We show that such a scheme also approximately achieves the rate-region for the interference channel with fading, for a large class of fading distributions.

The problem of multicasting two nested messages is studied over a class of networks known as combination networks. A source multicasts two messages, a common and a private message, to several receivers. A subset of the receivers (called the public receivers) only demand the common message, and the rest of the receivers (called the private receivers) demand both the common and the private message. Three encoding schemes are discussed that employ linear superposition coding, and their optimality is proved in special cases. The standard linear superposition scheme is shown to be optimal for networks with two public receivers and any number of private receivers. When the number of public receivers increases, this scheme stops being optimal. Two improvements are discussed: one using pre-encoding at the source, and one using a block Markov encoding scheme. The rate-regions that are achieved by the two schemes are characterized in terms of feasibility problems. Both inner bounds are shown to be the capacity region for networks with three (or fewer) public and any number of private receivers. Although the inner bounds are not comparable in general, it is shown through an example that the region achieved by the block Markov encoding scheme may strictly include the region achieved by the pre-encoding/linear superposition scheme. Optimality results are founded on the general framework of Balister and Bollobás (2007) for sub-modularity of the entropy function. An equivalent graphical representation is introduced and a lemma is proved that might be of independent interest. Motivated by the connections between combination networks and broadcast channels, a new block Markov encoding scheme is proposed for broadcast channels with two nested messages. The rate-region that is obtained includes the previously known rate-regions. It remains open whether this inclusion is strict.

This paper presents exact capacity characterizations for the case, when a principal, Alice, wants to securely send a message to another principal, Bob, over three network configurations: the parallel edges network, the V-network, and the triangle network. We assume that: 1) a passive eavesdropper, Eve, overhears any one edge in the network; 2) each edge corresponds to an independent broadcast packet erasure channel with arbitrary erasure probabilities; and 3) all legitimate nodes can publicly but causally acknowledge whether they received each packet or not. We develop optimal achievability schemes that are expressed as linear programs (LPs) and share a two-phase structure, where at the first phase, we create secret keys, and at the second phase, we use them to encrypt the transmitted message. Our outer bounds are also expressed through LP formulations. We prove that our schemes are optimal by showing that the optimal solution of the outer bound LP and the optimal solution of the achievability scheme LP coincide.

Caching of popular content during off-peak hours is a strategy to reduce network loads during peak hours. Recent work has shown significant benefits of designing such caching strategies not only to locally deliver the part of the content, but also to provide coded multicasting opportunities even among users with different demands. Exploiting both of these gains was shown to be approximately optimal for caching systems with a single layer of caches. Motivated by practical scenarios, we consider, in this paper, a hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer; the second approach provides coded multicasting opportunities across multiple layers. By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both the layers can simultaneously operate at approximately the minimum rate.

Embedded sensing systems are pervasively used in life- and security-critical systems such as those found in airplanes, automobiles, and healthcare. Traditional security mechanisms for these sensors focus on data encryption and other post-processing techniques, but the sensors themselves often remain vulnerable to attacks in the physical/analog domain. If an adversary manipulates a physical/analog signal prior to digitization, no amount of digital security mechanisms after the fact can help. Fortunately, nature imposes fundamental constraints on how these analog signals can behave. This work presents PyCRA, a physical challenge-response authentication scheme designed to protect active sensing systems against physical attacks occurring in the analog domain. PyCRA provides secure active sensing by continually challenging the surrounding environment via random but deliberate physical probes. By analyzing the responses to these probes, the system is able to ensure that the underlying physics involved are not violated, providing an authentication mechanism that not only detects malicious attacks but provides resilience against them. We demonstrate the effectiveness of PyCRA in detecting and mitigating attacks through several case studies using two sensing systems: (1) magnetic sensors like those found on gear and wheel speed sensors in robotics and automotive, and (2) commercial Radio Frequency Identification (RFID) tags used in many security-critical applications. In doing so, we evaluate both the robustness and the limitations of the PyCRA security scheme, concluding by outlining practical considerations as well as further applications for the proposed authentication mechanism.

Emerging heterogeneous wireless architectures consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). We design a coded caching-and-delivery scheme for such architectures that equips APs with storage, enabling content pre-fetching prior to knowing user demands. Users requesting content are served by connecting to local APs with cached content, as well as by listening to a BS broadcast transmission. For any given content popularity profile, the goal is to design the caching-and-delivery scheme so as to optimally trade off the transmission cost at the BS against the storage cost at the APs and the user cost of connecting to multiple APs. We design a coded caching scheme for non-uniform content popularity that dynamically allocates user access to APs based on requested content. We demonstrate the approximate optimality of our scheme with respect to information-theoretic bounds. We numerically evaluate it on a YouTube dataset and quantify the trade-off between transmission rate, storage, and access cost. Our numerical results also suggest the intriguing possibility that, to gain most of the benefits of coded caching, it suffices to divide the content into a small number of popularity classes.

When a multi-antenna (MIMO) base-station operates in full-duplex mode, multiple uplink and downlink streams can be supported simultaneously in the same frequency band. However, the inter-mobile interference from uplink streams to the downlink streams can limit the system performance. In this paper, we first characterize the degrees-of-freedom of a multiuser MIMO (MU-MIMO) full-duplex network with half-duplex mobile clients, and derive the regimes where the inter-mobile interference can be mitigated to yield significant gains over the half-duplex counterpart. The achievability is based on interference alignment and requires full channel-state information at the transmitter (CSIT). Next, we study the case with partial CSIT where only the base-station acquires downlink channel values to avoid collecting network-wide CSIT at all transmitters in the system. We show that the key to achieving the sum degrees-of-freedom upper bound with only partial CSIT is the ability of the base-station to switch antenna modes that can be realized via reconfigurable antennas.

It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. This has also been extended to the case when content has non-uniform popularity through several models. In this paper we focus on a multi-level popularity model, where content is divided into levels based on popularity. We consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup). When the capacity approximation is universal (independent of number of popularity levels as well as number of users, files and caches), we demonstrate a dichotomy in the order-optimal strategies for these two extreme cases. In the multi-user case, sharing memory among the levels is order-optimal, whereas for the single-user case clustering popularity levels and allocating all the memory to them is the order-optimal scheme. In proving these results, we develop new information-theoretic lower bounds for the problem.

We study opportunistic scheduling and the sum capacity of cellular networks with a full-duplex multi-antenna base station and a large number of single-antenna half-duplex users. Simultaneous uplink and downlink over the same band results in uplink-to-downlink interference, degrading performance. We present a simple opportunistic joint uplink-downlink scheduling algorithm that exploits multiuser diversity and treats interference as noise. We show that in homogeneous networks, our algorithm achieves the same sum capacity as what would have been achieved if there was no uplink-to-downlink interference, asymptotically in the number of users. The algorithm does not require interference CSI at the base station or uplink users. It is also shown that for a simple class of heterogeneous networks without sufficient channel diversity, it is not possible to achieve the corresponding interference-free system capacity. We discuss the potential for using device-to-device side-channels to overcome this limitation in heterogeneous networks.

We study oblivious transfer (OT) between Alice and Bob in the presence of an eavesdropper Eve over a degraded wiretapped binary erasure channel from Alice to Bob and Eve. In addition to the privacy goals of oblivious transfer between Alice and Bob, we require privacy of Alice and Bob's private data from Eve. In previous work we derived the OT capacity (in the honest-but-curious model) of the wiretapped binary independent erasure channel where the erasure processes of Bob and Eve are independent. Here we derive a lower bound on the OT capacity in the same secrecy model when the wiretapped binary erasure channel is degraded in favour of Bob.

Motivated by the need to secure cyber-physical systems against attacks, we consider the problem of estimating the state of a noisy linear dynamical system when a subset of sensors is arbitrarily corrupted by an adversary. We propose a secure state estimation algorithm and derive (optimal) bounds on the achievable state estimation error. In addition, as a result of independent interest, we give a coding theoretic interpretation for prior work on secure state estimation against sensor attacks in a noiseless dynamical system.

We investigate whether uncoded schemes are optimal for Gaussian sources on multiuser Gaussian channels. Particularly, we consider two problems: the first is to send correlated Gaussian sources on a Gaussian broadcast channel where each receiver is interested in reconstructing only one source component (or one specific linear function of the sources) under the mean squared error distortion measure; the second is to send correlated Gaussian sources on a Gaussian multiple-access channel, where each transmitter observes a noisy combination of the source, and the receiver wishes to reconstruct the individual source components (or individual linear functions) under the mean squared error distortion measure. It is shown that when the channel parameters match certain general conditions, the induced distortion tuples are on the boundary of the achievable distortion region, and thus optimal. Instead of following the conventional approach of attempting to characterize the achievable distortion region, we ask the question whether and how a match can be effectively determined. This decision problem formulation helps to circumvent the difficult optimization problem often embedded in region characterization problems, and it also leads us to focus on the critical conditions in the outer bounds that make the inequalities become equalities, which effectively decouples the overall problem into several simpler sub-problems.

One of the most widely-known techniques for securing a message from eavesdropping, is the famous one-time pad. Although the one-time pad offers unconditional security, it has limited applicability today, because it requires that to communicate, two parties already share a key that is not known by the eavesdropper and has size equal to the message. In this review paper we present a line of work that explores how we can efficiently share keys securely from an eavesdropper, and thus communicate using a one-time pad like approach. The basic idea is to exploit new opportunities that wireless networks offer, such as the fact that we have multiple paths, the fact that we have packet losses, and the availability of ACK/NACK feedback.

Secure network coding assumes that the underlying network channels are error-free; thus, if our channels introduce errors, we need to first apply a channel code to correct them, and then build security on top of the resulting error-free network. In this paper, we develop achievability protocols and outer bounds for the secure network coding setting, where the edges are subject to packet erasures, and public feedback of the channel state is available to both Eve and the legitimate network nodes. We show that by leveraging erasures and feedback, we can achieve secrecy rates that are in some cases multiple times higher than the alternative of separate channel-error-correction followed by secure network coding; moreover, we develop outer bounds and prove optimality of our proposed schemes in some special cases.

We consider a 1-to-K communication scenario, where a source transmits private messages to K receivers through a broadcast erasure channel, and the receivers feedback strictly, causally, and publicly their channel states after each transmission. We explore the achievable rate region when we require that the message to each receiver remains secret-in the information theoretical sense-from all the other receivers. We characterize the capacity of secure communication in all the cases where the capacity of the 1-to-K communication scenario without the requirement of security is known. As a special case, we characterize the secret-message capacity of a single receiver point-to-point erasure channel with public state-feedback in the presence of a passive eavesdropper. We find that in all the cases where we have an exact characterization, we can achieve the capacity using linear complexity two-phase schemes: in the first phase, we create appropriate secret keys, and in the second phase, we use them to encrypt each message. We find that the amount of key we need is smaller than the size of the message, and equal to the amount of encrypted message the potential eavesdroppers jointly collect. Moreover, we prove that a dishonest receiver that provides deceptive feedback cannot diminish the rate experienced by the honest receivers. We also develop a converse proof which reflects the two-phase structure of our achievability scheme. As a side result, our technique leads to a new outer bound proof for the nonsecure communication problem.

We investigate how to exploit intermittent feedback for interference management by studying the two-user Gaussian interference channel (IC). We approximately characterize (within a universal constant) the capacity region for the Gaussian IC with intermittent feedback. We exactly characterize the capacity region of the linear deterministic version of the problem, which gives us insight into the Gaussian problem. We find that the characterization only depends on the forward channel parameters and the marginal probability distribution of each feedback link. The result shows that passive and unreliable feedback can be harnessed to provide multiplicative capacity gain in Gaussian ICs. We find that when the feedback links are active with sufficiently large probabilities, the perfect feedback sum-capacity is achieved to within a constant gap. In contrast to other schemes developed for IC with feedback, our achievable scheme makes use of quantize-map-and-forward to relay the information obtained through feedback, performs forward decoding, and does not use structured codes. We also develop new outer bounds enabling us to obtain the (approximate) characterization of the capacity region.

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

Physical layer cooperation of a source with a relay can significantly boost the performance of a wireless connection. However, the best practical relaying scheme can vary depending on the relative strengths of the channels that connect the source, relay and destination. This paper proposes and evaluates QUILT, a system for physical-layer relaying that seamlessly adapts to the underlying network configuration to achieve competitive or better performance as compared to the best current approaches. QUILT combines on-demand, opportunistic use of Decode-Forward (DF) or Quantize-Map-Forward (QMF) followed by interleaving at the relay, with hybrid decoding at the destination that extracts information from received frames even if these are not decodable. We theoretically quantify how our design choices for QUILT affect the system performance. We also deploy QUILT on the WarpLab software radio platform, and show through over-the-air experiments up to 5 times FER improvement over the next best cooperative protocol.

We characterize the secret message capacity of the triangle network, that consists of a source, a relay and a destination connected through orthogonal erasure channels. A passive eavesdropper, Eve, wiretaps any one of the three channels. The source and the relay can each generate unlimited private randomness; the relay and the destination can publicly provide strictly causal channel state information. Our achievable scheme is expressed through a linear program (LP) with 11 inequalities that captures a minimal set of secret key generation methods and the use of them for message encryption. Our outer bound is expressed also through a linear program, in this case with 41 constraints, constructed from general information inequalities. We prove that the optimal value of the outer bound LP is no larger than that of the scheme LP, which implies that the solution of the achievable scheme LP is the capacity. We find that equipping the relay with private randomness increases the secrecy rate by more than 40% in some cases and that cut-set bounds, directly applied in the network, are not always tight. Because the derivation of the inner and outer bound are both lengthy, we describe in this paper the achievability scheme, outline the outer bound, and provide the full derivations online [1]. We also make available Matlab functions that take as input the erasure probabilities and evaluate the inner and outer bounds.

Recent work has demonstrated that, for content caching, joint design of storage and delivery can yield significant benefits over conventional caching approaches. This is based on storing content in the caches in a way that creates coded-multicast opportunities even among users with different demands. Such a coded-caching scheme has been shown to be order-optimal for a caching system with single-level content, i.e., one where all content is uniformly popular. In this work, we consider a system with content divided into multiple levels, based on varying degrees of popularity. The main contribution of this work is the derivation of an information-theoretic outer bound for the multi-level setup, and the demonstration that, under some natural regularity conditions, a memory-sharing scheme, which operates each level in isolation according to a single-level coded caching scheme, is in fact order-optimal with respect to this outer bound.

It has recently been demonstrated that for single-layer cache networks, jointly designing caching and delivery can enable significant benefits over conventional caching. This was based on strategically designing the cached content to induce coded multicasting opportunities even among users with different demands and without foreknowledge of the user demands. In this work, we extend this coded caching approach to a multi-hop hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer (through decoding and forwarding); the second approach provides coded multicasting opportunities across multiple layers (through strategic forwarding without decoding). By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate.

We consider oblivious transfer between Alice and Bob in the presence of an eavesdropper Eve when there is a broadcast channel from Alice to Bob and Eve. In addition to the secrecy constraints of Alice and Bob, Eve should not learn the private data of Alice and Bob. When the broadcast channel consists of two independent binary erasure channels, we derive the oblivious transfer capacity for both 2-privacy (where the eavesdropper may collude with either party) and 1-privacy (where there are no collusions).

We study parallel symmetric 2-user interference channels when the interference is bursty and feedback is available from the respective receivers. Presence of interference in each subcarrier is modeled as a memoryless Bernoulli random state. The states across subcarriers are drawn from an arbitrary joint distribution with the same marginal probability for each subcarrier and instantiated i.i.d. over time. For the linear deterministic setup, we give a complete characterization of the capacity region. For the setup with Gaussian noise, we give outer bounds and a tight generalized degrees of freedom characterization. We propose a novel helping mechanism which enables subcarriers in very strong interference regime to help in recovering interfered signals for subcarriers in strong and weak interference regimes. Depending on the interference and burstiness regime, the inner bounds either employ the proposed helping mechanism to code across subcarriers or treat the subcarriers separately. The outer bounds demonstrate a connection to a subset entropy inequality by Madiman and Tetali [4].

We study oblivious transfer (OT) using a binary erasure broadcast channel from Alice to Bob and Charlie. Alice wants to establish independent OTs with Bob and Charlie with 2-privacy, i.e., where secrecy needs to be maintained even against pairs of parties in addition to against parties working on their own. We give an achievable rate-region in the honest-but-curious setting and show its optimality for a range of erasure probabilities.

We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal in two general scenarios and is approximately optimal in a third scenario. The two scenarios for which separation is optimal complement each other: the first is when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, but the channels in this network are synchronized, orthogonal, and memoryless point-to-point channels; the second is when the memoryless sources are mutually independent, each of which is to be reconstructed only at one destination within a certain distortion, but the channels are general, including multi-user channels, such as multiple access, broadcast, interference, and relay channels, possibly with feedback. The third scenario, for which we demonstrate approximate optimality of source-channel separation, generalizes the second scenario by allowing each source to be reconstructed at multiple destinations with different distortions. For this case, the loss from optimality using the separation approach can be upper-bounded when a difference distortion measure is taken, and in the special case of quadratic distortion measure, this leads to universal constant bounds.

We consider the problem where a group of wireless nodes, connected to the same broadcast domain, want to create pairwise secrets, in the presence of an adversary Eve, who tries to listen in and steal these secrets. Existing solutions assume that Eve cannot perform certain computations (e.g., large-integer factorization) in useful time. We ask the question: can we solve this problem without assuming anything about Eve's computational capabilities? We propose a simple secret-agreement protocol, where the wireless nodes keep exchanging bits until they have agreed on pairwise secrets that Eve cannot reconstruct with very high probability. Our protocol relies on Eve's limited network presence (the fact that she cannot be located at an arbitrary number of points in the network at the same time), but assumes nothing about her computational capabilities. We formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure (it leaks zero information to Eve about the secrets). Using a small wireless testbed of smart-phones, we provide experimental evidence that it is feasible for 5 nodes to create thousands of secret bits per second, with their secrecy being independent from the adversary's capabilities.

Encoding schemes for broadcasting two nested message sets are studied. We start with a simple class of deterministic broadcast channels for which (variants of) linear superposition coding are optimal in several cases [1], [2]. Such schemes are sub-optimal in general, and we propose a block Markov encoding scheme which achieves (for some deterministic channels) rates not achievable by the previous schemes in [1], [2]. We adapt this block Markov encoding scheme to general broadcast channels, and show that it achieves a rate-region which includes the previously known rate-regions1.

We study the channel coding problem when errors and uncertainty occur in the encoding process. For simplicity we assume the channel between the encoder and the decoder is perfect. Focusing on linear block codes, we model the encoding uncertainty as erasures on the edges in the factor graph of the encoder generator matrix. We first take a worst-case approach and find the maximum tolerable number of erasures for perfect error correction. Next, we take a probabilistic approach and derive a sufficient condition on the rate of a set of codes, such that decoding error probability vanishes as blocklength tends to infinity. In both scenarios, due to the inherent asymmetry of the problem, we derive the results from first principles, which indicates that robustness to encoding errors requires new properties of codes different from classical properties.

We investigate how to exploit intermittent feedback for interference management. Focusing on the two-user linear deterministic interference channel, we completely characterize the capacity region. We find that the characterization only depends on the forward channel parameters and the marginal probability distribution of each feedback link. The scheme we propose makes use of block Markov encoding and quantize-map-and-forward at the transmitters, and backward decoding at the receivers. Matching outer bounds are derived based on novel genie-aided techniques. As a consequence, the perfect-feedback capacity can be achieved once the two feedback links are active with large enough probabilities.

We study the problem of secure message multicasting over graphs in the presence of a passive (node) adversary who tries to eavesdrop in the network. We show that use of feedback, facilitated through the existence of cycles or undirected edges, enables higher rates than possible in directed acyclic graphs of the same mincut. We demonstrate this using code constructions for canonical combination networks (CCNs). We also provide general outer bounds as well as schemes for node adversaries over CCNs.

We study opportunistic interference management when there is bursty interference in parallel 2-user linear deterministic interference channels. A degraded message set communication problem is formulated to exploit the burstiness of interference in M subcarriers allocated to each user. We focus on symmetric rate requirements based on the number of interfered subcarriers rather than the exact set of interfered subcarriers. Inner bounds are obtained using erasure coding, signal-scale alignment and Han-Kobayashi coding strategy. Tight outer bounds for a variety of regimes are obtained using the El Gamal-Costa injective interference channel bounds and a sliding window subset entropy inequality [7]. The result demonstrates an application of techniques from multilevel diversity coding to interference channels. We also conjecture outer bounds indicating the sub-optimality of erasure coding across subcarriers in certain regimes.

We explore the benefit of feedback for physical layer interference management in wireless networks without centralized upper layer control mechanisms. Lack of coordination in the upper layer could make the interference experienced in the physical layer bursty. To understand how to harness such burstiness with feedback, we investigate a two-user bursty interference channel (IC), where the presence of interference is governed by a Bernoulli random state. We completely characterize the capacity region of the symmetric two-user linear deterministic bursty IC with feedback. The proposed two-phase scheme exploits feedback either for refining the previous interfered reception or for relaying additional information to the legitimate receiver of the other user. Matching outer bounds are derived by novel techniques that take the effect of delayed state information into account. We also use insights from the deterministic case to characterize the approximate symmetric capacity for the symmetric Gaussian bursty IC with feedback in the weak interference regime.

We investigate the problem of secure communication in a simple network with three communicating parties, two distributed sources who communicate over orthogonal channels to one destination node. The cooperation between the sources is restricted to a rate limited common random source they both observe. The communication channels are erasure channels with strictly causal channel state information of the destination available publicly. A passive adversary is present in the system eavesdropping on any one of the channels. We design a linear scheme that ensures secrecy against the eavesdropper. By deriving an outer bound for the problem we prove that the scheme is optimal in certain special cases.

Feasibility of full-duplex opens up the possibility of applying it to cellular networks to operate uplink and downlink simultaneously for multiple users. However, simultaneous operation of uplink and downlink poses a new challenge of intra-cell inter-node interference. In this paper, we identify scenarios where inter-node interference can be managed to provide significant gain in degrees of freedom over the conventional half-duplex cellular design.

Current security systems often rely on the adversary's computational limitations. Wireless networks offer the opportunity for a different, complementary kind of security, which relies on the adversary's limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We present a system that leverages this opportunity to enable n wireless nodes to create a shared secret S, in a way that an eavesdropper, Eve, obtains very little information on S. Our system consists of two steps: (1) The nodes transmit packets following a special pattern, such that Eve learns very little about a given fraction of the transmitted packets. This is achieved through a combination of beam forming (from many different sources) and wiretap codes. (2) The nodes participate in a protocol that reshuffles the information known to each node, such that the nodes end up sharing a secret that Eve knows very little about. Our protocol is easily implementable in existing wireless devices and scales well with the number of nodes; these properties are achieved through a combination of public feedback, broadcasting, and network coding. We evaluate our system through a 5-node testbed. We demonstrate that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.

We present the design and experimental evaluation of a wireless system that exploits relaying in the context of WiFi. We opt for WiFi given its popularity and wide spread use for a number of applications, such as smart homes. Our testbed consists of three nodes, a source, a relay and a destination, that operate using the physical layer procedures of IEEE802.11. We deploy three main competing strategies that have been proposed for relaying, Decode-and-Forward (DF), Amplify-and-Forward (AF) and Quantize-Map-Forward (QMF). QMF is the most recently introduced of the three, and although it was shown in theory to approximately achieve the capacity of arbitrary wireless networks, its performance in practice had not been evaluated. We present in this work experimental results---to the best of our knowledge, the first ones---that compare QMF, AF and DF in a realistic indoor setting. We find that QMF is a competitive scheme to the other two, offering in some cases up to 12% throughput benefits and up to 60% improvement in frame error-rates over the next best scheme.

We consider the problem of distributed computation of a target function over a two-user deterministic multiple-access channel. If the target and channel functions are matched (i.e., compute the same function), significant performance gains can be obtained by jointly designing the communication and computation tasks. However, in most situations there is mismatch between these two functions. In this work, we analyze the impact of this mismatch on the performance gains achievable with joint communication and computation designs over separation-based designs. We show that for most pairs of target and channel functions there is no such gain, and separation of communication and computation is optimal.

We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help ofNrelays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of orderNbits and up to a multiplicative gap of orderN2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric GaussianN-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains and, unlike the best previously known result, are also independent of the number of relaysNin the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as in the high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound. We also present approximation results for the asymmetric GaussianN-relay diamond network. In particular, we show that bursty amplify-and-forward combined with optimal relay selection achieves a rate within a factorO(log4(N)) of capacity with preconstant in the order notation independent of the channel gains.

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

Current security systems typically rely on the adversary's computational limitations (e.g., the fact that it cannot invert a hash function or perform large-integer factorization). Wireless networks offer the opportunity for a different, complementary kind of security, which relies not on the adversary's computational limitations, but on its limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We take a first step toward designing and building a wireless security system that leverages this opportunity: We consider the problem where a group of n nodes, connected to the same broadcast wireless network, want to agree on a shared secret (e.g., an encryption key), in the presence of an adversary Eve who tries to listen in and steal the secret. We propose a secret-agreement protocol, where the n nodes of the group keep exchanging bits until they have all agreed on a bit sequence that Eve cannot reconstruct (with very high probability). We provide experimental evidence---to the best of our knowledge, the first one---that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.

In mutiterminal communication systems, signals carrying messages meant for different destinations are often observed together at any given destination receiver. Han and Kobayashi (1981) proposed a receiving strategy which performs a joint unique decoding of messages of interest along with a subset of messages which are not of interest. It is now well-known that this provides an achievable region which is, in general, larger than if the receiver treats all messages not of interest as noise. Nair and El Gamal (2009) and Chong, Motani, Garg, and El Gamal (2008) independently proposed a generalization called indirect or non-unique decoding where the receiver uses the codebook structure of the messages to only uniquely decode its messages of interest. Indirect (non-unique) decoding has since been used in various scenarios. The main result in this paper is to provide an interpretation and a systematic proof technique for why indirect decoding, in all known cases where it has been employed, can be replaced by a particularly designed joint unique decoding strategy, without any penalty from a rate region viewpoint1.

Consider a source, Alice, broadcasting private messages to multiple receivers through a broadcast erasure channel; users send back to Alice public feedback that she causally uses to decide the coding strategy for her following transmissions. Recently, the multiple unicast capacity region for this problem has been exactly characterized for a number of special cases; namely the 2-user, 3-user, symmetric K-user, and one-sidedly fair K-user [1], [2]. In this paper, we show that for all the cases where such characterizations exist, we can also optimally characterize the “secure” communication rates, where the message that Alice transmits to each user is information theoretically secure from the other users, even if these collude. We show that a simple, two-phase strategy, where appropriate amounts of secret keys are first generated and then consumed, matches a new outer bound we derive.

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

In this paper we study the two unicast information flow problem over layered Gaussian networks with arbitrary number of nodes and connectivity, under the model of delayed channel state information (CSI) at transmitters and instantaneous CSI at receivers. We show that similar to the case with instantaneous CSI at transmitters (CSIT), the degrees of freedom (DoF) region is strictly larger than the time-sharing DoF region if and only if there is no omniscient node, definition of which only depends on the topology of the network. Moreover, as in the case with instantaneous CSIT, 2/3 DoF per user is always achievable when there is no omniscient node in the network.

We present a method to integrate the Quantize-Map-Forward (QMF) relaying scheme [1] into the standard LTE operation, for a two-relay diamond network configuration. Our approach implements QMF using mainly existing LTE modules and functionalities, and results in minimal changes in the standard link-layer LTE operation. In particular, the destination operation is only affected in that we adapt the log-likelihood ratio (LLR) calculations at the decoder input to take into account the existence of relays; thus, the decoding complexity and operations (apart the LLR calculations) are not modified. We report extensive performance evaluations of our scheme using the OpenAirInterface (OAI) link-level simulation tools.

In this paper, we study delivery of two nested message sets over combination networks with an arbitrary number of receivers, where a subset of receivers (public receivers) demand only the lower priority message and a subset of receivers (private receivers) demand both the lower and the higher priority messages. We give a complete rate region characterization over combination networks with three public and any number of private receivers, where achievability is through linear coding. Our encoding scheme is general and characterizes an achievable region for arbitrary number of public and private receivers.

We study the secret-key capacity in a joint source-channel coding setup-the terminals are connected over a discrete memoryless channel and have access to side information, modelled as a pair of discrete memoryless source sequences. As our main result, we establish the upper and lower bounds on the secret-key capacity. In the lower bound expression, the equivocation terms of the source and channel components are functionally additive even though the coding scheme generates a single secret-key by jointly taking into account the source and channel equivocations. Our bounds coincide, thus establishing the capacity, when the underlying wiretap channel can be decomposed into a set of independent, parallel, and reversely degraded channels. For the case of parallel Gaussian channels and jointly Gaussian sources we show that Gaussian codebooks achieve the secret-key capacity. In addition, when the eavesdropper also observes a correlated side information sequence, we establish the secret-key capacity when both the source and channel of the eavesdropper are a degraded version of the legitimate receiver. We finally also treat the case when a public discussion channel is available, propose a separation based coding scheme, and establish its optimality when the channel output symbols of the legitimate receiver and eavesdropper are conditionally independent given the input.

Systems that employ network coding for content distribution convey to the receivers linear combinations of the source packets. If we assume randomized network coding, during this process, the network nodes collect random subspaces of the space spanned by the source packets. We establish several fundamental properties of the random subspaces induced in such a system and show that these subspaces implicitly carry topological information about the network and its state that can be passively collected and inferred. We leverage this information toward a number of applications that are interesting in their own right, such as topology inference, bottleneck discovery in peer-to-peer systems, and locating Byzantine attackers. We thus argue that randomized network coding, apart from its better known properties for improving information delivery rate, can additionally facilitate network management and control.

In this paper, we investigate the maximum achievable sum-rate of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we find the constrained sum-capacity and its achievable schemes with the minimum number of messages, first in symmetric channels, and then in general asymmetric channels. We show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either of the two users is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We provide two algorithms to translate the optimal schemes in the deterministic channel model to the Gaussian channel model. We also derive two upper bounds on the maximum achievable sum-rate of the Gaussian Han-Kobayashi schemes, which automatically upper bound the maximum achievable sum-rate using successive decoding of Gaussian codewords. Numerical evaluations show that, similar to the deterministic channel results, the maximum achievable sum-rate with successive decoding in the Gaussian channels oscillates between that with Han-Kobayashi schemes and that with single message schemes.

We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains, and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound.

We consider a group of m trusted nodes that aim to create a shared secret key K, using a state-dependent wireless broadcast channel that exists from one of the honest nodes to the rest of the nodes including a passive eavesdropper Eve. All of the trusted nodes can also discuss over a cost-free and unlimited rate public channel which is also observed by Eve. For this setup, we develop an information-theoretically secure secret key agreement protocol. We show the optimality of this protocol for linear deterministic wireless broadcast channels as well as in the high-SNR regime for wireless channels with large dynamic range over channel states.

In this paper, we investigate the sum-capacity of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either user is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We translate the optimal schemes in the deterministic channel model to the Gaussian channel model, and also derive two upper bounds on the constrained sum-capacity. Numerical evaluations show that the constrained sum-capacity in the Gaussian channels oscillates between the sum-capacity with Gaussian Han-Kobayashi schemes and that with single message schemes.

We characterize the secret message capacity of a wiretapped erasure channel where causal channel state information of the honest nodes is publicly available. In doing so, we establish an intimate connection between message secrecy and secret key generation for the same channel setup. We propose a linear coding scheme that has polynomial encoding/decoding complexity, and prove a converse that shows the optimality of our scheme. Our work also demonstrates the value of causal public feedback, which has previously been shown for the secret key generation problem.

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

This paper addresses the problem of finding the nearest neighbor (or one of the $R$-nearest neighbors) of a query object $q$ in a database of $n$ objects, when we can only use a comparison oracle. The comparison oracle, given two reference objects and a query object, returns the reference object most similar to the query object. The main problem we study is how to search the database for the nearest neighbor (NN) of a query, while minimizing the questions. The difficulty of this problem depends on properties of the underlying database. We show the importance of a characterization: \emph{combinatorial disorder} $D$ which defines approximate triangle inequalities on ranks. We present a lower bound of $\Omega(D\log \frac{n}{D}+D^2)$ average number of questions in the search phase for any randomized algorithm, which demonstrates the fundamental role of $D$ for worst case behavior. We develop a randomized scheme for NN retrieval in $O(D^3\log^2 n+ D\log^2 n \log\log n^{D^3})$ questions. The learning requires asking $O(n D^3\log^2 n+ D \log^2 n \log\log n^{D^3})$ questions and $O(n\log^2n/\log(2D))$ bits to store.

Rate and diversity impose a fundamental trade-off in communications. This trade-off was investigated for flat-fading channels in as well as for Inter-symbol Interference (ISI) channels in . A different point of view was explored in where high-rate codes were designed so that they have a high-diversity code embedded within them. These diversity embedded codes were investigated for flat fading channels both from an information-theoretic viewpoint and from a coding theory viewpoint in . In this paper, we explore the use of diversity embedded codes for inter-symbol interference channels. In particular the main result of this paper is that the diversity multiplexing trade-off for fading MISO/SIMO/SISO ISI channels is indeed successively refinable. This implies that for fading ISI channels with a single degree of freedom one can embed a high diversity code within a high rate code without any performance loss (asymptotically). This is related to a deterministic structural observation about the asymptotic behavior of frequency response of channel with respect to fading strength of time domain taps as well as a coding scheme to take advantage of this observation.

We study the capacity of secret-key agreement over a wiretap channel with state parameters. The transmitter, the legitimate receiver, and the eavesdropper are connected by a discrete memoryless wiretap channel with a memoryless state sequence. The transmitter and the legitimate receiver generate a secret-key that must be concealed from the eavesdropper. We assume that the state sequence is known noncausally to the transmitter and no public discussion channel is available. We derive lower and upper bounds on the secret-key capacity. The lower bound involves a source-channel codebook for constructing a common reconstruction sequence at the legitimate terminals and then mapping this sequence to a secret-key using a secret-key codebook. For the special case of Gaussian channels with additive interference (secret-keys from dirty paper channel) our bounds differ by 0.5 bit/symbol and coincide in the high signal-to-noise-ratio and high interference-to-noise-ratio regimes. In another special case-symmetric channel state information (CSI)-when the legitimate receiver is also revealed the state sequence, we establish optimality of our lower bound. In addition, only causal side information at the transmitter and the receiver suffices to attain the secret-key capacity in the case of symmetric CSI.

In a wireless network with a single source and a single destination and an arbitrary number of relay nodes, what is the maximum rate of information flow achievable? We make progress on this long standing problem through a two-step approach. First, we propose a deterministic channel model which captures the key wireless properties of signal strength, broadcast and superposition. We obtain an exact characterization of the capacity of a network with nodes connected by such deterministic channels. This result is a natural generalization of the celebrated max-flow min-cut theorem for wired networks. Second, we use the insights obtained from the deterministic analysis to design a new quantize-map-and-forward scheme for Gaussian networks. In this scheme, each relay quantizes the received signal at the noise level and maps it to a random Gaussian codeword for forwarding, and the final destination decodes the source's message based on the received signal. We show that, in contrast to existing schemes, this scheme can achieve the cut-set upper bound to within a gap which is independent of the channel parameters. In the case of the relay channel with a single relay as well as the two-relay Gaussian diamond network, the gap is 1 bit/s/Hz. Moreover, the scheme is universal in the sense that the relays need no knowledge of the values of the channel parameters to (approximately) achieve the rate supportable by the network. We also present extensions of the results to multicast networks, half-duplex networks, and ergodic networks.

In this paper, we study a Gaussian relay-interference network, in which relay (helper) nodes are to facilitate competing information flows between different source-destination pairs. We focus on two-stage relay-interference networks where there are weak cross links, causing the networks to behave like a chain ofZGaussian channels. Our main result is an approximate characterization of the capacity region for such ZZ and ZS networks. We propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This scheme allows for over-the-air interference removal, without the transmitters having complete access the interfering signals. This scheme in conjunction a new network decomposition technique provides the approximate characterization. Our analysis of these Gaussian networks is based on insights gained from an exact characterization of the corresponding linear deterministic model.

We consider the problem of multicasting information from a source to a set of receivers over a network where intermediate network nodes perform randomized linear network coding operations on the source packets. We propose a channel model for the noncoherent network coding introduced by Koetter and Kschischang in , that captures the essence of such a network operation, and calculate the capacity as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length. This model and the results also allow us to give guidelines on when subspace coding is beneficial for the proposed model and by how much, in comparison to a coding vector approach, from a capacity viewpoint. We extend our results to the case of multiple source multicast that creates a virtual multiple access channel.

We consider the joint source-channel coding problem of sending a Gaussian source on a K-user Gaussian broadcast channel with bandwidth mismatch. A new outer bound to the achievable distortion region is derived using the technique of introducing more than one additional auxiliary random variable, which was previously used to derive sum-rate lower bound for the symmetric Gaussian multiple description problem. By combining this outer bound with the achievability result based on source-channel separation, we provide approximate characterizations of the achievable distortion region within constant multiplicative factors. Furthermore, we show that the results can be extended to general broadcast channels, and the performance of the source-channel separation based approach is also within the same constant multiplicative factors of the optimum.

We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over bandwidth-matched Gaussian broadcast channels, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient. We further show that in this joint source channel coding setting, the Gaussian scenario is the worst scenario among the sources and channel noises with the same covariances.

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

In this paper we consider information-theoretically secure communication between two special nodes (“source” and “destination”) in a memoryless network with authenticated relays, where the secrecy is with respect to a class of eavesdroppers. We develop achievable secrecy rates when authenticated relays also help increase secrecy rate by inserting noise into the network.

We consider the optimality of source-channel separation in networks, and show that such a separation approach is optimal or approximately optimal for a large class of scenarios. More precisely, for lossy coding of memoryless sources in a network, when the sources are mutually independent, and each source is needed only at one destination (or at multiple destinations at the same distortion level), the separation approach is optimal; for the same setting but each source is needed at multiple destinations under a restricted class of distortion measures, the separation approach is approximately optimal, in the sense that the loss from optimum can be upper-bounded. The communication channels in the network are general, including various multiuser channels with finite memory and feedback, the sources and channels can have different bandwidths, and the sources can be present at multiple nodes.

We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over a bandwidth-matched Gaussian broadcast channel, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient.

In this paper we consider communication from a source to a destination over a wireless network with the help of a set of authenticated relays. We focus on a special “diamond” network, where there is no direct link between the source and the destination; however the relay nodes help to establish such a communication. There is a single adversarial node which injects signals to disrupt this communication. Like the source, it can only influence the destination through the relays. We develop an approximate characterization of the reliable transmission rate in the presence of such an adversary. This is done by developing an outer bound, and demonstrating an achievable strategy that is within a constant number of bits of the outer bound, regardless of the channel values. A deterministic version of the same problem is solved exactly, yielding insights which are used in the approximate characterization.

In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occurred, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how communication should happen in such identity-aware sensor networks. We calculate theoretical performance bounds for this type of communication, where 'performance' refers to the number of transmitted bits. We propose a communication protocol, where the identity and message of each source are specified jointly using subspace coding. We show through analysis and simulation that our protocol's performance is close to optimal and compare it to the performance of a traditional protocol, where identity and message are specified separately.

Providing real-time multimedia services over a besteffort network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. The framework is based on the theoretical modeling where we consider two descriptions and high source coding rate region approximated within small constants. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that we need greater redundancy in the MD streams to protect against such failures. However, one surprising aspect of our study reveals that for large number of users who compete for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

We consider the asymmetric multilevel diversity (A-MLD) coding problem, where a set of2K- 1 information sources, ordered in a decreasing level of importance, is encoded intoKmessages (or descriptions). There are2K- 1 decoders, each of which has access to a nonempty subset of the encoded messages. Each decoder is required to reproduce the information sources up to a certain importance level depending on the combination of descriptions available to it. We obtain a single letter characterization of the achievable rate region for the 3-description problem. In contrast to symmetric multilevel diversity coding, source-separation coding is not sufficient in the asymmetric case, and ideas akin to network coding need to be used strategically. Based on the intuitions gained in treating the A-MLD problem, we derive inner and outer bounds for the rate region of the asymmetric Gaussian multiple description (MD) problem with three descriptions. Both the inner and outer bounds have a similar geometric structure to the rate region template of the A-MLD coding problem, and, moreover, we show that the gap between them is constant, which results in an approximate characterization of the asymmetric Gaussian three description rate region.

We introduce the interference-multiple-access channel, which is a discrete memoryless channel with two transmitters and two receivers, similar to the interference channel. One receiver is required to decode the information encoded at one transmitter, the other receiver is required to decode the messages from both transmitters. We provide an inner bound on the capacity region of this channel, as well as an outer bound for a special class of such channels. For this class, we also quantify the gap between inner and outer bound and show that the bounds match for a semi-deterministic channel, providing a complete characterization. For the Gaussian case, we show that the gap is at most 1 bit, yielding an approximate characterization.

In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occured, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how should communication happen in such identity-aware sensor networks. We reexamine the traditional source-identity/message separation and propose a scheme for jointly encoding the two. We use this to develop a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks - for instance, node failures, or large numbers of nodes where only few are active during each reporting round.

Given that wireless communication occurs in a shared and inherently broadcast medium, the transmissions are vulnerable to undesired eavesdropping. This occurs even when a point-to-point communication is sought, and hence a fundamental question is whether we can utilize the wireless channel properties to establish secrecy. In this paper we consider secret communication between two special nodes ("source" and "destination") in a wireless network with authenticated relays: the message communicated to the destination is to be kept information-theoretically (unconditionally) secret from any eavesdropper within a class. Since the transmissions are broadcast and interfere with each other, complex signal interactions occur. We develop cooperative schemes which utilize these interactions in wireless communication over networks with arbitrary topology, and give provable unconditional secrecy guarantees.

In this paper we find properties that are shared between two seemingly unrelated lossy source coding setups with side-information. The first setup is when the source and side-information are jointly Gaussian and the distortion measure is quadratic. The second setup is when the side-information is an erased version of the source. We begin with the observation that in both these cases the Wyner-Ziv and conditional rate-distortion functions are equal. We further find that there is a continuum of optimal strategies for the conditional rate distortion problem in both these setups. Next, we consider the case when there are two decoders with access to different side-information sources. For the case when the encoder has access to the side-information we establish bounds on the rate-distortion function and a sufficient condition for tightness. Under this condition, we find a characterization of the rate-distortion function for physically degraded side-information. This characterization holds for both the Gaussian and erasure setups.

We study secret-key agreement protocols over a wiretap channel controlled by a state parameter. The secret-key capacity is established when the wiretap channel is discrete and memoryless, the sender and receiver are both revealed the underlying state parameter, and no public discussion is allowed. An optimal coding scheme involves a two step approach — (i) design a wiretap codebook assuming that the state parameter is also known to the eavesdropper (ii) generate an additional secret key by exploiting the uncertainty of the state parameter at the eavesdropper. When unlimited public discussion is allowed between the legitimate terminals, we provide an upper bound on the secret-key capacity and establish its tightness when the channel outputs of the legitimate receiver and eavesdropper satisfy a conditional independence property. Numerical results for an on-off fading model suggest that the proposed coding schemes significantly outperform naive schemes that either disregard the contribution of the common state sequence or the contribution of the underlying channel.

In this paper we study the Gaussian relay-interference network, in which relay (helper) nodes are to facilitate competing information flows over a wireless network. We examine this problem for certain regimes of channel values, when one of the cross-links is dominated by noise, resulting in Z and/or S configurations for the networks. For these Gaussian ZZ and ZS networks, we establish an approximate characterization of the rate region. The outer bounds to the capacity regions are established using genie-aided techniques that extend the methods used for the Gaussian interference channel to the relay-interference network. For the inner bound of the ZZ network, we utilize a new interference management scheme, termed interference neutralization, which was inspired by our earlier study of such deterministic networks. This technique allows for over-the-air interference removal, without the transmitters having complete access to the interfering signals.

The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N ¿ 1 receivers can also be achieved using packets of length logN bits, if the operations the intermediate nodes perform are deterministically known at the receivers. We here calculate the capacity in the case where these operations are unknown, and characterize how the capacity depends on the min-cut value and the packet length.

We consider the joint source-channel coding problem of sending a Gaussian source over a K-user Gaussian broadcast channel with bandwidth mismatch. A new outer bound to the achievable distortion region is derived using the technique of introducing more than one additional auxiliary random variable, which was previously used to derive sum-rate lower bound for the Gaussian multiple description problem. By combining this outer bound with the source-channel-separation-based achievable region, we provide approximate characterizations of the achievable distortion region within constant multiplicative factors.

In this paper we consider communication between two special nodes (ldquosourcerdquo and ldquodestinationrdquo) in a wireless relay network, which has malfunctioning or malicious nodes (inserting errors). We develop the model for wireless network communication in the presence of a Byzantine adversary for different assumptions on channel/adversarial knowledge. We examine coding schemes which utilize signal interactions in the deterministic wireless network to reliably deliver information in the presence of such errors due to a Byzantine adversary.

The wireless multiple-unicast problem is considered over a layered network, where the rates of transmission are limited by the relaying and interference effect. The deterministic model introduced is used to capture the broadcasting and multiple access effects. The capacity region of the Z-chain relay-interference network is fully characterized. In order to solve the problem, we introduce a new achievability scheme based on ldquointerference neutralizationrdquo and a new analysis technique to bound the number of non-interfering (pure) signals.

We consider multisource non-coherent network coding, where multiple sources send information to one or multiple receivers. We prove that this is equivalent to a ldquosubspacerdquo channel, that takes subspaces as inputs and outputs. We then show that the rate of each individual receiver is upper bounded as deltai(T - delta1- delta2), where deltaiis what we define to be the ldquodominatingrdquo dimension in the subspace codebook of source i, and T is the ldquocoherencerdquo time of the network.

We design a novel class of space-time codes, called linear diversity-embedding space-time block codes (LDE-STBC) where a high-rate STBC is linearly superimposed on a highdiversity STBC without requiring channel knowledge at the transmitter. In applying this scheme to multimedia wireless communications, each traffic type constitutes a transmission layer that operates at a suitable rate-diversity tradeoff point according to its quality-of-service requirements. This, in turn, provides an unequal-error-protection (UEP) capability to the different information traffic types and allows a form of wireless communications where the high-rate STBC opportunistically takes advantage of good channel realizations while the embedded high-diversity STBC ensures that at least part of the information is decoded reliably. We investigate transceiver design issues specific to LDE-STBC including reduced-complexity coherent decoding and effective schemes to vary the coding gain to further enhance UEP capabilities of the code. Furthermore, we investigate the application of LDE-STBC to wireless multicasting and demonstrate its performance advantage over conventional equal-error-protection STBC.

Networks need to accommodate diverse applications with different quality-of-service (QoS) requirements. New ideas at the physical layer are being developed for this purpose, such as diversity embedded coding, which is a technique that combines high rates with high reliability. We address the problem of how to fully utilize different rate-reliability characteristics at the physical layer to support different types of traffic over a network and to jointly maximize their utilities. We set up a new framework based on utility maximization for networks with composite links, meaning that each link consists of sub-links that can attain different rate-reliability characteristics simultaneously. We incorporate delay, in addition to rate and reliability, into the utility functions. To accommodate different types of traffic, we propose distributed algorithms converging to the optimal rate-reliability-delay tradeoff based on capacity division and priority queueing. Numerical results show that compared with traditional codes, the new codes can provide higher network utilities for all traffic types simultaneously. The results also show that priority queueing achieves higher network utility than capacity division.

We consider the problem of multiple description coding for stationary Gaussian sources under the squared error distortion measure. The rate region is characterized for the 2-description case. It is shown that each supporting line of the rate region is achievable with a transform lattice quantization scheme. We show the optimal coding scheme has a natural spectral domain coding interpretation, which yields a reverse water-filling solution with a frequency-dependent water level instead of the flat water level as in the conventional single description case.

We consider multiple description (MD) coding for the Gaussian source withKdescriptions under the symmetric mean-squared error (MSE) distortion constraints, and provide an approximate characterization of the rate region. We show that the rate region can be sandwiched between two polytopes, between which the gap can be upper-bounded by constants dependent on the number of descriptions, but independent of the distortion constraints. Underlying this result is an exact characterization of the lossless multilevel diversity source coding problem: a lossless counterpart of the MD problem. This connection provides a polytopic template for the inner and outer bounds to the rate region. In order to establish the outer bound, we generalize Ozarow's technique to introduce a strategic expansion of the original probability space by more than one random variable. For the symmetric rate case with any number of descriptions, we show that the gap between the upper bound and the lower bound for the individual description rate-distortion function is no larger than 0.92 bit. The results developed in this work also suggest that the ldquoseparationrdquo approach of combining successive refinement quantization and lossless multilevel diversity coding is a competitive one, since its performance is only a constant away from the optimum. The results are further extended to general sources under the MSE distortion measure, where a similar but looser bound on the gap holds.

Symmetric multilevel diversity coding was introduced by Roche et al, where a set of K information sources is encoded by K encoders and the decoders reconstruct sources 1,...,k, where k is the number of encoders to which they have access. In this paper, we formulate an asymmetric multilevel diversity coding problem, where a set of 2K- 1 information sources is encoded by K encoders into K streams/descriptions. There are 2K- 1 decoders, each of which has access to a non-empty subset of the encoded messages. The decoders are assigned with ordered levels, and each of them has to decode a subset of the information sources, according to its level, which depends on the set of encoders to which it has access, not just the cardinality. We obtain a single letter characterization of the complete achievable rate region for the 3- description problem. In doing so, we show that it is necessary to jointly encode independent sources (i.e., similar to network coding), and that linear codes are optimal for this problem.

We consider symmetric multiple description coding for the Gaussian source, and provide upper and lower bounds for the individual description rate-distortion function. One of the main contributions of this work is a novel lower bound on the sum rate under symmetric distortion constraints, which yields a lower bound on the individual rate for the symmetric case. Two upper bounds are derived, the first of which is based on successive refinement coding coupled with multilevel diversity coding (SR-MLD), and the second is based on the multi-layer coding scheme proposed in literature. We show that the gaps between the lower bound and the upper bounds are no larger than certain constants depending only on the number of descriptions, but not the distortion constraints. Moreover, regardless of the number of descriptions, the gap between the lower bound and the upper bound using the SR-MLD coding scheme is less than 1.5 bits, and for the other case, the gap is less than 1 bit.

To provide real-time multimedia services over a network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Yet such services are beginning to be deployed over best effort networks. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that greater redundancy in the MD streams is needed to protect against such failures. However, one surprising aspect of our study reveals that for large number of users competing for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

We present an achievable rate for general Gaussian relay networks. We show that the achievable rate is within a constant number of bits from the information-theoretic cut-set upper bound on the capacity of these networks. This constant depends on the topology of the network, but not the values of the channel gains. Therefore, we uniformly characterize the capacity of Gaussian relay networks within a constant number of bits, for all channel parameters.

Multiplexing rate and diversity impose a fundamental trade-off in wireless communications. This tradeoff was investigated for inter-symbol interference (ISI) channels in (Grokop, 2004). A different point of view was explored in (Diggavi et al., 2008) where high-rate codes were designed so that they have a high-diversity code embedded within them. It was shown in (Diggavi, 2005) that the diversity-multiplexing (D-M) tradeoff for channels with one degree of freedom (SIMO/MISO) is successively refinable i.e., one can perfectly embed a high diversity code within a high rate code. The performance of such diversity embedded codes were investigated for ISI channels in (Dusad, 2006) where it was shown that for SISO/SIMO ISI fading channels the D-M tradeoff is still successively refinable, in contrast to parallel flat fading channels (Diggavi, 2006). The main result of this paper is that the diversity multiplexing tradeoff for fading MISO ISI channels is indeed successively refinable. This is related to a deterministic structural observation about the asymptotic behavior of frequency response of channel with respect to fading strength of time domain taps as well as a coding scheme to take advantage of this observation.

A joint-source-channel setup for secret-key generation between remote terminals is considered. The sender communicates to the receiver over a discrete memoryless wiretap channel and the sender and receiver observe a pair of correlated discrete memoryless sources. Lower and upper bounds for the secret-key rate are presented and shown to coincide for the case when the underlying channel is a reversely degraded parallel channel. Our setup also provides an operational significance to the rate-equivocation tradeoff of the wiretap channel, and this is illustrated in detail for the Gaussian case.

We consider asymmetric multiple description (MD) source coding for Gaussian source under mean squared error distortion constraints, and focus on the three description problem. Inner and outer bounds for the rate region are derived, both of which can be represented as the intersection of ten half spaces with matching normal directions. Moreover, the gap between the inner and outer bounds is shown to be small. The inner bound relies on the rate region characterization of a lossless asymmetric multilevel diversity (MLD) coding problem treated in our earlier work, which is a natural generalization of the symmetric MLD coding problem previously considered by Roche et al. Different from symmetric MLD coding, superposition coding is not sufficient in the asymmetric case, and ideas akin to network coding need to be used strategically. Equipped with this finding, and motivated by the connection between symmetric MD and symmetric MLD coding, in this work we consider asymmetric MD as a lossy version of the asymmetric MLD coding, which requires coding beyond simple superposition. An outer bound is also derived, which bears a geometric structure particularly suitable for comparison with the inner bound. Combining the inner and outer bounds provides an approximate characterization of the rate region for the asymmetric Gaussian three description problem.

We examine the problem of multiple sources transmitting information to one or more receivers that require the information from all the sources, over a network where the network nodes perform randomized network coding. We consider the noncoherent case, where neither the sources nor the receivers have any knowledge of the intermediate nodes operations. We formulate a model for this problem, inspired from block- fading noncoherent MIMO communications. We prove, using information theoretic tools, that coding over subspaces is sufficient to achieve the capacity, and give bounds for the capacity. We then examine the associated combinatorial problem of code design. We extend the work by Koetter and Kschischang [3] to code constructions for the multisource case. Our constructions can also be viewed as coding for the noncoherent multiple-access finite-field channel.

We consider multiple description coding for the Gaussian source with K descriptions under the symmetric mean squared error distortion constraints. Inner and outer bounds for the achievable rate region are derived and carefully tailored, such that they can be compared conveniently. The inner bound is based on a generalization of the multilayer scheme previously proposed by Puri et al., through a more flexible binning method. The resulting achievable region has the same geometric structure as the rate region of the lossless multilevel diversity coding problem, which reveals a strong connection between them. The outer bound is derived by combining the bounding technique for the sum rate in our earlier work, together with the α-resolution method introduced by Yeung and Zhang. Comparison between the inner and outer bounds shows that the gap in between is upper bounded by some constants. Particularly for the three description problem, the bounds can be written explicitly, and both the inner and outer bounds can be represented by ten planes with matching normal directions, between which the pairwise difference is small.

Dynamic networks are those where the topology changes over time and therefore efficient routes need to be maintained by frequent updates. Such updates could be costly in terms of consuming throughput available for data transmission, which is a precious resource in wireless networks. In this paper, we ask the question whether there exist low-overhead schemes for dynamic wireless networks, that could produce routes that are within a small constant factor (stretch) of the optimal route-length. This is studied by using the underlying geometric properties of the connectivity graph in wireless networks. For a class of models for mobile wireless network that fulfill some mild conditions on the connectivity and on mobility over the time of interest, we can design distributed routing algorithm that maintains the routes over a changing topology. This scheme needs only node identities and therefore integrates location service along with routing, therefore accounting for the complete overhead. We analyze the worst-case (conservative) overhead and route-quality (stretch) performance of this algorithm for the aforementioned class of wireless network connectivity and mobility models. In particular for these models, we show that our algorithm allows constant stretch routing with a network wide control traffic overhead of O(nlog 2 n) bits per mobility time step (time-scale of topology change) translating to O(log 2 n) overhead per node (with high probability for wireless networks with such mobility model). Additionally, we can reduce the maximum overhead per node by using a load-balancing technique at the cost of a slightly higher average overhead. We also demonstrate through numerics that these worst-case bounds are quite conservative in terms of the constants derived theoretically. 1 I.

Rate and diversity impose a fundamental tradeoff in wireless communication. High-rate space-time codes come at a cost of lower reliability (diversity), and high reliability (diversity) implies a lower rate. However, wireless networks need to support applications with very different quality-of-service (QoS) requirements, and it is natural to ask what characteristics should be built into the physical layer link in order to accommodate them. In this paper, we design high-rate space-time codes that have a high-diversity code embedded within them. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations while the embedded high-diversity code provides guarantees that at least part of the information is received reliably. We provide constructions of linear and nonlinear codes for a fixed transmit alphabet constraint. The nonlinear constructions are a natural generalization to wireless channels of multilevel codes developed for the additive white Gaussian noise (AWGN) channel that are matched to binary partitions of quadrature amplitude modulation (QAM) and phase-shift keying (PSK) constellations. The importance of set-partitioning to code design for the wireless channel is that it provides a mechanism for translating constraints in the binary domain into lower bounds on diversity protection in the complex domain. We investigate the systems implications of embedded diversity codes by examining value to unequal error protection, rate opportunism, and packet delay optimization. These applications demonstrate that diversity-embedded codes have the potential to outperform traditional single-layer codes in moderate signal-to-noise (SNR) regimes.

Designs for transmit alphabet constrained space-time codes naturally lead to questions about the design of rank distance codes. Recently, diversity embedded multilevel space-time codes for flat-fading channels have been designed from sets of binary matrices with rank distance guarantees over the binary field by mapping them onto quadrature amplitude modulation (QAM) and phase-shift keying (PSK) constellations. In this paper, we demonstrate that diversity embedded space-time codes for fading intersymbol interference (ISI) channels can be designed with provable rank distance guarantees. As a corollary, we obtain an asymptotic characterization of the fixed transmit alphabet rate-diversity tradeoff for multiple antenna fading ISI channels. The key idea is to construct and analyze properties of binary matrices with a particular structure (Toeplitz structure) induced by ISI channels.

In this correspondence, we consider the multiuser successive refinement (MSR) problem, where the users are connected to a central server via links with different noiseless capacities, and each user wishes to reconstruct in a successive-refinement fashion. An achievable region is given for the two-user two-layer case and it provides the complete rate-distortion region for the Gaussian source under the MSE distortion measure. The key observation is that this problem includes the multiple description (MD) problem (with two descriptions) as a subsystem, and the techniques useful in the MD problem can be extended to this case. It is shown that the coding scheme based on the universality of random binning is suboptimal, because multiple Gaussian side informations only at the decoders do incur performance loss, in contrast to the case of single side information at the decoder. It is further shown that unlike the single user case, when there are multiple users, the loss of performance by a multistage coding approach can be unbounded for the Gaussian source. The result suggests that in such a setting, the benefit of using successive refinement is not likely to justify the accompanying performance loss. The MSR problem is also related to the source coding problem where each decoder has its individual side information, while the encoder has the complete set of the side informations. The MSR problem further includes several variations of the MD problem, for which the specialization of the general result is investigated and the implication is discussed.

We consider the problem of side-information scalable (SI-scalable) source coding, where the encoder constructs a two-layer description, such that the receiver with high quality side information will be able to use only the first layer to reconstruct the source in a lossy manner, while the receiver with low quality side information will have to receive both layers in order to decode. We provide inner and outer bounds to the rate-distortion (R-D) region for general discrete memoryless sources. The achievable region is tight when either one of the decoders requires a lossless reconstruction, and when the distortion measures are degraded and deterministic. Furthermore, the gap between the inner and the outer bounds can be bounded by certain constants when the squared error distortion measure is used. The notion of perfect scalability is introduced, for which necessary and sufficient conditions are given for sources satisfying a mild support condition. Using SI-scalable coding and successive refinement Wyner-Ziv coding as basic building blocks, we provide a complete characterization of the rate-distortion region for the important quadratic Gaussian source with multiple jointly Gaussian side informations, where the side information quality is not necessarily monotonic along the scalable coding order. A partial result is provided for the doubly symmetric binary source under the Hamming distortion measure when the worse side information is a constant, for which one of the outer bounds is strictly tighter than the other.

We consider the problem of transmitting a Gaussian source on a slowly fading Gaussian channel, subject to the mean-squared error distortion measure. The channel state information is known only at the receiver but not at the transmitter. The source is assumed to be encoded in a successive refinement (SR) manner, and then transmitted over the channel using the broadcast strategy. In order to minimize the expected distortion at the receiver, optimal power allocation is essential. We propose an efficient algorithm to compute the optimal solution in linear time , when the total number of possible discrete fading states. Moreover, we provide a derivation of the optimal power allocation when the fading state is a continuum, using the classical variational method. The proposed algorithm as well as the continuous solution is based on an alternative representation of the capacity region of the Gaussian broadcast channel.

We consider the problem of multiple description (MD) coding for stationary sources with the squared error distortion measure. The MD rate region is derived for the stationary and ergodic Gaussian sources, and is shown to be achievable with a practical transform lattice quantization scheme. Moreover, the proposed scheme is asymptotically optimal at high resolution for all stationary sources with finite differential entropy rate

Networks need to accommodate diverse applications with different quality-of-service (QoS) requirements. New ideas at the physical layer are being developed for this purpose, such as diversity embedded coding, which is a technique that combines high rates with high reliability. We address the problem of how to fully utilize different rate-reliability characteristics at the physical layer to support different types of traffic over a network and to jointly maximize their utilities. We set up a new framework based on utility maximization for networks with composite links, meaning that each link consists of sub-links that can attain different rate-reliability characteristics simultaneously. We incorporate delay, in addition to rate and reliability, into the utility functions. To accommodate different types of traffic, we propose distributed algorithms for the optimal rate-reliability-delay tradeoff based on capacity division and priority queueing. Numerical results show that compared with traditional codes, the new codes can provide higher network utilities for all traffic types simultaneously. The results also show that priority queueing achieves higher network utility than capacity division.

Wireless routing based on an embedding of the connectivity graph is a very promising technique to overcome shortcomings of geographic routing and topology-based routing. This is of particular interest when either absolute coordinates for geographic routing are unavailable or when they poorly reflect the underlying connectivity in the network. We focus on dynamic networks induced by time-varying fading and mobility. This requires that the embedding is stable over time, whereas the focus of most existing embedding algorithms is on low distortion of single realizations of a graph. We develop a beacon-based distributed embedding algorithm that requires little control overhead, produces low distortion embeddings, and is stable. We also show that a low-dimensional embedding suffices, since at a sufficiently large scale, wireless connectivity graphs are dictated by geometry. The stability of the embedding allows us to combine geo-routing on the embedding with last encounter routing (LER) for node lookup, further reducing the control overhead. Our routing algorithm avoids dead ends through randomized greedy forwarding. We demonstrate through extensive simulations that our combined embedding and routing scheme outperforms existing algorithms.

We present two upper bounds on the capacity of the i.i.d. binary deletion channel, where each bit is independently deleted with a fixed probability d. The first can be numerically evaluated for any fixed d. The second provides an asymptotic upper bound as d goes to 1. These appear to be the first nontrivial upper bounds for this probabilistic deletion channel.

We consider the problem of scalable source coding with decoder side informations. Two special cases of this problem have been investigated in the literature, namely successive refinement Wyner-Ziv (SR-WZ) coding and side-information scalable (Si-Scalable) coding, whose distinction lies in the degradedness of the side informations. In this work, we first show the achievable region for the Si-scalable problem provided in a previous work is tight when either the first stage or the second stage requires lossless reconstruction. Then the notion of perfectly scalable coding is introduced as both the stages operate on the Wyner-Ziv bound, and a set of necessary and sufficient conditions is given for sources satisfying a mild support condition. Furthermore, generalizing the coding scheme for the SR-WZ and SI-scalable coding, we provide a conclusive solution for the (multistage) quadratic Gaussian scalable coding problem with jointly Gaussian side informations in an arbitrary order of quality.

We present a deterministic channel model which captures several key features of multiuser wireless communication. We consider a model for a wireless network with nodes connected by such deterministic channels , and compute the end-to-end capacity when there is a single source and a single destination and an arbitrary number of relay nodes. This capacity has the interpretation of the in ax-flow min-cut solution of a wireline network naturally associated with the deterministic wireless network.

Designs for transmit alphabet constrained space-time codes naturally lead to questions about the design of rank distance codes. Recently, diversity embedded multi-level space-time codes for flat fading channels have been designed by using sets of binary matrices with rank distance guarantees over the binary field and mapping them onto QAM and PSK constellations. In this paper we give the design of diversity embedded space-time codes for fading Inter-Symbol Interference (ISI) channels with provable rank distance guarantees. In the process of doing so we also get a (asymptotic) characterization of the rate-diversity trade-off for multiple antenna fading ISI channels when there is a fixed transmit alphabet constraint. The key idea is to construct and analyze properties of binary matrices with the particular structure induced by ISI channels.

Randomized network coding has network nodes randomly combine and exchange linear combinations of the source packets. A header appended to the packet, called coding vector, specifies the exact linear combination that each packet carries. The main contribution of this work is to investigate properties of the subspaces spanned by the collected coding vectors in each network node. We use these properties to exhibit the relationship between the network topology and the subspaces collected at the nodes. This allows us to passively infer the network topology for a general class of graphs.

We consider the problem of transmitting a Gaussian source on a slowly fading Gaussian channel, subject to the mean squared error distortion measure. The channel state information is known only at the receiver but not the transmitter. The source is assumed to be encoded in a successive refinement manner, and then transmitted over the channel using the broadcast strategy. In order to minimize the expected distortion at the receiver, optimal power allocation is essential. We propose an efficient algorithm to compute the optimal solution in linear time O(M). Moreover, we provide a derivation of the optimal power allocation when the fading state is a continuum, using the classical variational method. The proposed algorithm as well as the continuous solution is based on an alternative representation of the capacity region of the Gaussian broadcast channel.

In this correspondence, we provide a complete characterization of the rate-distortion region for themultistagesuccessive refinement of the Wyner–Ziv source coding problem with degraded side informations at the decoder. Necessary and sufficient conditions for a source to be successively refinable along a distortion vector are subsequently derived. A source–channel separation theorem is provided when the descriptions are sent over independent channels for the multistage case. Furthermore, the notion of generalized successive refinability with multiple degraded side informations is introduced. This notion captures whether progressive encoding to satisfy multiple distortion constraints for different side informations is as good as encoding without progressive requirement. Necessary and sufficient conditions for generalized successive refinability are given. It is shown that the following two sources are generalized successively refinable: 1) the Gaussian source with degraded Gaussian side informations and 2) the doubly symmetric binary source when the worse side information is a constant. Thus for both cases, the failure of being successively refinable is only due to the inherent uncertainty on which side information will occur at the decoder, but not the progressive encoding requirement.

We consider a lossy source coding problem where the description of a source is going to be used by two decoders, each having access to information correlated with the source. This side-information is also present at the encoder. We gave inner and outer bounds to the set of achievable rate and distortion triples. For the special case Gaussian sources wish degraded side-information and squared error distortions, the two bounds coincide and we obtain the true rate-distortion region. As a further specialization, we obtain the rate-distortion region of the Gaussian version of a problem previously solved by Kaspi for discrete memoryless sources. Using this resist we quantify bow much revealing the side-information to the encoder helps in such a Gaussian setup

We provide a complete characterization of rate region for the multistage successive refinement of Wyner-Ziv source coding problem with degraded side information at the decoder. This problem was left open in a recent work by Steinberg and Merhav (T-IT, 2004), where it was solved for the special case of two stages. Furthermore, we introduce the notion of generalized successive refinability with multiple side informations. This captures whether progressive encoding to satisfy the distortion constraints for different side information as good as encoding without progressive requirement. For degraded side-information, we give necessary and sufficient conditions for generalized successive refinability. Using this, we show that for Gaussian source, the failure of being successively refinable with multiple side informations is only due to the inherent uncertainty on which side information will occur at the decoder, but not the progressive encoding requirement

Diversity embedded codes are opportunistic codes which take advantage of good channel realizations while ensuring at least part of the information is received reliably for bad channels. We establish a connection between these codes and degraded message set broadcast codes. We characterize the achievable rate region for the parallel Gaussian degraded message set broadcast problem, when only the strongest user needs the private information. Using this, we partially characterize the set of achievable rate-diversity tuples for the diversity embedded problem for parallel fading channels.

We study information transmission through a finite buffer queue. We model the channel as a finite-state channel whose state is given by the buffer occupancy upon packet arrival; a loss occurs when a packet arrives to a full queue. We study this problem in two contexts: one where the state of the buffer is known at the receiver, and the other where it is unknown. In the former case, we show that the capacity of the channel depends on the long-term loss probability of the buffer. Thus, even though the channel itself has memory, the capacity depends only on the stationary loss probability of the buffer. The main focus of this correspondence is on the latter case. When the receiver does not know the buffer state, this leads to the study of deletion channels, where symbols are randomly dropped and a subsequence of the transmitted symbols is received. In deletion channels, unlike erasure channels, there is no side-information about which symbols are dropped. We study the achievable rate for deletion channels, and focus our attention on simple (mismatched) decoding schemes. We show that even with simple decoding schemes, with independent and identically distributed (i.i.d.) input codebooks, the achievable rate in deletion channels differs from that of erasure channels by at most H0(pd)-pdlogK/(K-1) bits, for pd-1, where pdis the deletion probability, K is the alphabet size, and H0(middot) is the binary entropy function. Therefore, the difference in transmission rates between the erasure and deletion channels is not large for reasonable alphabet sizes. We also develop sharper lower bounds with the simple decoding framework for the deletion channel by analyzing it for Markovian codebooks. Here, it is shown that the difference between the deletion and erasure capacities is even smaller than that with i.i.d. input codebooks and for a larger range of deletion probabilities. We also examine the noisy deletion channel where a deletion channel is cascaded with a symmetric discrete memoryless channel (DMC). We derive a single letter expression for an achievable rate for such channels. For the binary case, we show that this result simplifies to max(0,1-[H0(thetas)+thetasH0(pe)]) where peis the cross-over probability for the binary symmetric channel

Inspired by the combinatorial denoising method DUDE, we present efficient algorithms for implementing this idea for arbitrary contexts or for using it within subsequences. We also propose effective, efficient denoising error estimators so we can find the best denoising of an input sequence over different context lengths. Our methods are simple, drawing from string matching methods and radix sorting. We also present experimental results of our proposed algorithms.

Diversity-embedded codes for fading channels are high-rate codes that are designed so that they have a high-diversity code embedded within them. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations whereas the embedded high-diversity code ensures that at least part of the information is received reliably. This can also be thought as coding the data into two streams such that the high-priority stream has higher reliability than the low-priority stream. For SISO (single-input-single-output), SIMO, MISO and parallel fading channels, we characterize the achievable rates and reliability of the two streams in the high SNR regime in terms of the diversity-multiplexing tradeoff. We exhibit the performance gain over a single-stream code. We also show some constructions for finite block lengths that achieve the optimal performance

Abstract Next‐generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine‐grained QoS to users in such networks poses the two‐dimensional challenge of assigning both power (rate) and codes to every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next‐generation wireless data systems. Our contribution includes a communication‐theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for streams of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, on‐line algorithms for approximating the optimal maximum response time. We also perform an experimental study with realistic data of channel conditions and user requests that strengthens our theoretical results. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 9–22 2005

We study the capacity of ad hoc wireless networks with mobile nodes. The mobility model examined is one where the nodes are restricted to move along one-dimensional paths. We examine the scaling laws for the per user throughput achievable over long time-scales, making this suitable for applications with loose delay constraints. We show that under this regime of restricted mobility, we attain a constant throughput (i.e., Θ (1)) per user, which is significantly higher than the throughput of fixed networks, which decays as O(1/√n) with the number of nodes n, as shown by Gupta and Kumar.

Two subspaces of a vector space are here called "nonintersecting" if they meet only in the zero vector. Motivated by the design of noncoherent multiple-antenna communications systems, we consider the following question. How many pairwise nonintersecting M/sub t/-dimensional subspaces of an m-dimensional vector space V over a field F can be found, if the generator matrices for the subspaces may contain only symbols from a given finite alphabet A/spl sube/F? The most important case is when F is the field of complex numbers C; then M/sub t/ is the number of antennas. If A=F=GF(q) it is shown that the number of nonintersecting subspaces is at most (q/sup m/-1)/(q/sup Mt/-1), and that this bound can be attained if and only if m is divisible by M/sub t/. Furthermore, these subspaces remain nonintersecting when "lifted" to the complex field. It follows that the finite field case is essentially completely solved. In the case when F=C only the case M/sub t/=2 is considered. It is shown that if A is a PSK-configuration, consisting of the 2/sup r/ complex roots of unity, the number of nonintersecting planes is at least 2/sup r(m-2)/ and at most 2/sup r(m-1)-1/ (the lower bound may in fact be the best that can be achieved).

This paper designs space-time codes for standard PSK and QAM signal constellations that have flexible rate, diversity and require no constellation expansion. Central to this construction are binary partitions of the PSK and QAM constellations that appear in codes designed for the Gaussian channel. The space-time codes presented here are designed by separately specifying the different levels of the binary partition in the space-time array. The individual levels are addressed by either the binary symmetric matrices associated with codewords in a Kerdock code or other families of binary matrices. Binary properties of these sets are sufficient to verify the diversity property of the codewords in the complex domain. Larger sets of binary symmetric matrices (such as the set used in Delsarte-Goethals codes) are used to trade diversity protection for increased rate.

In this paper, we construct a new nonlinear 4x4 full-rate, full-diversity orthogonal space-time block code (STBC) using quaternionic algebra on which the Alamouti code is also based. We also develop a differential encoding and decoding scheme for this code, which also enjoys low decoding complexity

This paper describes the construction of codewords and subspaces are nonintersecting over the finite field. When the alphabet is a finite field, constructions are lifted to the complex field to obtain maximal diversity differential space-time codes for the noncoherent multiple antenna problems. The construction of codewords (i.e. nonintersecting subspaces) subjects to the constraint that the elements of the codewords use symbols from a fixed, small PSK constellation.

We formulate a multi-terminal source coding problem, where we are required to construct a multiple-description code for a source sequence when side information about dependent random processes is available at the decoder only, or at both the decoder and the encoder. We describe an achievable rate-distortion region for these problems in two cases: where there is common side-information at the decoders and when they are different. In the quadratic Gaussian case, and when there is common side information among the decoders, we show that the rate region when both the encoder and decoder have access to the side information coincides with that of decoder-only side information. This is analogous to the single-description (Wyner-Ziv) case, and an explicit characterization of the rate-distortion region is provided for this case.

The effect of spatial diversity on the throughput and reliability of wireless networks is examined. Spatial diversity is realized through multiple independently fading transmit/receive antenna paths in single-user communication and through independently fading links in multiuser communication. Adopting spatial diversity as a central theme, we start by studying its information-theoretic foundations, then we illustrate its benefits across the physical (signal transmission/coding and receiver signal processing) and networking (resource allocation, routing, and applications) layers. Throughout the paper, we discuss engineering intuition and tradeoffs, emphasizing the strong interactions between the various network functionalities.

Rate and diversity impose a fundamental trade-off in space-time coding. High-rate space-time codes come at a cost of lower diversity, and high reliability (diversity) implies a lower rate. We explore a different point of view where we design high-rate space-time codes that have a high-diversity code embedded within them. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations whereas the embedded high-diversity code ensures that at least part of the information is received reliably. We explore this point of view with design issues, along with some preliminary progress on code constructions and some information-theoretic considerations.

In this paper we study the multiple-access channel where users employ space-time block codes (STBC). The problem is formulated in the context of an inter-symbol interference (IS) multiple-access channel. The algebraic structure of the STBC is utilized to design joint interference suppression, equalization, and decoding schemes. Each user transmits using 2 transmit antennas and a time-reversed space-time block code suitable for frequency-selective channels. We first show that a diversity order of 2M/sub r/(v+1) is achievable at full transmission rate for each user, when we have M/sub r/ receive antennas, channel memory of v and an optimal multi-user maximum-likelihood (ML) decoder is used. Due to the decoding complexity of the ML detectors we study the algebraic structure of linear multiuser detectors, which utilize he properties of the STBC. We do this both in the transform domain (D-domain formulation) and when we impose finite block length constraints (matrix formulation). The receiver is designed to utilize the algebraic structure of the codes in order to preserve the block quaternionic structure of the equivalent channel for each user.

The next generation wireless networks are posited to support large scale data applications. Implementing end-to-end TCP in such networks faces two problems. First, it is well known that TCP can not distinguish packet losses due to link failures and that due to network congestion. Second, TCP congestion control mechanism does not deal effectively with large amount of out-of-order packet retransmissions; this problem has received less attention in literature. In this paper, we present solutions to both these problems. In particular, we present a link-layer header protection (LHP) protocol, which implements explicit loss notification (ELN) in a simple, scalable manner, addressing the first problem. We also modify the congestion control mechanism to incorporate knowledge of ELN and packet loss pattern into retransmission decisions, solving the second problem. We combine both these solutions with TCP to present scalable, reliable end-to-end wireless transport protocol.

In this paper, we study the multiple-access channel where users employ space-time block codes (STBC). The problem is formulated in the context of an intersymbol interference (ISI) multiple-access channel which occurs for transmission over frequency-selective channels. The algebraic structure of the STBC is utilized to design joint interference suppression, equalization, and decoding schemes. Each of the K users transmits using M/sub t/=2 transmit antennas and a time-reversed STBC suitable for frequency-selective channels. We first show that a diversity order of 2M/sub r/(/spl nu/+1) is achievable at full transmission rate for each user, when we have M/sub r/ receive antennas, channel memory of /spl nu/, and an optimal multiuser maximum-likelihood (ML) decoder is used. Due to the decoding complexity of the ML detector we study the algebraic structure of linear multiuser detectors which utilize the properties of the STBC. We do this both in the transform (D-domain) formulation and when we impose finite block-length constraints (matrix formulation). The receiver is designed to utilize the algebraic structure of the codes in order to preserve the block quaternionic structure of the equivalent channel for each user. We also explore some algebraic properties of D-domain quaternionic matrices and of quaternionic circulant block matrices that arise in this study.

We examine multicarrier transmission over time-varying channels. We first develop the model for such a transmission scheme and focus particularly on OFDM-based schemes. We analyze the impact of time-variation within a transmission block which could arise both from Doppler spread of the channel and from synchronization errors. We propose a time-domain approach to mitigate the effects of such time-variations. This approach reduces to the familiar single-tap frequency-domain equalizer when the channel is block time-invariant. We also develop this in the context of multiple transmit and receive antennas and specialize the receiver to space-time block-coded systems. Finally we provide numerical results.

Next generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two dimensional challenge of assigning both power (rate) and codes for every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next generation wireless data systems. This includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for stream of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, online algorithms for approximating the optimal maximum response time. This relies on resource augmented competitive analysis. We also perform an experimental study with realistic data of channel conditions and user requests to show that our algorithms are more accurate than our worst case analysis shows, and they provide fine-grained QoS to users effectively.

In this paper, we investigate OFDM transmission over fast fading channels. In such scenarios, the Doppler spread of the channel and synchronization errors cause intercarrier interference (ICI) and complicate channel estimation because the channel cannot be assumed constant during the transmission of an OFDM block. Channel estimation in rapidly time-varying scenarios becomes critical, an we propose a scheme for estimating channel parameters varying within a transmission block. Along with the channel estimation scheme, we also examine the issue of pilot tone placement and show that in time-varying channels it may be better to group pilot tones together into clumps equispaced onto the FFT grid; this placement technique is in contrast to the common wisdom for time-invariant channels. Finally we provide numerical results.

We show that the optimum length-/spl nu/ guard sequence for block transmission over a linear Gaussian-noise dispersive channel with memory /spl nu/ is a linear combination of the N information symbols of the block. A closed-form expression for the optimum guard sequence is derived subject to a total average energy constraint on the information and guard symbols. The achievable channel block throughput with the optimum guard sequence is compared with that achievable with two common guard sequence types, namely zero stuffing and cyclic prefix.

This paper addresses the problem of soft equalization for space-time-coded transmissions over frequency-selective fading channels. The structure of the space-time code is embedded in the channel impulse response for efficient joint equalization and decoding. The proposed equalization/decoding approach uses a prefilter to concentrate the effective channel power in a small number of taps followed by a reduced-complexity maximum a posteriori probability (MAP) equalizer/decoder to produce soft decisions. The prefilter introduces residual intersymbol interference which degrades the performance of MAP when applied to the trellis of the shortened channel. However, the shape of the overall shortened channel impulse response allows the M-algorithm to approximate the prefiltered MAP performance with a small number of states. Based on this general framework, we investigate several enhancements such as using different prefilters for the forward and backward recursions, concatenating two trellis steps during decoding, and temporal oversampling. The performance is evaluated through simulations over the EDGE typical urban channel.

We consider the design of asymmetric multiple description lattice quantizers that cover the entire spectrum of the distortion profile, ranging from symmetric or balanced to successively refinable. We present a solution to a labeling problem, which is an important part of the construction, along with a general design procedure. The high-rate asymptotic performance of the quantizer is also studied. We evaluate the rate-distortion performance of the quantizer and compare it to known information-theoretic bounds. The high-rate asymptotic analysis is compared to the performance of the quantizer.

Channel time-variation and frequency selectivity [causing intersymbol interference (ISI)] are two major impairments in transmission for a wireless communication environment. Spatial diversity on the transmitter or the receiver side has been traditionally used to combat multipath fading. Previous results indicate significant gains in using multiple transmitter and receiver antenna diversity. By deriving the mutual information and cutoff rate we characterize the gains on these channels. We show that gains linear in the number of antennas can be achieved either when the signal-to-noise ratio (SNR) becomes very large or when the number of antennas becomes large. We show that some of these gains can be achieved by lower complexity linear receiver structures. By evaluating the cutoff rate for phase-shift keying (PSK) constellations we further quantify the gains of using spatial diversity at both the transmitter and the receiver. Next, we examine the expected mutual information for slowly fading ISI channels where the channel is assumed to be block time-invariant. We then examine the impact of fast channel time variation (time variation within a transmission block) on multicarrier transmission schemes. We derive the average mutual information for orthogonal frequency-division multiplexing (OFDM) in time-varying ISI environments. Using this we examine the impact of transmitter and receiver diversity on OFDM transmission over time-varying ISI channels. We also study the effect of time variation on OFDM packet-size design.

The maximum entropy noise under a lag p autocorrelation constraint is known by Burg's theorem to be the pth order Gauss-Markov process satisfying these constraints. The question is, what is the worst additive noise for a communication channel given these constraints? Is it the maximum entropy noise? The problem becomes one of extremizing the mutual information over all noise processes with covariances satisfying the correlation constraints R/sub 0/,..., R/sub p/. For high signal powers, the worst additive noise is Gauss-Markov of order p as expected. But for low powers, the worst additive noise is Gaussian with a covariance matrix in a convex set which depends on the signal power.

We consider the design of asymmetric multiple description lattice quantizers that cover the entire spectrum of the distortion profile, ranging from symmetric or balanced to successively refinable. We present a solution to a labeling problem, which is an important part of the construction, along with a general design procedure. This procedure is illustrated using a ZZ/sup 2/ lattice. We also evaluate its rate-distortion performance and compare it to known information theoretic bounds.

We show that the optimum length-/spl nu/ guard sequence for block transmission over a linear, noisy, and dispersive channel with memory /spl nu/ is a linear combination of the N information symbols of the block. The channel block throughput is maximized through a joint numerical optimization of N/spl nu/ linear combination coefficients determining the guard sequence and the N-dimensional auto-correlation matrix of the information symbols, subject to a total average energy constraint on the information and guard symbols. A closed-form solution for the optimum guard sequence is derived for the special case of high SNR. The achievable channel block throughput with the optimum guard sequence is compared with that achievable with two common guard sequence types, namely zero stuffing and cyclic prefix.

The effect of narrow-band interference (NBI) on the finite blocklength throughput of linear noisy dispersive channels is studied. Spectral characteristics (both shape and frequency location) of worst-case NBI and its associated minimum channel block throughput are derived. The performance of finite-length linear and decision feedback equalizers in the presence of worst-case NBI is presented.

Information-theoretic results have shown significant gains in transmission rate over fading channels using multiple transmitter and receiver antenna (spatial) diversity. We review some of these results and show that these gains could also be achieved using simpler receiver structures. We then examine the rates achievable in a multiuser environment, i.e. a multiple access fading channel. The symmetric rate per user is studied and we show that even with simple linear detectors one could obtain non-zero symmetric rates for fading channels (when we have a large number of users). Next we observe that the symmetric rate decreases with the number of users sharing the spectrum. Therefore, one can define a "user capacity" which refers to the number of users who can be supported at a desired symmetric rate per user. We evaluate the user capacity as a function of the number of transmit and receive antennas and observe the benefits of using spatial diversity, from this point of view.

This paper describes an adaptive space-time receiver with joint channel-data estimation (JCDE) to combat time-varying (TV) multipath channels in the presence of undesired cochannel interference (CCI). The receiver uses a colored Gaussian metric for sequence detection in order to suppress the CCI. The proposed scheme also uses the knowledge of the transmit filter for improved channel estimation to enhance performance. The algorithm is derived as a quasi-Newton scheme on a chosen cost criterion and is also locally convergent. The performance of this class of interference cancellers is examined through the pairwise error probability (PEP). Through these expressions we gain insight into the properties of the canceller. The effect of channel dynamics and identification mismatch on the PEP is also examined. To reduce implementational complexity, a hybrid delayed-decision feedback and JCDE scheme is also proposed. The performance is illustrated using numerical results in realistic transmission environments.

This paper describes an adaptive space-time receiver with joint channel and data estimation (JCD) to combat time-varying multipath channels in the presence of undesired co-channel interference (CCI). The receiver uses a colored Gaussian metric in the sequence detection to suppress the CCI. The proposed scheme also uses the knowledge of the transmit filter for improved channel estimation to enhance the performance. We gain insight into the interference suppression scheme through pairwise error-probability analysis. To reduce implementational complexity, a hybrid delayed-decision feedback and JCD scheme is also proposed. The performance is illustrated using numerical results in realistic transmission environments.

Transceiver design is dependent on the a priori information available about the communication environment. We consider two cases: channel completely known at the receiver and transmitter (via feedback); and only channel statistics are known at the transmitter and the channel is known at the receiver. We develop an information-theoretic analysis of these scenarios by examining the mutual information expressions. We analyze a vector coding scheme suitable for time-varying channels and illustrate its asymptotic optimality. We examine the expected mutual information for slowly fading channels and investigate the OFDM transceiver structure. We then derive the average mutual information for OFDM in time-varying environments. This allows us to study the effect of time-variation on OFDM packet-size design. We illustrate the transmission overhead requirements through a numerical example.

This paper presents a frame-work for joint source-channel coding of images over time-varying wireless channels. The source coding algorithm produces an embedded bit-stream to support decoders at different bandwidths. The embedded (source) bit-stream produced is prioritized with bits arranged in order of visual importance. The subjective quality of compressed images improves significantly by the use of perceptual distortion measures in the source coder. Rate-compatible punctured convolutional codes (RCPC) suited for a time-varying channel are used as the channel codes in the joint source-channel codec. The advantage of using RCPC codes is that the high rate codes are embedded into the lower rate codes of the family and the same Viterbi decoder can be used for all codes of a family. A DQPSK modulator is used for transmission in our system. We consider the rate allocation between the source and channel for four scenarios. The scenarios vary according to the amount of information at the transmitter about the channel state at the receiver.