We study the incentives behind double-spend attacks on Nakamoto-style Proof-of-Work cryptocurrencies. In these systems, miners are allowed to choose which transactions to reference within their block, and a common strategy for selecting transactions is to greedily choose those with the highest fees. This can be problematic if these transactions originate from an adversary with substantial computational power (even if it is less than 50% of the total), as high-value transactions are targets for double-spend attacks. The most common mechanism for deterring double-spend attacks is for the recipients of large transactions to wait for additional block confirmations beyond the number suggested by the protocol (effectively increasing the attack cost). We argue that this defense mechanism is not satisfactory, as the security of the system is contingent on the actions of its users . Instead, defending against double-spend attacks should be the responsibility of the miners ; to this end, we propose a protocol rule under which miners limit the amount of transaction value in a block (i.e., reduce the attack reward). To demonstrate the efficacy of our proposed rule, we model cryptocurrency mining as a mean-field game in which the standard mining reward function is augmented to simulate the presence of a rational, double-spending adversary. We design and implement an algorithm which characterizes the behavior of miners at equilibrium, and we show that miners who respond to the adversary-aware reward function accumulate more wealth than those who do not. Under this reward function, the optimal strategy for honest miners is to limit the value transferred in each block such that the adversary’s expected profit is 0. Additionally, we examine Bitcoin’s resilience to double-spend attacks under our model. Assuming a six-block confirmation time, we find that a Bitcoin miner with 26% of the network mining power expects to profit from a double-spend attack.

Gossip algorithms are pivotal in the dissemination of information within decentralized systems. Consequently, numerous gossip libraries have been developed and widely utilized especially in blockchain protocols for the propagation of blocks and transactions. A well-established library is libp $2 p$, which provides two gossip algorithms: floodsub and gossipsub. These algorithms enable the delivery of published messages to a set of peers. In this work we aim to enhance the performance and reliability of libp $2 p$ by introducing OptimumP2P, a novel gossip algorithm that leverages the capabilities of Random Linear Network Coding (RLNC) to expedite the dissemination of information in a peer-to-peer (P2P) network. Preliminary research from the Ethereum Foundation has demonstrated the use of RLNC in the significant improvement in the block propagation time [15]. Here we present extensive evaluation results both in simulation and real-world environments that demonstrate the performance gains of OptimumP2P over the Gossipsub protocol.

Visual tokenization via auto-encoding empowers state-of-the-art image and video generative models by compressing pixels into a latent space. However, questions remain about how auto-encoder design impacts reconstruction and downstream generative performance. This work explores scaling in auto-encoders for reconstruction and generation by replacing the convolutional backbone with an enhanced Vision Transformer for Tokenization (ViTok). We find scaling the auto-encoder bottleneck correlates with reconstruction but exhibits a nuanced relationship with generation. Separately, encoder scaling yields no gains, while decoder scaling improves reconstruction with minimal impact on generation. As a result, we determine that scaling the current paradigm of auto-encoders is not effective for improving generation performance. Coupled with Diffusion Transformers, ViTok achieves competitive image reconstruction and generation performance on 256p and 512p ImageNet-1K. In videos, ViTok achieves SOTA reconstruction and generation performance on 16-frame 128p UCF-101.

Speech embeddings often retain sensitive attributes such as speaker identity, accent, or demographic information, posing risks in biased model training and privacy leakage. We propose WavShape, an information-theoretic speech representation learning framework that optimizes embeddings for fairness and privacy while preserving task-relevant information. We leverage mutual information (MI) estimation using the Donsker-Varadhan formulation to guide an MI-based encoder that systematically filters sensitive attributes while maintaining speech content essential for downstream tasks. Experimental results on three known datasets show that WavShape reduces MI between embeddings and sensitive attributes by up to 81% while retaining 97% of task-relevant information. By integrating information theory with self-supervised speech models, this work advances the development of fair, privacy-aware, and resource-efficient speech systems.

Deepfake (DF) attacks pose a growing threat as generative models become increasingly advanced. However, our study reveals that existing DF datasets fail to deceive human perception, unlike real DF attacks that influence public discourse. It highlights the need for more realistic DF attack vectors. We introduce PhonemeFake (PF), a DF attack that manipulates critical speech segments using language reasoning, significantly reducing human perception by up to 42% and benchmark accuracies by up to 94%. We release an easy-to-use PF dataset on HuggingFace and open-source bilevel DF segment detection model that adaptively prioritizes compute on manipulated regions. Our extensive experiments across three known DF datasets reveal that our detection model reduces EER by 91% while achieving up to 90% speed-up, with minimal compute overhead and precise localization beyond existing models as a scalable solution.

In this paper, we consider aK-user interference channel where interference among the users is neither too strong nor too weak, a scenario that is relatively underexplored in the literature. We propose a novel deep learning-based approach to design the encoder and decoder functions that aim to maximize the sumrate of the interference channel for discrete constellations. We first consider the MaxSINR algorithm, a state-of-the-art linear scheme for Gaussian inputs, as the baseline and then propose a modified version of the algorithm for discrete inputs. We then propose a neural network-based approach that learns a non-linear constellation mapping with the objective of maximizing the sumrate. We provide numerical results to show that the constellations learned by the neural network-based approach provide enhanced alignments, not just in beamforming directions but also in terms of the effective constellation at the receiver, thereby leading to improved sum-rate performance.

With the exponential growth in data volume and the emergence of data-intensive applications, particularly in the field of machine learning, concerns related to resource utilization, privacy, and fairness have become paramount. This paper focuses on the textual domain of data and addresses challenges regarding encoding sentences to their optimized representations through the lens of information-theory. In particular, we use empirical estimates of mutual information, using the Donsker-Varadhan definition of Kullback-Leibler divergence. Our approach leverages this estimation to train an information-theoretic sentence embedding, called TexShape, for (task-based) data compression or for filtering out sensitive information, enhancing privacy and fairness. In this study, we employ a benchmark language model for initial text representation, complemented by neural networks for information-theoretic compression and mutual information estimations. Our experiments demonstrate significant advancements in preserving maximal targeted information and minimal sensitive information over adverse compression ratios, in terms of predictive accuracy of downstream models that are trained using the compressed data.

We introduce OpenDebateEvidence, a comprehensive dataset for argument miningand summarization sourced from the American Competitive Debate community.This dataset includes over 3.5 million documents with rich metadata, making itone of the most extensive collections of debate evidence. OpenDebateEvidencecaptures the complexity of arguments in high school and college debates, pro-viding valuable resources for training and evaluation. Our extensive experimentsdemonstrate the efficacy of fine-tuning state-of-the-art large language models forargumentative abstractive summarization across various methods, models, anddatasets. By providing this comprehensive resource, we aim to advance com-putational argumentation and support practical applications for debaters, edu-cators, and researchers. OpenDebateEvidence is publicly available to supportfurther research and innovation in computational argumentation. Access it here:https://huggingface.co/datasets/Yusuf5/OpenCaselist.

Characterizing self-interference is essential to the design and evaluation of in-band full-duplex communication systems. Until now, little has been understood about this coupling in full-duplex systems operating at millimeter wave (mmWave) frequencies, and it has been shown that the highly-idealized models proposed for such do not align with practice. This work presents the first spatial and statistical model of mmWave self-interference backed by measurements, enabling engineers to draw realizations that exhibit the large-scale and small-scale spatial characteristics observed in our nearly 6.5 million measurements taken at 28 GHz. Core to our model is its use of system and model parameters having real-world meaning, which facilitates its extension to systems beyond our own phased array platform through proper parameterization. We demonstrate this by collecting nearly 13 million additional measurements to show that our model can generalize to two other system configurations. We assess our model by comparing it against actual measurements to confirm its ability to align spatially and in distribution with real-world self-interference. In addition, using both measurements and our model of self-interference, we evaluate an existing beamforming-based full-duplex mmWave solution to illustrate that our model can be reliably used to design new solutions and validate the performance improvements they may offer.

This work develops LoneSTAR, a novel enabler of full-duplex millimeter wave (mmWave) communication systems through the design of analog beamforming codebooks. LoneSTAR codebooks deliver high beamforming gain and broad coverage while simultaneously reducing the self-interference coupled by transmit and receive beams at a full-duplex mmWave transceiver. Our design framework accomplishes this by tolerating some variability in transmit and receive beamforming gain to strategically shape beams that reject self-interference spatially while accounting for digitally-controlled analog beamforming networks and self-interference channel estimation error. By leveraging the coherence time of the self-interference channel, a mmWave system can use the same LoneSTAR design over many time slots to serve several downlink-uplink user pairs in a full-duplex fashion without the need for additional self-interference cancellation. Compared to those using conventional codebooks, full-duplex mmWave systems employing LoneSTAR codebooks can mitigate higher levels of self-interference, tolerate more cross-link interference, and demand lower SNRs in order to outperform half-duplex operation—all while supporting beam alignment. This makes LoneSTAR a potential standalone solution for enabling simultaneous transmission and reception in mmWave systems, from which it derives its name.

Modern millimeter wave (mmWave) communication systems rely on beam alignment to deliver sufficient beamforming gain to close the link between devices. We present a novel beam selection methodology for multi-panel, full-duplex mmWave systems, which we call Steer, that delivers high beamforming gain while significantly reducing the full-duplex self-interference coupled between the transmit and receive beams. Steer does not necessitate changes to conventional beam alignment methodologies nor additional over-the-air feedback, making it compatible with existing cellular standards. Instead, Steer uses conventional beam alignment to identify the general directions beams should be steered, and then it makes use of a minimal number of self-interference measurements to jointly select transmit and receive beams that deliver high gain in these directions while coupling low self-interference. We implement Steer on an industry-grade 28 GHz phased array platform and use further simulation to show that full-duplex operation with beams selected by Steer can notably outperform both half-duplex and full-duplex operation with beams chosen via conventional beam selection. For instance, Steer can reliably reduce self-interference by more than 20 dB and improve SINR by more than 10 dB, compared to conventional beam selection. Our experimental results highlight that beam alignment can be used not only to deliver high beamforming gain in full-duplex mmWave systems but also to mitigate self-interference to levels near or below the noise floor, rendering additional self-interference cancellation unnecessary with Steer.

We present measurements and analysis of self-interference in multi-panel millimeter wave (mmWave) full-duplex communication systems at 28 GHz. In an anechoic chamber, we measure the self-interference power between the input of a transmitting phased array and the output of a colocated receiving phased array, each of which is electronically steered across a number of directions in azimuth and elevation. These self-interference power measurements shed light on the potential for a full-duplex communication system to successfully receive a desired signal while transmitting in-band. Our nearly 6.5 million measurements illustrate that more self-interference tends to be coupled when the transmitting and receiving phased arrays steer their beams toward one another but that slight shifts in steering direction (on the order of one degree) can lead to significant fluctuations in self-interference power. We analyze these measurements to characterize the spatial variability of self-interference to better quantify and statistically model this sensitivity. Our analyses and statistical results can be useful references when developing and evaluating mmWave full-duplex systems and motivate a variety of future topics including beam selection, beamforming codebook design, and self-interference channel modeling.

Efficient modeling of relational data arising in physical, social, and information sciences is challenging due to complicated dependencies within the data. In this work we build off of semi-implicit graph variational auto-encoders to capture higher order statistics in a low-dimensional graph latent representation. We incorporate hyperbolic geometry in the latent space through a Poincare embedding to efficiently represent graphs exhibiting hierarchical structure. To address the naive posterior latent distribution assumptions in classical variational inference, we use semi-implicit hierarchical variational Bayes to implicitly capture posteriors of given graph data, which may exhibit heavy tails, multiple modes, skewness, and highly correlated latent structures. We show that the existing semi-implicit variational inference objective provably reduces information in the observed graph. Based on this observation, we estimate and add an additional mutual information term to the semi-implicit variational inference learning objective to capture rich correlations arising between the input and latent spaces. We show that the inclusion of this regularization term in conjunction with the \poincare embedding boosts the quality of learned high-level representations and enables more flexible and faithful graphical modeling. We experimentally demonstrate that our approach outperforms existing graph variational auto-encoders both in Euclidean and in hyperbolic spaces for edge link prediction and node classification.

This paper develops a novel methodology for designing analog beamforming codebooks for full-duplex millimeter wave (mmWave) transceivers, the first such codebooks to the best of our knowledge. Our design reduces the self-interference coupled by transmit-receive beam pairs and simultaneously delivers high beamforming gain over desired coverage regions, allowing mmWave full-duplex systems to support beam alignment while minimizing self-interference. To do so, our methodology allows some variability in beamforming gain to strategically shape beams that reject self-interference while still having substantial gain. We present an algorithm for approximately solving our codebook design problem while accounting for the non-convexity posed by digitally-controlled phase shifters and attenuators. Numerical results suggest that our design can outperform or nearly match existing codebooks in sum spectral efficiency across a wide range of self-interference power levels. Results show that our design offers an extra 20–50 dB of robustness to selfinterference, depending on hardware constraints.

In this paper, we develop a framework for an autoencoder based transmission strategy for achieving distributed interference alignment and optimal power allocation in a multiuser interference channel. The users in the interference channel have access to the local channel state information only. We compare the explicit schemes, such as MaxSINR [1], against the autoencoder schemes. We find that the MaxSINR schemes outperform the autoencoder networks which are either jointly or distributively trained from scratch. However, we find that the autoencoders which are pretrained with the beamforming vectors and the power allocation obtained from the explicit schemes outperform the explicit schemes when the interference gets stronger. The explicit schemes perform well as they are effective in choosing the set of users which are to be suppressed. The pretrained autoencoders benefit from this initialization, and also from the fact that end to end training can improve their performance even further. We showcase our performance comparison results for 5 user interference channels with different levels of interference.

Full-duplex millimeter wave (mmWave) communication has shown increasing promise for self-interference cancellation via hybrid precoding and combining. This paper proposes a novel mmWave multiple-input multiple-output (MIMO) design for configuring the analog and digital beamformers of a full-duplex transceiver. This work is the first to holistically consider the key practical constraints of analog beamforming codebooks, a minimal number of radio frequency (RF) chains, limited channel knowledge, beam alignment, and a limited receive dynamic range. To prevent self-interference from saturating receive components, such as LNAs and ADCs, a design framework is developed that limits the degree of self-interference on a per-antenna and per-RF chain basis. We present a means for constructing analog beamforming candidates from beam alignment measurements to afford our design greater flexibility in its aim to reduce self-interference. Numerical results evaluate the design in a variety of settings and validate the need to prevent receiver-side saturation. These results and corresponding insights serve as useful design references and benchmarks for practical full-duplex mmWave transceivers.

The wide bandwidths offered at millimeter-wave (mmWave) frequencies have made them an attractive choice for future wireless communication systems. Recent works have presented beamforming strategies for enabling in-band full-duplex (FD) capability at mmWave even under the constraints of hybrid beamforming, extending the exciting possibilities of next-generation wireless. Existing mmWave FD designs, however, do not consider frequency-selective mmWave channels. Wideband communication at mmWave suggests that frequency-selectivity will likely be of concern since communication channels will be on the order of hundreds of megahertz or more. This has motivated the work of this paper, in which we present a frequency-selective beamforming design to enable practical wideband mmWave FD applications. In our designs, we account for the challenges associated with hybrid analog/digital beamforming such as phase shifter resolution, a desirably low number of radio frequency (RF) chains, and the frequency-flat nature of analog beamformers. We use simulation to validate our work, which indicates that spectral efficiency gains can be achieved with our design by enabling simultaneous transmission and reception in-band.

Variational autoencoders (VAE) have ushered in an new era of unsupervised learning methods for complex distributions. Although these techniques are elegant in their approach, they are typically not useful for representation learning. In this work, we propose a simple yet powerful class of VAEs that simultaneously result in meaningful learned representations. Our solution is to combine traditional VAEs with mutual information maximization, with the goal to enhance amortized inference in VAEs using Information Theoretic techniques. We call this approach InfoMax-VAE, and such an approach can significantly boost the quality of learned high-level representations. We realize this through explicit maximization of information measures associated with the representation. Using extensive experiments on varied datasets and setups, we show that InfoMax-VAE outperforms contemporary popular approaches, including Info- VAE and β-VAE.

We study the problem of discovering the simplest latent variable that can make two observed discrete variables conditionally independent. The minimum entropy required for such a latent is known as common entropy in information theory. We extend this notion to Renyi common entropy by minimizing the Renyi entropy of the latent variable. To efficiently compute common entropy, we propose an iterative algorithm that can be used to discover the trade-off between the entropy of the latent variable and the conditional mutual information of the observed variables. We show two applications of common entropy in causal inference: First, under the assumption that there are no low-entropy mediators, it can be used to distinguish direct causation from spurious correlation among almost all joint distributions on simple causal graphs with two observed variables. Second, common entropy can be used to improve constraint-based methods such as PC or FCI algorithms in the small-sample regime, where these methods are known to struggle. We propose a modification to these constraint-based methods to assess if a separating set found by these algorithms are valid using common entropy. We finally evaluate our algorithms on synthetic and real data to establish their performance.

In this paper, the impact of nonlinear distortions created by coherent combination on the spur-free dynamic range (SFDR) and response stability of microwave photonic (MWP) systems is studied. High SFDR is one of the key requirements in demanding modern communication networks which is usually limited by the nonlinearity of active devices. However, we demonstrate that even purely passive devices can generate nonlinear distortion when modulated optical signals coherently combine on photonic integrated circuits (PIC) or in fiber- based systems. This type of combination is more frequent in PICs since the total signal path on the chip is usually shorter than the coherence length of the laser source. Two different major types of coherent interference, Fabry-Perot (FP) and Mach-Zehnder (MZ), are considered and the induced nonlinearity is simulated for a directly intensity modulated optical signal. Two-tone method is employed to characterize intermodulation (IMD) products added to the signal. Based on the simulation results in the case of FP interference, the dynamic range of a link with 30% optical modulation index (OMI) and reflections as low as - 20 dB can be limited to 90.32 dB.Hz1/2or 118.89 dB.Hz2/3, respectively, by SFDR2or SDFR3rather than the distortions of active devices. Also, the output signal can be dominated by nonlinear distortions even higher than the fundamental signal when MZ interference happens. Finally, the response instability and environmental dependency of the link is discussed based on the simulation results.

In recent years, there has been extensive research on millimeter-wave (mmWave) communication and on in-band full-duplex (FD) communication, but work on the combination of the two is relatively lacking. FD mmWave systems could offer increased spectral efficiency and decreased latency while also suggesting the redesign of existing mmWave applications. While FD technology has been well- explored for sub-6 GHz systems, the developed methods do not translate well to mmWave. This turns us to a method called beamforming cancellation (BFC), where the highly directional mmWave beams are steered to mitigate self-interference (SI) and enable simultaneous transmission and reception in- band. In this paper, we present BFC designs for two fully-connected hybrid beamforming scenarios, both of which sufficiently suppress the SI such that the sum spectral efficiency approaches that of a SI- free FD system. A simulation and its results are then used to verify our designs.

Over the past five years, the rewards associated with mining Proof-of-Work blockchains have increased substantially. As a result, miners are heavily incentivized to design and utilize Application Specific Integrated Circuits (ASICs) that can compute hashes far more efficiently than existing general purpose hardware. Currently, it is difficult for most users to purchase and operate ASICs due to pricing and availability constraints, resulting in a relatively small number of miners with respect to total user base for most popular cryptocurrencies. In this work, we aim to invert the problem of ASIC development by constructing a Proof-of-Work function for which an existing general purpose processor (GPP, such as an x86 IC) is already an optimized ASIC. In doing so, we will ensure that any would-be miner either already owns an ASIC for the Proof-of-Work system they wish to participate in or can attain one at a competitive price with relative ease. In order to achieve this, we present HashCore, a Proof-of-Work function composed of "widgets" generated pseudo-randomly at runtime that each execute a sequence of general purpose processor instructions designed to stress the computational resources of such a GPP. The widgets will be modeled after workloads that GPPs have been optimized for, for example, the SPEC CPU 2017 benchmark suite for x86 ICs, in a technique we refer to as inverted benchmarking. We provide a proof that HashCore is collision-resistant regardless of how the widgets are implemented. We observe that GPP designers/developers essentially create an ASIC for benchmarks such as SPEC CPU 2017. By modeling HashCore after such benchmarks, we create a Proof-of-Work function that can be run most efficiently on a GPP, resulting in a more accessible, competitive, and balanced mining market.

We consider the minimum cost intervention design problem: Given the essential graph of a causal graph and a cost to intervene on a variable, identify the set of interventions with minimum total cost that can learn any causal graph with the given essential graph. We first show that this problem is NP-hard. We then prove that we can achieve a constant factor approximation to this problem with a greedy algorithm. We then constrain the sparsity of each intervention. We develop an algorithm that returns an intervention design that is nearly optimal in terms of size for sparse graphs with sparse interventions and we discuss how to use it when there are costs on the vertices.

This paper considers a distributed storage system, where multiple storage nodes can be reconstructed simultaneously at a centralized location. This centralized multi-node repair (CMR) model is a generalization of regenerating codes that allow for bandwidth efficient repair of a single-failed node. This paper focuses on the tradeoff between the amount of data stored and repair bandwidth in the CMR model. In particular, repair bandwidth bounds are derived for the minimum storage multi-node repair (MSMR) and the minimum bandwidth multi-node repair (MBMR) operating points. The tightness of these bounds is analyzed via code constructions. The MSMR point is characterized by codes achieving this point under functional repair for the general set of CMR parameters, as well as with codes enabling exact repair for certain CMR parameters. The MBMR point, on the other hand, is characterized with exact repair codes for all CMR parameters for systems that satisfy a certain entropy accumulation property. Finally, the model proposed here is utilized for the secret sharing problem, where the codes for the multi-node repair problem are used to construct communication efficient secret sharing schemes with the property of bandwidth efficient share repair.

We consider the problem of identifying the causal direction between two discrete random variables using observational data. Unlike previous work, we keep the most general functional model but make an assumption on the unobserved exogenous variable: Inspired by Occam's razor, we assume that the exogenous variable is simple in the true causal direction. We quantify simplicity using Renyi entropy. Our main result is that, under natural assumptions, if the exogenous variable has low H0 entropy (cardinality) in the true direction, it must have high H0 entropy in the wrong direction. We establish several algorithmic hardness results about estimating the minimum entropy exogenous variable. We show that the problem of finding the exogenous variable with minimum H1 entropy (Shannon Entropy) is equivalent to the problem of finding minimum joint entropy given n marginal distributions, also known as minimum entropy coupling problem. We propose an efficient greedy algorithm for the minimum entropy coupling problem, that for n=2 provably finds a local optimum. This gives a greedy algorithm for finding the exogenous variable with minimum Shannon entropy. Our greedy entropy-based causal inference algorithm has similar performance to the state of the art additive noise models in real datasets. One advantage of our approach is that we make no use of the values of random variables but only their distributions. Our method can therefore be used for causal inference for both ordinal and also categorical data, unlike additive noise models.

We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton. We show that this problem is solvable in polynomial time. Later, we consider the case when the number of interventions is limited. For this case, we provide polynomial time algorithms when the skeleton is a tree or a clique tree. For a general chordal skeleton, we develop an efficient greedy algorithm, which can be improved when the causal graph skeleton is an interval graph.

We derive inner and outer bounds on the capacity region for a class of three-user partially connected interference channels. We focus on the impact of topology, interference alignment, and interplay between interference and noise. The representative channels we consider are the ones that have clear interference alignment gain. For these channels, Z-channel type outer bounds are tight to within a constant gap from capacity. We present near-optimal achievable schemes based on rate-splitting, lattice alignment, and successive decoding.

We study the problem of identifying the causal relationship between two discrete random variables from observational data. We recently proposed a novel framework called entropie causality that works in a very general functional model but makes the assumption that the unobserved exogenous variable has small entropy in the true causal direction. This framework requires the solution of a minimum entropy coupling problem: Given marginal distributions of m discrete random variables, each on n states, find the joint distribution with minimum entropy, that respects the given marginals. This corresponds to minimizing a concave function of nmvariables over a convex polytope defined by nm linear constraints, called a transportation polytope. Unfortunately, it was recently shown that this minimum entropy coupling problem is NP-hard, even for 2 variables with n states. Even representing points (joint distributions) over this space can require exponential complexity (in n, m) if done naively. In our recent work we introduced an efficient greedy algorithm to find an approximate solution for this problem. In this paper we analyze this algorithm and establish two results: that our algorithm always finds a local minimum and also is within an additive approximation error from the unknown global optimum.

This paper studies the haplotype assembly problem from an information-theoretic perspective. In the human genome, a haplotype is a sequence of nucleotide bases on a chromosome that differ from the bases in the corresponding positions on the other chromosome in a homologous pair. Haplotype sequences can conveniently be represented by binary strings, which enable us to transform the bioinformatics problem of haplotype assembly into an equivalent information-theoretic problem. Information about the order of bases in a genome is readily inferred using short reads provided by high-throughput DNA sequencing technologies. Performing haplotype assembly is challenging due to limited lengths of the reads and the presence of sequencing errors. In this paper, the recovery of the target pair of haplotype sequences using short reads is transformed into an equivalent joint source-channel coding problem. Two binary messages, representing haplotypes and chromosome memberships of reads, are encoded and transmitted over a channel with erasures and errors, where the channel model reflects salient features of high-throughput sequencing. The focus of this paper is on determining the required number of reads for reliable haplotype reconstruction. For the error-free reading case, erasure decoding is shown to be one of the optimal algorithms enabling reliable haplotype assembly. For the erroneous reading case, spectral partitioning is proved to be an efficient algorithm with orderwise optimal bounds.

Crowdsourcing of jobs to online freelance platforms is rapidly gaining popularity. Most crowdsourcing platforms are uncontrolled and offer freedom to customers and freelancers to choose each other. This works well for unskilled jobs (e.g., image classification) with no specific quality requirement since freelancers are functionally identical. For skilled jobs (e.g., software development) with specific quality requirements, however, this does not ensure that the maximum number of job requests is satisfied. In this paper, we determine the capacity of regulated freelance systems, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom for customers and freelancers, we propose simple schemes compatible with the operation of current crowdsourcing platforms that approximately achieve capacity. Furthermore, for settings where the number of job requests exceeds capacity, we propose a scheme that is agnostic of that information, but is optimal and fair in declining jobs without wait.

This paper presents a novel retransmission strategy for communication networks based on index coding. The particular example of OFDMA downlink networks is taken to illustrate its efficacy. The benefits and challenges in using index coding as a transmission strategy are highlighted. The paper concludes with characterization of expected index coding gain in terms of channel parameters.

Many companies now use crowdsourcing to leverage external (as well as internal) crowds to perform specialized work, and so methods of improving efficiency are critical. Tasks in crowdsourcing systems with specialized work have multiple steps and each step requires multiple skills. Steps may have different flexibilities in terms of obtaining service from one or multiple agents, due to varying levels of dependency among parts of steps. Steps of a task may have precedence constraints among them. Moreover, there are variations in loads of different types of tasks requiring different skill-sets and availabilities of different types of agents with different skill-sets. Considering these constraints together necessitates the design of novel schemes to allocate steps to agents. In addition, large crowdsourcing systems require allocation schemes that are simple, fast, decentralized and offer customers (task requesters) the freedom to choose agents. In this work we study the performance limits of such crowdsourcing systems and propose efficient allocation schemes that provably meet the performance limits under these additional requirements. We demonstrate our algorithms on data from a crowdsourcing platform run by a non-profit company and show significant improvements over current practice.

This paper considers a distributed storage system, where multiple storage nodes can be reconstructed simultaneously at a centralized location. This centralized multi-node repair (CMR) model is a generalization of regenerating codes that allow for bandwidth-efficient repair of a single failed node. This work focuses on the trade-off between the amount of data stored and repair bandwidth in this CMR model. In particular, repair bandwidth bounds are derived for the minimum storage multi-node repair (MSMR) and the minimum bandwidth multi-node repair (MBMR) operating points. The tightness of these bounds are analyzed via code constructions. The MSMR point is characterized through codes achieving this point under functional repair for general set of CMR parameters, as well as with codes enabling exact repair for certain CMR parameters. The MBMR point, on the other hand, is characterized with exact repair codes for all CMR parameters for systems that satisfy a certain entropy accumulation property.

This paper presents a polar coding scheme to achieve secrecy in block fading binary symmetric wiretap channels without the knowledge of instantaneous channel state information (CSI) at the transmitter. For this model, a coding scheme that hierarchically utilizes polar codes is presented. In particular, on the polarization of different binary symmetric channels over different fading blocks, each channel use is modeled as an appropriate binary erasure channel over fading blocks. Polar codes are constructed for both coding over channel uses for each fading block and coding over fading blocks for certain channel uses. In order to guarantee security, random bits are introduced at appropriate places to exhaust the observations of the eavesdropper. It is shown that this coding scheme, without instantaneous CSI at the transmitter, is secrecy capacity achieving for the simultaneous fading scenario. For the independent fading case, the capacity is achieved when the fading realizations for the eavesdropper channel are always degraded with respect to the receiver. For the remaining cases, the gap between lower and upper bounds is analyzed. Remarkably, for the scenarios where the secrecy capacity is achieved, the results imply that the instantaneous CSI does not increase the secrecy capacity.

This paper considers a state dependent broadcast channel with one transmitter, Alice, and two receivers, Bob and Eve. The problem is to effectively convey (“amplify”) the channel state sequence to Bob while “masking” it from Eve. The extent to which the state sequence cannot be masked from Eve is referred to as leakage. This can be viewed as a secrecy problem, where we desire that the channel state itself be minimally leaked to Eve while being communicated to Bob. This paper is aimed at characterizing the tradeoff region between amplification and leakage rates for such a system. An achievable coding scheme is presented, wherein the transmitter transmits a partial state information over the channel to facilitate the amplification process. For the case when Bob observes a stronger signal than Eve, the achievable coding scheme is enhanced with secure refinement. Outer bounds on the tradeoff region are also derived, and used in characterizing some special case results. In particular, the optimal amplification-leakage rate difference, called as differential amplification capacity, is characterized for the reversely degraded discrete memoryless channel, the degraded binary, and the degraded Gaussian channels. In addition, for the degraded Gaussian model, the extremal corner points of the tradeoff region are characterized, and the gap between the outer bound and achievable rate-regions is shown to be less than half a bit for a wide set of channel parameters.

Microarchitectural resources such as caches and predictors can be used to leak information across security domains. Significant prior work has demonstrated attacks and defenses for specific types of such microarchitectural side and covert channels. In this paper, we introduce a general mathematical study of microarchitectural channels using information theory. Our conceptual contribution is a simple mathematical abstraction that captures the common characteristics of all microarchitectural channels. We call this the Bucket model and it reveals that microarchitectural channels are fundamentally different from side and covert channels in networking. We then quantify the communication capacity of several microarchitectural covert channels (including channels that rely on performance counters, AES hardware and memory buses) and measure bandwidths across both KVM based heavy-weight virtualization and light-weight operating-system level isolation. We demonstrate channel capacities that are orders of magnitude higher compared to what was previously considered possible. Finally, we introduce a novel way of detecting intelligent adversaries that try to hide while running covert channel eavesdropping attacks. Our method generalizes a prior detection scheme (that modeled static adversaries) by introducing noise that hides the detection process from an intelligent eavesdropper.

Traditional models in opinion dynamics involve agents updating their opinions based on the opinions of their neighbors in a static social-graph, regardless of their differences in opinions. In contrast, the bounded confidence opinion dynamics does not presume a static interaction graph, and instead models interactions between those agents that share similar opinions (i.e., are close to one another, capturing online discussion groups and conventional meetings). We generalize the bounded confidence opinion dynamics model by incorporating pairwise stochastic interactions based on opinion differences as well as the self or endogenous evolution of the agent opinions, which is represented by a random process. We analytically characterize the conditions under which this stochastic dynamics is stable in an appropriate sense. This characterization relates well to what is observed in social systems. Moreover, this generalization sheds light on dynamics that combine aspects of graph-based updates and bounded confidence models.

Crowdsourcing of jobs to online freelance markets is rapidly gaining popularity. Most crowdsourcing platforms are uncontrolled and offer freedom to customers and freelancers to choose each other. This works well for unskilled jobs (e.g., image classification) with no specific quality requirement since freelancers are functionally identical. For skilled jobs (e.g., software development) with specific requirements, however, this does not ensure the maximum number of job requests is satisfied. In this work we determine the capacity of freelance markets, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom of choice for customers and freelancers, we propose simple schemes compatible with the operation of current crowd-sourcing platforms that approximately achieve capacity. Further, for settings where job requests exceed capacity, we propose an optimal and fair scheme for declining jobs without wait.

We develop achievable sum rate expressions for the Gaussian X channel at finite SNR using layered lattice coding with interference alignment. For different regimes of channel parameter h, we consider different decoding strategies including successive decoding and compute-and-forward decoding. For some regimes of h, we characterize the sum-rate capacity to within constant bits by using successive decoding. For a set of h that satisfy certain feasibility conditions, we show that compute-and-forward decoding outperforms a timesharing MAC-based lower bound. However, we find that the direct application of compute-and-forward results in high sensitivity of computation rates to the variation of h. Therefore, we introduce a channel steering method to significantly reduce the fluctuation in achievable sum-rate and consistently achieve high rates. We subsequently compare the achievable sum-rate with a new upper bound to demonstrate the value of channel steering.

This paper presents a polar coding scheme for fading wiretap channels that achieves reliability as well as security without the knowledge of instantaneous channel state information at the transmitter. Specifically, a block fading model is considered for the wiretap channel that consists of a transmitter, a receiver, and an eavesdropper; and only the information regarding the statistics (i.e., distribution) of the channel state information is assumed at the transmitter. For this model, a coding scheme that hierarchically utilizes polar codes is presented in order to address channel state variation. In particular, on polarization of different binary symmetric channels over different fading blocks, each channel use (corresponding to a possibly different polarization) is modeled as an appropriate binary erasure channel over fading blocks. Polar codes are constructed for both coding over channel uses for each fading block and coding over fading blocks for certain channel uses. In order to guarantee security, message bits are transmitted such that they can be reliably decoded at the receiver, and random bits are introduced to exhaust the observations of the eavesdropper. It is shown that this coding scheme, without instantaneous channel state information at the transmitter, is secrecy capacity achieving for the corresponding fading binary symmetric wiretap channel.

We consider the problem of learning causal networks with interventions, when each intervention is limited in size under Pearl's Structural Equation Model with independent errors (SEM-IE). The objective is to minimize the number of experiments to discover the causal directions of all the edges in a causal graph. Previous work has focused on the use of separating systems for complete graphs for this task. We prove that any deterministic adaptive algorithm needs to be a separating system in order to learn complete graphs in the worst case. In addition, we present a novel separating system construction, whose size is close to optimal and is arguably simpler than previous work in combinatorics. We also develop a novel information theoretic lower bound on the number of interventions that applies in full generality, including for randomized adaptive learning algorithms. For general chordal graphs, we derive worst case lower bounds on the number of interventions. Building on observations about induced trees, we give a new deterministic adaptive algorithm to learn directions on any chordal skeleton completely. In the worst case, our achievable scheme is an $\alpha$-approximation algorithm where $\alpha$ is the independence number of the graph. We also show that there exist graph classes for which the sufficient number of experiments is close to the lower bound. In the other extreme, there are graph classes for which the required number of experiments is multiplicatively $\alpha$ away from our lower bound. In simulations, our algorithm almost always performs very close to the lower bound, while the approach based on separating systems for complete graphs is significantly worse for random chordal graphs.

Graphical models and related algorithmic tools such as belief propagation have proven to be useful tools in (approximately) solving combinatorial optimization problems across many application domains. A particularly combinatorially challenging problem is that of determining solutions to a set of simultaneous congruences. Specifically, a continuous source is encoded into multiple residues with respect to distinct moduli, and the goal is to recover the source efficiently from noisy measurements of these residues. This problem is of interest in multiple disciplines, including neural codes, decentralized compression in sensor networks, and distributed consensus in information and social networks. This letter reformulates the recovery problem as an optimization over binary latent variables. Then we present a belief propagation algorithm, a layered variant of affinity propagation, to solve the problem. The underlying encoding structure of multiple congruences naturally results in a layered graphical model for the problem, over which the algorithms are deployed, resulting in a layered affinity propagation (LAP) solution. First, the convergence of LAP to an approximation of the maximum likelihood (ML) estimate is shown. Second, numerical simulations show that LAP converges within a few iterations and that the mean square error of LAP approaches that of the ML estimation at high signal-to-noise ratios.

We consider the problem of network coding across three unicast sessions over a directed acyclic graph, where the sender and receiver of each unicast session are both connected to the network via a single edge of unit capacity. We consider a network model in which the middle of the network can only perform random linear network coding, and restrict our approaches to precoding-based linear schemes, where the senders use precoding matrices to encode source symbols. We adapt a precoding-based interference alignment technique, originally developed for the wireless interference channel, to construct a precoding-based linear scheme, which we refer to as precoding-based network alignment scheme (PBNA). A primary difference between this setting and the wireless interference channel is that the network topology can introduce dependencies among the elements of the transfer matrix, which we refer to as coupling relations, and can potentially affect the achievable rate of PBNA. We identify all these coupling relations and interpret them in terms of network topology. We then present polynomial-time algorithms to check the presence of these coupling relations in a particular network. Finally, we show that, depending on the coupling relations present in the network, the optimal symmetric rate achieved by precoding-based linear scheme can take only three possible values, all of which can be achieved by PBNA.

This paper presents and analyzes a novel concatenated coding scheme for enabling error resilience in two distributed storage settings: one being storage using existing regenerating codes and the second being storage using locally repairable codes. The concatenated coding scheme brings together a maximum rank distance code as an outer code and either a globally regenerating or a locally repairable code as an inner code. In addition, error resilience for combination of locally repairable codes with regenerating codes is considered. This concatenated coding system is designed to handle two different types of adversarial errors: the first type includes an adversary that can replace the content of an affected node only once; while the second type studies an adversary that is capable of polluting data an unbounded number of times. The paper establishes an upper bound on the resilience capacity for a locally repairable code. This paper also proves that the proposed concatenated coding approach attains the upper bound on the resilience capacity in the presence of the first type of adversary for both minimum storage regenerating codes and locally repairable codes. Further, this paper presents mechanisms that combine the presented concatenated coding scheme with subspace signatures to achieve error resilience for the second type of errors.

In this paper, we study the coverage probability of a K-tier multiple-input multiple-output heterogeneous cellular network (MIMO HetNet) assuming (i) zero-forcing precoding at all the base stations (BSs), (ii) Rayleigh fading, (iii) independent Poisson Point Process (PPP) model for the locations of BSs of each tier, and (iv) general cell selection rule that maximizes average received signal-to-interference-plus-noise ratio (SINR) at the users. Our analysis highlights key differences between MIMO HetNets and the more familiar single antenna HetNets in terms of cell selection. While it is challenging to derive exact cell selection rule to maximize average downlink SINR in MIMO HetNets, we show that adding an appropriately chosen per-tier selection bias yields a close approximation. The bias value for each tier is given in closed form. One interpretation of this result is that MIMO HetNets may balance load more naturally across different tiers in certain special cases compared to single antenna HetNets where an artificial selection bias is often needed for load balancing.

Index coding, initially introduced within theoretical computer science to address a specialized class of problems, has gained significant interest within communications and networking communities in recent years. Index coding has been shown to be analogous to a large class of challenging wired network coding and wireless multi-terminal problems, the latter class being of primary interest in this paper. Here, a (relaxed) rank minimization based analytic framework is presented for wireless index coding, which represents a first step in a systematic algorithmic approach to index coding for practical use. Further, the paper demonstrates its applicability over a real-world wireless testbed. The scheme operates at the network layer, and can be understood as a (non-trivial) generalization of existing principles of random linear network coding. Experimental results demonstrate that, for a class of network topologies, the rank-minimized index coding system presents a throughput gain of 50 to 100 percent greater than random linear coding for this system.

We consider the problem of learning the underlying graph structure of discrete Markov networks based on power-law graphs, generated using the configuration model. We translate the learning problem into an equivalent channel coding problem and obtain necessary conditions for solvability in terms of problem parameters. In particular, we relate the exponent of the power-law graph to the hardness of the learning problem, and show that more number of samples are required for exact recovery of discrete power-law Markov graphs with small exponent values. We develop an efficient learning algorithm for accurate reconstruction of graph structure of Ising model on power-law graphs. Finally, we show that order-wise optimal number of samples suffice for recovering the exact graph under certain constraints on Ising model parameters and scalings of node degrees.

This paper studies the problem of information symbol availability in codes: we refer to a systematic code as code with (r, t)-availability if every information (systematic) symbol can be reconstructed from t disjoint groups of other code symbols, each of the sizes at most r. This paper shows that it is possible to construct codes that can support a scaling number of parallel reads while keeping the rate to be an arbitrarily high constant. It further shows that this is possible with the minimum Hamming distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a tradeoff between rate, minimum Hamming distance, and availability parameters. Our codes match the aforementioned bound, and their constructions rely on certain combinatorial structures. Resolvable designs provide one way to realize these required combinatorial structures. The two constructions presented in this paper require field sizes, which are linear and exponential in the code length, respectively. From a practical standpoint, our codes are relevant for distributed storage applications involving hot data, i.e., the information, which is frequently accessed by multiple processes in parallel.

A general method of source coding is proposed in this paper, which enables one to reduce the problem of compressing an analog (continuous-valued) source to a set of much simpler problems, compressing discrete sources. Specifically, the focus is on lossy compression of exponential and Laplace sources, which are represented as set of discrete variables through a finite alphabet expansion. Due to the decomposability property of such sources, the resulting random variables post expansion are independent and discrete. Thus, these variables can be considered as independent discrete source coding problems, and the original problem is reduced to coding over these sources with a total distortion constraint. Any feasible solution to this resulting optimization problem corresponds to an achievable rate distortion pair of the original continuous-valued source compression problem. Although finding the optimal solution for a given distortion is not a tractable task, we show that, via a heuristic choice, our expansion coding scheme still presents a good performance in the low distortion regime. Further, by adopting low-complexity codes designed for discrete source coding, the total coding complexity can be reduced for practical implementations.

This paper studies the haplotype assembly problem from an information-theoretic perspective. A haplotype is a sequence of nucleotide bases on a chromosome, often conveniently represented by a binary string, that differ from the bases in the corresponding positions on the other chromosome in a homologous pair. Information about the order of bases in a genome is readily inferred using short reads provided by high-throughput DNA sequencing technologies. Associating reads that cover variant positions with specific chromosomes in a homologous pairs, which enables haplotype assembly, is challenging due to limited lengths of the reads and presence of sequencing errors. In this paper, the recovery of the target pair of haplotype sequences using short reads is rephrased as a joint source-channel coding problem. Two messages, representing haplotypes and chromosome memberships of reads, are encoded and transmitted over a channel with erasures and errors, where the channel model reflects salient features of high-throughput sequencing. The focus of this paper is on determining the required number of reads for reliable haplotype reconstruction, and both the necessary and sufficient conditions are presented with order-wise optimal bounds.

We model and analyze heterogeneous cellular networks with multiple antenna BSs (multi-antenna HetNets) with K classes or tiers of base stations (BSs), which may differ in terms of transmit power, deployment density, number of transmit antennas, number of users served, transmission scheme, and path loss exponent. We show that the cell selection rules in multi-antenna HetNets may differ significantly from the single-antenna HetNets due to the possible differences in multi-antenna transmission schemes across tiers. While it is challenging to derive exact cell selection rules even for maximizing signal-to-interference-plus-noise-ratio (SINR) at the receiver, we show that adding an appropriately chosen tier-dependent cell selection bias in the received power yields a close approximation. Assuming arbitrary selection bias for each tier, simple expressions for downlink coverage and rate are derived. For coverage maximization, the required selection bias for each tier is given in closed form. Due to this connection with biasing, multi-antenna HetNets may balance load more naturally across tiers in certain regimes compared to single-antenna HetNets, where a large cell selection bias is often needed to offload traffic to small cells.

This work presents a polar coding scheme for fading channels, focusing primarily on fading binary symmetric and additive exponential noise channels. For fading binary symmetric channels, a hierarchical coding scheme is presented, utilizing polar coding both over channel uses and over fading blocks. The receiver uses its channel state information (CSI) to distinguish states, thus constructing an overlay erasure channel over the underlying fading channels. By using this scheme, the capacity of a fading binary symmetric channel is achieved without CSI at the transmitter. Noting that a fading AWGN channel with BPSK modulation and demodulation corresponds to a fading binary symmetric channel, this result covers a fairly large set of practically relevant channel settings. For fading additive exponential noise channels, expansion coding is used in conjunction to polar codes. Expansion coding transforms the continuous-valued channel to multiple (independent) discrete-valued ones. For each level after expansion, the approach described previously for fading binary symmetric channels is used. Both theoretical analysis and numerical results are presented, showing that the proposed coding scheme approaches the capacity in the high SNR regime. Overall, utilizing polar codes in this (hierarchical) fashion enables coding without CSI at the transmitter, while approaching the capacity with low complexity.

Regenerating codes enable trading off repair bandwidth for storage in distributed storage systems (DSS). Due to their distributed nature, these systems are intrinsically susceptible to attacks, and they may also be subject to multiple simultaneous node failures. Cooperative regenerating codes allow bandwidth efficient repair of multiple simultaneous node failures. This paper analyzes storage systems that employ cooperative regenerating codes that are robust to (passive) eavesdroppers. The analysis is divided into two parts, studying both minimum bandwidth and minimum storage cooperative regenerating scenarios. First, the secrecy capacity for minimum bandwidth cooperative regenerating codes is characterized. Second, for minimum storage cooperative regenerating codes, a secure file size upper bound and achievability results are provided. These results establish the secrecy capacity for the minimum storage scenario for certain special cases. In all scenarios, the achievability results correspond to exact repair, and secure file size upper bounds are obtained using min-cut analyses over a suitable secrecy graph representation of DSS. The main achievability argument is based on an appropriate precoding of the data to eliminate the information leakage to the eavesdropper.

This paper considers the problem of compressive sensing over a finite alphabet, where the finite alphabet may be inherent to the nature of the data or a result of quantization. We show that there are significant benefits to analyzing the problem while incorporating its finite alphabet nature, versus ignoring it and employing a conventional real alphabet based toolbox. Specifically, when the alphabet is finite, our techniques have a lower sample complexity compared to real-valued compressive sensing for low levels of sparsity, facilitate constructive designs of sensing matrices based on coding-theoretic techniques, and allow for lesser amount of data storage.

Node failures are inevitable in distributed storage systems (DSS). To enable efficient repair when faced with such failures, two main techniques are known: Regenerating codes, i.e., codes that minimize the total repair bandwidth; and codes with locality, which minimize the number of nodes participating in the repair process. This paper focuses on regenerating codes with locality, using pre-coding based on Gabidulin codes, and presents constructions that utilize minimum bandwidth regenerating (MBR) local codes. The constructions achieve maximum resilience (i.e., optimal minimum distance) and have maximum capacity (i.e., maximum rate). Finally, the same pre-coding mechanism can be combined with a subclass of fractional-repetition codes to enable maximum resilience and repair-by-transfer simultaneously.

Regenerating codes enable trading off repair bandwidth for storage in distributed storage systems (DSS). Due to their distributed nature, these systems are intrinsically susceptible to attacks, and they may be susceptible to multiple node failures. This paper analyzes storage systems that employ cooperative regenerating codes that are robust to passive eavesdroppers, and proposes codes achieving the secrecy capacity for the minimum bandwidth cooperative regenerating point. The achievability results correspond to exact repair, and secure file size upper bounds are obtained using mincut analyses over a suitable secrecy graph representation of DSS. The main achievability argument is based on appropriate precoding of the data using MRD (Gabidulin) codes to eliminate any information leakage to the eavesdropper.

This paper presents coding schemes for distributed storage systems (DSS) that are secure against eavesdroppers, while simultaneously enabling efficient node repair (regeneration). Towards this, novel upper bounds on secrecy capacity for minimum storage regenerating (MSR) codes and locally repairable codes (LRCs) are derived. The eavesdropper model considered in this paper incorporates the ability to listen in on data downloaded during ℓ2node repairs in addition to content stored on ℓ1nodes. Finally, this paper presents coding schemes, based on precoding using Gabidulin codes, that achieve the upper bounds on secrecy capacity and characterize the secrecy capacity of DSS for various settings of system parameters.

This paper presents a new explicit construction for locally repairable codes (LRCs) for distributed storage systems which possess all-symbol locality and the largest possible minimum distance, or equivalently, can tolerate the maximum number of node failures. This construction, based on maximum rank distance (MRD) Gabidulin codes, provides new optimal vector and scalar LRCs. In addition, the paper also discusses mechanisms by which codes obtained using this construction can be used to construct LRCs with efficient local repair of failed nodes by combination of LRCs with regenerating codes.

We consider the problem of linear network coding over communication networks, representable by directed acyclic graphs, with multiple groupcast sessions: the network comprises of multiple destination nodes, each desiring messages from multiple sources. We adopt an interference alignment perspective, providing new insights into designing practical network coding schemes as well as the impact of network topology on the complexity of the alignment scheme. In particular, we show that under certain (polynomial-time checkable) constraints on networks with K sources, it is possible to achieve a rate of 1/(L+d+1) per source using linear network coding coupled with interference alignment, where each destination receives messages from L sources (L <; K), and d is a parameter, solely dependent on the network topology, that satisfies 0 ≤ d <; K - L.

A polar coding scheme for fading channels is proposed in this paper. More specifically, the focus is on the Gaussian fading channel with a BPSK modulation, where the equivalent channel is modeled as a binary symmetric channel with varying cross-over probabilities. To deal with variable channel states, a coding scheme of hierarchically utilizing polar codes is proposed. In particular, by observing the polarization of different binary symmetric channels over different fading blocks, each channel use corresponding to a different polarization is modeled as a binary erasure channel such that polar codes could be adopted to encode over blocks. It is shown that the proposed coding scheme, without instantaneous channel state information at the transmitter, achieves the capacity of the corresponding fading binary symmetric channel.

Multimode fibers (MMF) are generally used in short and medium haul optical networks owing to the availability of low cost devices and inexpensive packaging solutions. However, the performance of conventional multimode fibers is limited primarily by the presence of high modal dispersion owing to large core diameters. While electronic dispersion compensation methods improve the bandwidth-distance product of MMFs, they do not utilize the fundamental diversity present in the different modes of the multimode fiber. In this paper, we draw from developments in wireless communication theory and signal processing to motivate the use of vector intensity modulation and signal processing to enable high-data rates over MMFs. Further, we discuss the implementation of a closed-loop system with limited channel state feedback to enable the use of precoding at the transmitter, and show that this technique enhances the performance in a 10 Gb/s MMF link, consisting of 3 km of conventional multimode fiber. Experimental results indicate that vector intensity modulation and direct detection with with two modulators and detectors, along with the use of limited feedback results in a 50% increase over the single laser and detector case.

Multimode fibers (MMFs) offer a cost-effective connection solution for small and medium length networks. However, data rates through multimode fibers are traditionally limited by modal dispersion. Signal processing and Multiple-Input Multiple-Output (MIMO) have been shown to be effective at combating these limitations, but device design for the specific purpose of MIMO in MMFs is still an open issue. This paper utilizes a statistical field propagation model for MMFs to aid the analysis and designs of MMF laser and detector arrays, and aims to improve data rates of the fiber. Simulations reveal that optimal device designs could possess 2-3 times the data carrying capacity of suboptimal ones.

Multi-robot patrol is a fundamental application of multi-robot systems. While much theoretical work exists providing an understanding of the optimal patrol strategy for teams of coordinated homogeneous robots, little work exists on building and evaluating the performance of such systems for real. In this paper, we evaluate the performance of multirobot patrol in a practical outdoor distributed robotic system, and evaluate the effect of different coordination schemes on the performance of the robotic team. The multi-robot patrol algorithms evaluated vary in the level of robot coordination: no coordination, loose coordination, and tight coordination. In addition, we evaluate versions of these algorithms that distribute state information-either individual state, or entire team state (global-view state). Our experiments show that while tight coordination is theoretically optimal, it is not practical in practice. Instead, uncoordinated patrol performs best in terms of average waypoint visitation frequency, though loosely coordinated patrol that shares only individual state performed best in terms of worst-case frequency. Both are significantly better than a loosely coordinated algorithm based on sharing global-view state. We respond to this discrepancy between theory and practice, caused primarily by robot heterogeneity, by extending the theory to account for such heterogeneity, and find that the new theory accounts for the empirical results.

Motivated by an emerging theory of robust low-rank matrix representation, in this paper, we introduce a novel solution for online rigid-body motion registration. The goal is to develop algorithmic techniques that enable a robust, real-time motion registration solution suitable for low-cost, portable 3-D camera devices. Assuming 3-D image features are tracked via a standard tracker, the algorithm first utilizes Robust PCA to initialize a low-rank shape representation of the rigid body. Robust PCA finds the global optimal solution of the initialization, while its complexity is comparable to singular value decomposition. In the online update stage, we propose a more efficient algorithm for sparse subspace projection to sequentially project new feature observations onto the shape subspace. The lightweight update stage guarantees the real-time performance of the solution while maintaining good registration even when the image sequence is contaminated by noise, gross data corruption, outlying features, and missing data. The state-of-the-art accuracy of the solution is validated through extensive simulation and a real-world experiment, while the system enjoys one to two orders of magnitude speed-up compared to wellestablished RANSAC solutions.

Autonomous intersection management (AIM) is a new intersection control protocol that exploits the capabilities of autonomous vehicles to control traffic at intersections in a way better than traffic signals and stop signs. A key assumption of this protocol is that vehicles can always follow their trajectories. But mechanical failures can occur in real life, causing vehicles to deviate from their trajectories. A previous approach for handling mechanical failure was to prevent vehicles from entering the intersection after the failure. However, this approach cannot prevent collisions among vehicles already in the intersection or too close to stop because (1) the lack of coordination among vehicles can cause collisions during the execution of evasive actions; and (2) the intersection may not have enough room for evasive actions. In this paper, we propose a preemptive approach that pre-computes evasion plans for several common types of mechanical failures before vehicles enter an intersection. This preemptive approach is necessary because there are situations in which vehicles cannot evade without pre-allocation of space for evasion. We present a modified AIM protocol and demonstrate the effectiveness of evasion plan execution on a miniature autonomous intersection testbed.

This paper presents a rate distortion approach to Markov graph learning. It provides lower bounds on the number of samples required for any algorithm to learn the Markov graph structure of a probability distribution, up to edit distance. We first prove a general result for any probability distribution, and then specialize it for Ising and Gaussian models. In particular, for both Ising and Gaussian models on p variables with degree at most d, we show that at least Ω((d - s/p)log p) samples are required for any algorithm to learn the graph structure up to edit distance s. Our bounds represent a strong converse; i.e., we show that for a lower number of samples, the probability of error goes to 1 as the problem size increases. These results show that substantial gains in sample complexity may not be possible without paying a significant price in edit distance error.

A general method of coding over expansions is proposed, which allows one to reduce the highly non-trivial problem of coding over continuous channels to a much simpler discrete ones. More specifically, the focus is on the additive exponential noise (AEN) channel, for which the (binary) expansion of the (exponential) noise random variable is considered. It is shown that each of the random variables in the expansion corresponds to independent Bernoulli random variables. Thus, each of the expansion levels (of the underlying channel) corresponds to a binary symmetric channel (BSC), and the coding problem is reduced to coding over these parallel channels while satisfying the channel input constraint. This optimization formulation is stated as the achievable rate result, for which a specific choice of input distribution is shown to achieve a rate which is arbitrarily close to the channel capacity in the high SNR regime. Remarkably, the scheme allows for low-complexity capacity-achieving codes for AEN channels, using the codes that are originally designed for BSCs. Extensions to different channel models and applications to other coding problems are discussed.

This paper studies the design of codes for distributed storage systems (DSS) that enable local repair in the event of node failure. This paper presents locally repairable codes based on low degree multivariate polynomials. Its code construction mechanism extends work on Noisy Interpolating Set by Dvir et al. [1]. The paper presents two classes of codes that allow node repair to be performed by contacting 2 and 3 surviving nodes respectively. It further shows that both classes are good in terms of their rate and minimum distance, and allow their rate to be bartered for greater flexibility in the repair process.

As its name suggests, "interference alignment" is a class of transmission schemes that aligns multiple sources of interference to minimize its impact, thus aiming to maximize rate in an interference network. To our knowledge, this paper presents the first real-time implementation of interference alignment. Other implementation in the literature are either done offline or assume a backchannel between participating nodes to perform alignment. On the other hand, this paper presents a blind interference alignment scheme, one that does not require channel state information at the transmitters or the knowledge of other transmitters data or the knowledge of data between receivers and functions in real-time.

An abstraction of the physical-layer coding using bit pipes that are coupled through data-rates is insufficient to capture notions such as node cooperation in cooperative relay networks. Consequently, network-stability analyses based on such abstractions are valid for non-cooperative schemes alone and meaningless for cooperative schemes. Motivated from this, this paper develops a framework that brings the information-theoretic coding scheme together with network-stability analysis. This framework does not constrain the system to any particular achievable scheme, i.e., the relays can use any cooperative coding strategy of its choice such as amplify/compress/quantize or any alter-and-forward scheme. The paper focuses on the scenario when coherence duration is of the same order of the packet/codeword duration, the channel distribution is unknown and the fading state is only known causally. The main contributions of this paper are two-fold: first, it develops a low-complexity queue-architecture to enable stable operation of cooperative relay networks, and, second, it establishes the throughput optimality of a simple network algorithm that utilizes this queue-architecture.

We develop distributed algorithms for efficient spectrum access strategies in cognitive radio relay networks. In our setup, primary users permit secondary users access to the resource (spectrum) as long as they consent to aiding the primary users as relays in addition to transmitting their own data. Given a pool of primary and secondary users, we desire to optimize overall network utility by determining the best configuration/pairing of secondary users with primary users. This optimization can be stated in a form similar to the maximum weighted matching problem. Given such formulation, we develop an algorithm based on affinity propagation technique that is completely distributed in its structure. We demonstrate the convergence of the developed algorithm and show that it performs close to the optimal centralized scheme.

This paper considers the problem of interference channel (IFC) with overlay cognitive radio setting. Both achievable rate and outer bounds for an overlay cognitive radio channel are developed, where the cognitive transmitter has partial knowledge of the legitimate transmitter's message. Specifically, an IFC setting is considered where one transmitter (the “cognitive” one) knows the message of the other (“legitimate” transmitter) partially. An outer bound on the capacity region of this channel is found for the “weak” interference case (where the “interference” caused by the cognitive transmitter to the legitimate receiver is weaker than the “signal” from the cognitive transmitter to the cognitive receiver). This outer bound is developed for the discrete-memoryless case and evaluated for a Gaussian channel setting. An achievable region is subsequently determined for a partially cognitive radio channel, and the outer bound on the capacity region is compared with the achievable rate in a Gaussian channel. Subsequently, an achievable region that incorporates elements of the Han-Kobayashi coding strategy with dirty paper coding is developed for this channel.

We study the effect of the absence of channel knowledge at the transmitters for multiple-input-multiple-output (MIMO) networks. Specifically, we assume perfect channel state information at the receivers, no channel state information at the transmitter(s), and independent identically distributed (i.i.d.) Rayleigh fading across antennas, users and time slots. We provide the characterization of the degrees of freedom (DoF) region for a 2-user MIMO broadcast channel. We then provide a DoF region outer bound for a 2-user MIMO interference channel. This bound is shown to be tight for all possible combinations of the number of antennas at each node except for one case. To analyze the unsolved case, we point out the potential of interference alignment in the 2-user MIMO interference channel with no channel state information at the transmitters. As a byproduct, we explore a special class of MIMO broadcast channels where the capacity region is established by using the outer bound developed in the DoF analysis.

The aim of this paper is to study the achievable rates for a K-user Gaussian interference channel (G-IFC) for any signal-to-noise ratio using a combination of lattice and algebraic codes. Lattice codes are first used to transform the G-IFC into a discrete input--output noiseless channel, and subsequently algebraic codes are developed to achieve good rates over this new alphabet. In this context, a quantity called efficiency is introduced which reflects the effectiveness of the algebraic coding strategy. This paper first addresses the problem of finding high-efficiency algebraic codes. A combination of these codes with Construction-A lattices is then used to achieve nontrivial rates for the original G-IFC.

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

This paper considers the problem of transmitting linear functions of two correlated Gaussian sources over a two-user additive Gaussian noise multiple access channel. The goal is to recover this linear function within an average mean squared error distortion criterion. Each transmitter has access to only one of the two Gaussian sources and is limited by an average power constraint. In this paper, a lattice coding scheme and two lower bounds on the achievable distortion are presented. The lattice scheme achieves within a constant of a distortion lower bound if the signal-to-noise ratio is greater than a threshold. Furthermore, for the difference of correlated Gaussian sources, uncoded transmission is shown to be worse in performance to lattice coding methods for correlation coefficients above a threshold.

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

This paper determines mechanisms to mitigate errors when implementing Boolean functions in nano-circuits. Nano-fabrics are expected to have high defect rates as atomic variations directly impact such materials. This paper develops a coding mechanism that uses a combination of cheap, but unreliable nano-device as the main function and reliable, but expensive CMOS devices to implement the coding mechanism. The unique feature of this paper is that it exploits the don't-cares that naturally occur in Boolean functions to construct better codes. The reliable Boolean function problem is cast as a constraint satisfaction problem and then solved using a tree-based dynamic programming algorithm. (Here, the word “dynamic programming” is used in the same sense as computer-science literature, i.e., and as an efficient search algorithm over trees.)

In traditional wireless protocols, medium-access-control and physical-layer rate-allocation are performed separately. This paper makes the case for combining the two into a single cross-layer framework. It presents the design, implementation, and evaluation of queue-based channel-measurement and rate-allocation (Q-CMRA) that is based on this single cross-layer framework. Q-CMRA's distributed algorithms utilize both queue-state and channel-state to jointly control medium-access and rate-allocation. Such joint control is essential to improving spatial-reuse and total network throughput. In our experiments, Q-CMRA outperforms traditional CSMA-CA and doubles the total network throughput in some setups.

This paper applies affinity propagation (AP) to develop distributed solutions for routing over networks. AP is a message passing algorithm for unsupervised learning. This paper demonstrates that AP can be generalized and applied to a wide class of problems in networking. In particular, AP can be used to develop distributed routing mechanisms for networks. Simulation results demonstrate that the proposed schemes compare favorably with the existing methods.

This paper considers a class of overlay cognitive radios with three messages, referred to as overlay cognitive MAC radios. The system consists of two transmitters and receivers but three independent messages, two of which are to be decoded at one receiver while the third is destined for the other receiver. An achievable region and an outer bound for the “weak” and “strong” interference cases are presented for this channel, which are ultimately shown to match for the special class of “weak” Gaussian overlay cognitive MAC radios.

This paper presents outerbounds for the two-user Gaussian fading broadcast channel. These outerbounds are based on Costa's entropy power inequality (Costa-EPI) and are formulated mathematically as a feasibility problem. For classes of the two-user Gaussian fading broadcast channel where the outerbound is found to have a feasible solution, we find conditions under which a suitable inner and outer bound meet. For all such cases, this paper provides a partial characterization of the capacity region of the Gaussian two-user fading broadcast channel.

This paper determines mechanisms for distributed storage that are simultaneously repair and update efficient. Repair efficiency demands that minimum information be downloaded from surviving nodes to reconstruct failed storage nodes. Update efficiency desires that changes in the original data require minimal updates at the storage nodes. These two requirements can be seen as counteracting one another, as the latter imposes a sparsity constraint on the encoding process that is not desirable for the former. In this paper we establish the existence of the codes that meet both requirements: require only logarithmic updates when data changes, while simultaneously minimizing repair bandwidth for exact reconstruction. To show this, we use a combination of KG codes for update efficiency with interference-alignment strategies for distributed storage.

This paper studies a multi -terminal source coding problem, where two terminals possess two (correlated) Gaussian sources to be compressed and delivered to the destination through an intermediate relay. Unlike the CEO and conventional two terminal source coding problems as well as point-to-point relay source coding problem, lattices are found to play an important role in achieving "good" rates for this problem setting. Two achievable strategies compute-and-forward and compress-and forward are used to develop achievable rates for this problem setting. For the symmetric case, the inner and outer bounds developed are shown to be within 1/2 bits of each other.

This paper uses the compressive sensing framework to establish secure physical layer communication over a Wyner wiretap channel. The idea, at its core, is simple - the paper shows that compressive sensing can exploit channel asymmetry so that a message, encoded as a sparse vector, is decodable with high probability at the legitimate receiver while it is impossible to decode it with high probability at the eavesdropper.

Mobile cyberphysical systems have received considerable attention over the last decade, as communication, computing and control come together on a common platform. Understanding the complex interactions that govern the behavior of large complex cyberphysical systems is not an easy task. The goal of this paper is to address this challenge in the particular context of multimedia delivery over an autonomous aerial vehicle (AAV) network. Bandwidth requirements and stringent delay constraints of real-time video streaming, paired with limitations on computational complexity and power consumptions imposed by the underlying implementation platform, make cross-layer and cross-domain co-design approaches a necessity. In this paper, we propose a novel, low-complexity rate-distortion optimized (RDO) protocol specifically targeted at video streaming over mobile embedded networks. We test the performance of our RDO algorithm on simulation models developed for aerial mobility of multiple wirelessly communicating AAVs. Results show that our optimized streaming leads to 47% and 39% less video distortion with very little computational overhead compared to regular ACKed and non-ACKed transmission, respectively.

This paper develops a distributed algorithm for rate allocation in wireless networks that achieves the same throughput region as optimal centralized algorithms. This cross-layer algorithm jointly performs medium access control and physical-layer rate adaptation. The paper establishes that this algorithm is throughput-optimal for general rate regions. In contrast to on-off scheduling, rate allocation enables optimal utilization of physical-layer schemes by scheduling multiple rate levels. The algorithm is based on local queue-length information, and thus the algorithm is of significant practical value. An important application of this algorithm is in multiple-band multiple-radio throughput-optimal distributed scheduling for white-space networks. The algorithm requires that each link can determine the global feasibility of increasing its current data-rate. In many classes of networks, any one link's data-rate primarily impacts its neighbors and this impact decays with distance. Hence, local exchanges can provide the information needed to determine feasibility. Along these lines, the paper discusses the potential use of existing physical-layer control messages to determine feasibility. This can be considered as a technique analogous to carrier sensing in carrier sense multiple access (CSMA) networks.

This paper considers a multi-cell multiple antenna system with precoding used at the base stations for downlink transmission. Channel state information (CSI) is essential for precoding at the base stations. An effective technique for obtaining this CSI is time-division duplex (TDD) operation where uplink training in conjunction with reciprocity simultaneously provides the base stations with downlink as well as uplink channel estimates. This paper mathematically characterizes the impact that uplink training has on the performance of such multi-cell multiple antenna systems. When non-orthogonal training sequences are used for uplink training, the paper shows that the precoding matrix used by the base station in one cell becomes corrupted by the channel between that base station and the users in other cells in an undesirable manner. This paper analyzes this fundamental problem of pilot contamination in multi-cell systems. Furthermore, it develops a new multi-cell MMSE-based precoding method that mitigates this problem. In addition to being linear, this precoding method has a simple closed-form expression that results from an intuitive optimization. Numerical results show significant performance gains compared to certain popular single-cell precoding methods.

This paper studies dirty-paper coding in a Gaussian broadcast channel with two receivers. It finds that an approximate version of dirty-paper coding using low-density lattices can be implemented with a complexity that is polynomial-time on average in the block length. The main difference between this paper and prior work is that a non-binary LDPC-based lattice codebook is used for each user, and one codebook is aligned with the other. The low-density nature enables tractable encoding and decoding algorithms, and the alignment gives structure to the overall signal transmitted and it enables us to perform the encoding and decoding efficiently.1

A new class of message-passing algorithms for motif finding is presented. Motif finding is the problem of identifying a collection of common subsequences within a given set of DNA sequences. It can be cast as an integer linear program (ILP). Message-passing techniques are a computationally efficient alternative to the often infeasible combinatorial solutions to the ILP. We introduce a new graphical representation of the ILP formulation of the problem, and use it to develop new message-passing algorithms for motif finding. Simulation results demonstrate that the new algorithms have better performance and convergence properties than the previously proposed solutions.

Analogous to the beneficial impact that mobility has on the throughput of unicast networks, this paper establishes that mobility can provide a similar gain in the order-wise growth-rate of the throughput for multicast networks. This paper considers an all-mobile multicast network, and characterizes its multicast capacity scaling. The scaling result shows that the growth-rate of the throughput in the all-mobile multicast network is order-wise higher compared to the all-static multicast network. Further, the paper considers a static-mobile hybrid multicast network, and establishes that, if there are sufficient number of mobile nodes (that is order-wise smaller than the total number of nodes) in the network, then mobile nodes can enhance the order behavior of the multicast throughput.

This paper presents the concept of incremental traceback for determining changes in the trace of a network as it evolves with time. A distributed algorithm, based on the methodology of algebraic traceback developed by Dean et al., is proposed that can determine a path of d nodes using O(d) marked packets, and subsequently determine the changes in it using O(log d) marked packets. The algorithm is established to be order-wise optimal, i.e. no other distributed algorithm can determine changes in the path topology using lesser order of bits (or marked packets). The algorithm is shown to have a computational complexity of O(d log d), which is significantly less than that of any existing non-incremental algorithm for algebraic traceback. The extension of the traceback mechanism to systems deploying network coding is also considered.

This paper considers the problem of network coding for multiple unicast connections in networks represented by directed acyclic graphs. The concept of interference alignment, traditionally used in interference networks, is extended to analyze the performance of linear network coding in this setup and to provide a systematic code design approach. It is shown that, for a broad class of three-source three-destination unicast networks, a rate corresponding to half the individual source-destination min-cut is achievable via alignment strategies.

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

This paper studies the low-rank matrix completion problem from an information theoretic perspective. The completion problem is rephrased as a communication problem of an (uncoded) low-rank matrix source over an erasure channel. The paper then uses achievability and converse arguments to present order-wise optimal bounds for the completion problem.

This paper extends the literature on interference alignment to more certain classes of deterministic channels which incorporate non-linear input-output relationships. It is found that the concept of alignment extends naturally to these deterministic interference channels, and in many cases, the achieved degrees of freedom (DoF) can be shown to be optimal. A key contribution of the paper is the connection it builds between interference alignment and number theory.

This paper studies a family of genie-MAC (multiple access channel) outer bounds for K-user Gaussian interference channels. This family is inspired by existing genie-aided bounding mechanisms, but differs from current approaches in its optimization problem formulation and application. The fundamental idea behind these bounds is to create a group of genie receivers that form multiple access channels that can decode a subset of the original interference channel's messages. The MAC sum capacity of each of the genie receivers provides an outer bound on the sum of rates for this subset. The genie-MAC outer bounds are used to derive new sum-capacity results. In particular, this paper derives sum-capacity in closed-form for the class of K-user Gaussian degraded interference channels. The sum-capacity achieving scheme is shown to be a successive interference cancellation scheme. This result generalizes a known result for two-user channels to K-user channels.

We characterize the generalized degrees of freedom of the K user symmetric Gaussian interference channel where all desired links have the same signal-to-noise ratio (SNR) and all undesired links carrying interference have the same interference-to-noise ratio, INR = SNRα. We find that the number of generalized degrees of freedom per user, d(α), does not depend on the number of users, so that the characterization is identical to the 2 user interference channel with the exception of a singularity at α = 1 where d(1) = 1/K. The achievable schemes use multilevel coding with a nested lattice structure that opens the possibility that the sum of interfering signals can be decoded at a receiver even though the messages carried by the interfering signals are not decodable.

This paper considers the problem of transmitting the difference of two positively correlated Gaussian sources over a two-user additive Gaussian noise multiple access channel (MAC). The goal is to recover this difference within an average mean squared error distortion criterion. Each transmitter has access to only one of the two Gaussian sources and is limited by an average power constraint. In this work, a lattice coding scheme that achieves a distortion within a constant of a distortion lower bound is presented if the signal to noise ratio (SNR) is greater than a threshold. Further, uncoded transmission is shown to be worse in performance to lattice coding methods for correlation coefficients above a threshold. An alternative lattice coding scheme is also presented that can potentially improve on the performance of uncoded transmission.

This paper shows that structured transmission schemes are a good choice for secret communication over interference networks with an eavesdropper. Structured transmission is shown to exploit channel asymmetries and thus perform better than randomly generated codebooks for such channels. For a class of interference channels, we show that an equivocation sum-rate that is within two bits of the maximum possible legitimate communication sum-rate is achievable using lattice codes.

We characterize the capacity region of a class of the deterministic Z channels. We show that, interestingly, Han-Kobayashi type rate-splitting is not required in the optimal achievable scheme for the class of channels considered.

This paper considers the problem of cognitive radios with partial message information. Here, an interference channel setting is considered where one transmitter (the ldquocognitiverdquo one) knows the message of the other (ldquolegitimaterdquo user) partially. An outer bound on the capacity region of this channel is found for the ldquoweakrdquo interference case (where the interference from the cognitive transmitter to the legitimate receiver is weak). This outer bound is shown for both the discrete-memoryless and the Gaussian channel cases. An achievable region is subsequently determined for a Gaussian partially cognitive-radio channel. The achievable strategy described in this paper is a combination of superposition and dirty paper coding.

This paper considers a multi-cell multiple antenna system with precoding at the base stations for downlink transmission. To enable precoding, channel state information (CSI) is obtained via uplink training. This paper mathematically characterizes the impact that uplink training has on the performance of multi-cell multiple antenna systems. When non-orthogonal training sequences are used for uplink training, it is shown that the precoding matrix used by the base station in one cell becomes corrupted by the channel between that base station and the users in other cells. This problem of pilot contamination is analyzed in this paper. A multi-cell MMSE-based precoding is proposed that, when combined with frequency/time/pilot reuse techniques, mitigate this problem.

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

This paper considers a degraded Gaussian broadcast channel over which Gaussian sources are to be communicated. When the sources are independent, this paper shows that hybrid coding achieves the optimal distortion region, the same as that of separate source and channel coding. It also shows that uncoded transmission is not optimal for this setting. For correlated sources, the paper shows that a hybrid coding strategy has a better distortion region than separate source-channel coding below a certain signal to noise ratio threshold. Thus, hybrid coding is a good choice for Gaussian broadcast channels with correlated Gaussian sources.

This paper studies the K > 2 user cognitive radio network. In this paper, there are one licensed transmit-receive pair and K - 1 cognitive transmit-receive pairs wishing to communicate simultaneously. For the case of a class of ¿very strong¿ interference channels, this paper shows that all users can simultaneously communicate as if all cross-channels in the interference network were absent.

An analytically tractable model for Gaussian multiuser channels with fading is studied, and the capacity region of this model is found to be a good approximation of the capacity region of the original Gaussian network. This work extends the existing body of work on deterministic models for Gaussian multiuser channels to include the physical phenomenon of fading. In particular, it generalizes these results to a unicast, multiple node network setting with fading.

In this paper, we investigate upper and lower bounds on the capacity of two-user fading broadcast channels where one of the users has a constant (non-fading) channel. We use the Costa entropy power inequality (EPI) along with an optimization framework to derive upper bounds on the sum-capacity and superposition coding to obtain lower bounds on the sum-rate for this channel. For this fading broadcast channel where one channel is constant, we find that the upper and lower bounds meet under special cases, and in general, we show that the achievable sum-rate comes within a constant of the outer bound.

This paper studies a symmetricKuser Gaussian interference channel withKtransmitters andKreceivers. A "very strong" interference regime is derived for this channel setup. A "very strong" interference regime is one where the capacity region of the interference channel is the same as the capacity region of the channel with no interference. In this regime, the interference can be perfectly canceled by all the receivers without incurring any rate penalties. A "very strong" interference condition for an example symmetricKuser deterministic interference channel is also presented.

The downlink transmission in multi-user multiple- input multiple-output (MIMO) systems has been extensively studied from both communication-theoretic and information-theoretic perspectives. Most of these papers assume perfect/imperfect channel knowledge. In general, the problem of channel estimation is studied separately. However, in interference-limited communication systems with high mobility, the problem of channel estimation is tightly coupled with the problem of maximizing throughput of the system. In this paper, scheduling and preconditioning in the presence of reciprocal time-division duplex (TDD) training are considered. In the case of homogeneous users, a scheduling scheme is proposed and an improved lower bound on the sum capacity is derived. The problem of choosing training sequence length to maximize net throughput of the system is also studied. In the case of heterogeneous users, a modified pre-conditioning method is proposed and an optimized pre-conditioning matrix is derived. This method is combined with a scheduling scheme to further improve achievable weighted-sum rate.

In this paper, the sum capacity of the Gaussian multiple input multiple output (MIMO) cognitive radio channel (MCC) is expressed as a convex problem with finite number of linear constraints, allowing for polynomial time interior point techniques to find the solution. In addition, a specialized class of sum power iterative waterfilling algorithms is determined that exploits the inherent structure of the sum capacity problem. These algorithms not only determine the maximizing sum capacity value, but also the transmit policies that achieve this optimum. The paper concludes by providing numerical results which demonstrate that the algorithm takes very few iterations to converge to the optimum.

This paper studies the lossy, wireless packet network of [1], in the case of a multicast requirement and the availability of feedback. In the unicast case, feedback is sufficient to allow a strategy which achieves the throughput-optimal cut-set capacity without requiring network coding [3]. We provide a counter-example to show that source coding and feedback, without network coding, is insufficient to achieve the cut-set capacity for the multicast wireless erasure network. In particular, we examine a network with one source, one relay, and two destinations. We show that even with the highly optimistic assumption of feedback which provides global packet state awareness, this network still fails to reach capacity. This bridges the gap between two previously known results; one, that network coding can achieve the capacity of the wireless erasure network, and two, that feedback allows a capacity achieving scheme which does not require network coding in the unicast wireless erasure network.

The compound wiretap channel provides a general framework for studying secrecy communication under channel uncertainty. Characterizing the secrecy capacity of nondegraded compound wiretap channels is a challenging problem in information theory. This paper considers the class of parallel Gaussian compound wiretap channels with only one possible channel realization for the legitimate receiver and characterizes the secrecy capacity. (Such parallel Gaussian compound wiretap channels are generally nondegraded.) Moreover, it is shown that the proposed coding scheme strictly outperforms the best known single-letter scheme with Gaussian codebooks.

This paper studies the secrecy capacity of unicast communication in a wireless erasure network setting in the presence of a wire-tapper. From an information-theoretic setting of perfect secrecy, both upper bounds and achievable secrecy rates are presented. Secrecy capacity is determined in closed form for a class of broadcast constrained erasure networks.

This paper studies a two source, two destination Gaussian interference channel in the presence of a cognitive relay. The cognitive relay has access to the messages transmitted by both the sources and assists them in communicating the messages successfully to their respective destinations. An achievable rate region for the system is derived by combining the Han-Kobayashi coding scheme for the general interference channel with dirty paper coding. The paper also derives outer bounds on the capacity region and obtains the degrees of freedom of the system.

This paper studies the fundamental operational limits of a class of Gaussian multicast channels with an interference setting. In particular, the paper considers two base stations multicasting separate messages to distinct sets of users. In the presence of channel state information at the transmitters and at the respective receivers, the capacity region of the Gaussian multicast channel with interference is characterized to within one bit. At the crux of this result is an extension to the multicast channel with interference of the Han-Kobayashi or the Chong-Motani-Garg achievable region for the interference channel.

This paper considers the problem of selecting a set of relay nodes to assist a transmitting node in a two-hop wireless network. Throughput-maximizing relay subset selection is a difficult problem that depends on variables such as node locations and power constraints. It is proposed that all relays employ partial decode-and-forward operations to improve the tractability of the relay selection problem. This allows relay selection to be transformed into a simpler relay placement problem which motivates two proximity-based relay selection algorithms. These algorithms are compared with a greedy algorithm based on relay channel gains to the sink and an algorithm that randomly selects relays. The diversity gain achieved by employing multiple relay nodes is derived. The proposed proximity-based algorithms offer good performance in terms of the expected achieved rate.

This correspondence derives bounds on the jamming capacity of a slotted ALOHA system. A system with n legitimate users, each with a Bernoulli arrival process is considered. Packets are temporarily stored at the corresponding user queues, and a slotted ALOHA strategy is used for packet transmissions over the shared channel. The scenario considered is that of a pair ofillegitimateusers that jam legitimate transmissions in order to communicate over the slotted ALOHA channel. Jamming leads to binary signaling between the illegitimate users, with packet collisions due to legitimate users treated as (multiplicative) noise in this channel. Further, the queueing dynamics at the legitimate users stochastically couples the jamming strategy used by the illegitimate users and the channel evolution. By considering various independent and identically distributed (i.i.d.) jamming strategies, achievable jamming rates over the slotted ALOHA channel are derived. Further, an upper bound on the jamming capacity over the class of all ergodic jamming policies is derived. These bounds are shown to be tight in the limit where the offered system load approaches unity.

This paper develops a contention-based opportunistic feedback technique towards relay selection in a dense wireless network. This technique enables the forwarding of additional parity information from the selected relay to the destination. For a given network, the effects of varying key parameters such as the feedback probability are presented and discussed. A primary advantage of the proposed technique is that relay selection can be performed in a distributed way. Simulation results find its performance to closely match that of centralized schemes that utilize GPS information, unlike the proposed method. The proposed relay selection method is also found to achieve throughput gains over a point-to-point transmission strategy.

This paper studies cooperation between transmitters in a two-user Gaussian multiple access channel (MAC) with correlated sources in the wideband limit. The paper's findings can be intuitively stated as follows: if the two sources are sufficiently (highly) correlated, then full cooperation between the transmitters is possible in the wideband limit incurring an arbitrarily small bit error rate. The core idea behind this paper is to use pulse-position modulation and to allow signals from the two transmitters to coherently combine with one another. This result also emphasizes the difference between bit-error and block-error rates. Whereas cooperation is very difficult to establish when achieving arbitrarily small block error rates, it can be enabled when the objective is to achieve arbitrarily small bit error rates and the sources are highly correlated.

The transport capacity of a class of erasure networks with broadcast and interference constraints is studied in this paper. A memoryless network model is considered, with transmitted symbols constrained to belong to a finite field. Connections between nodes are modeled to be independent erasures, with the probability of the existence of a ";link"; between any two nodes decaying exponentially with increasing geographic distance between those two nodes. Each node obeys a broadcast requirement. In addition, each receiver obtains the finite-field sum of the unerased symbols sent along all the edges connecting to it (an interference condition). In this setting, the transport capacity is bounded above by a linear growth term in the number of nodes, for any network which obeys a minimum node separation constraint. Finally, we show that this linear growth is achievable in random networks by employing routing. The main thrust of this paper is its conclusion: Routing is order-optimal in a random broadcast erasure network. Thus, network coding can only provide a constant gain in performance in this network model.

This paper studies secrecy capacity in a semi-deterministic setting, in which the channel between legitimate users (called Alice and Bob) is deterministic, while that between Alice and the eavesdropper (called Eve) is a discrete memoryless channel. Such a model is particularly relevant when a pre-existing error correcting code tailored to the legitimate channel is in use on top of which secret information is to be shared. First, a point-to-point setting is considered with a single wiretapper, a situation in which the secrecy capacity has an elegant characterization. Next, a generalized multiple access setting with confidential messages is considered in which each user wishes to communicate secret information to a common destination without the other determining its message. In this latter situation, outer bounds on the secrecy capacity are obtained.

This paper studies the use of layered coding in fading multiple-input single-output (MISO) and multiple access channels (MAC). In this setting, the transmitter(s) have no knowledge of the channel state while the receiver has accurate knowledge of it. The channel is assumed to be slowly fading in amplitude with a rapid change in phase. This is used to model a system with low mobility where the surrounding scattering environment is rich and changing quickly. In this setting, codebooks with rates greater than that supported by the channel undergo an outage. Our goal is to layer multiple codebooks at different rates such that the overall average throughput of the channel is maximized. The inherent difficulty in studying such channels is in determining an absolute decoding order at the receiver. In this paper, we focus on a class of strategies based on channel norm that has a natural decoding ordering. We use existing results for single antenna systems to obtain a "good" resource allocation policy for these channels.

In this paper, the feasibility of multiple-input multiple-output (MIMO) systems in aircraft is examined for the specific application of seatback entertainment, using an approach built around a site-specific capacity analysis methodology. The average capacity is evaluated as a function of the seat location, using the proposed methodology that relies on inputs from measurement results or ray-tracing simulations. The extension of the methodology to optimize the access point and client antenna placement locations and array configurations is also described in the paper. While the specific results are for the deployment of MIMO communication in aircraft for seatback entertainment, the same methodology can be applied to other deployment scenarios as well.

It has been shown that a decentralized relay selection protocol based on opportunistic feedback from the relays yields good throughput performance in dense wireless networks. This selection strategy supports a hybrid-ARQ transmission approach where relays forward parity information to the destination in the event of a decoding error. Such an approach, however, suffers a loss compared to centralized strategies that select relays with the best channel gain to the destination. This paper closes the performance gap by adding another level of channel feedback to the decentralized relay selection problem. It is demonstrated that only one additional bit of feedback is necessary for good throughput performance. The performance impact of varying key parameters such as the number of relays and the channel feedback threshold is discussed. An accompanying bit error rate analysis demonstrates the importance of relay selection

In this paper, the multiple access channel (MAC) with channel state is analyzed in a scenario where a) the channel state is known non-causally to the transmitters and b) there is perfect causal feedback from the receiver to the transmitters. An achievable region and an outer bound are found for a discrete memoryless MAC that extend existing results, bringing together ideas from the two separate domains of MAC with state and MAC with feedback. Although this achievable region does not match the outer bound in general, non-trivial conditions are found where they meet. In the case of Gaussian MAC, a specialized achievable region is found by using a combination of dirty paper coding and a generalization of the Schalkwijk-Kailath (1966), Ozarow (1984) and Merhav-Weissman (2005) schemes, and this region is found to be capacity achieving. Specifically, it is shown that additive Gaussian interference that is known non-causally to the transmitter causes no loss in capacity for the Gaussian MAC with feedback

Relay channels plays a central role in next-generation multihop wireless systems. This paper considers the MIMO relay channel where multiple antennas are employed by each terminal. New lower bounds on the capacity of a Gaussian MIMO relay channel are derived under the assumption that the transmitter employs either superposition coding or dirty-paper coding. The proposed lower bounds improve on a previously proposed lower bound that arises from a simple transmit strategy.

In this correspondence, we consider the problem of maximizing sum rate of a multiple-antenna Gaussian broadcast channel (BC). It was recently found that dirty-paper coding is capacity achieving for this channel. In order to achieve capacity, the optimal transmission policy (i.e., the optimal transmit covariance structure) given the channel conditions and power constraint must be found. However, obtaining the optimal transmission policy when employing dirty-paper coding is a computationally complex nonconvex problem. We use duality to transform this problem into a well-structured convex multiple-access channel (MAC) problem. We exploit the structure of this problem and derive simple and fast iterative algorithms that provide the optimum transmission policies for the MAC, which can easily be mapped to the optimal BC policies.

This work formulates a procedure of obtaining Lagrangian dual problems to a class of rate-distortion problems. The technique used here is analogous to the techniques used to address channel capacity problems in Vishwanath et al. (2003). The dual problem now obtained is a maximization problem and its solution in general a lower bound to the rate-distortion problem. This dual problem provides us with simple lower bounds to the rate achievable under distortion constraints, and with algorithms to compute this rate. We combine this dual problem with that obtained for channel capacity in Vishwanath et al. to obtain upper and lower bounds to worst-case channel capacity and worst-case rate under distortion constraints problems.

The capacity of a vector Gaussian interference channel is investigated. Outer bounds, and where possible, capacity regions of a class of interference channels is characterized. The analysis of single transmit multiple receive antenna (SIMO) Gaussian interference channels with strong interference can be easily seen to be exactly analogous to that of a single transmit single receive antenna system. This paper demonstrates that, in contrast, multiple transmit single receive antenna (MISO) Gaussian interference channels are much harder to characterize. In this paper, the capacity region for a class of MISO interference channels with very strong interference is characterized. Also, the rank of the optimal transmit policy in a MISO Gaussian interference channel is shown to be bounded by the number of users in the system. Finally, outer bounds on the capacity region of the general multiple transmit and receive antenna (MIMO) Gaussian interference channels are derived. A new outer bound is obtained, which combines and improves previously known strategies for bounding the capacity of interference channels.

We define a duality between Gaussian multiple-access channels (MACs) and Gaussian broadcast channels (BCs). The dual channels we consider have the same channel gains and the same noise power at all receivers. We show that the capacity region of the BC (both constant and fading) can be written in terms of the capacity region of the dual MAC, and vice versa. We can use this result to find the capacity region of the MAC if the capacity region of only the BC is known, and vice versa. For fading channels we show duality under ergodic capacity, but duality also holds for different capacity definitions for fading channels such as outage capacity and minimum-rate capacity. Using duality, many results known for only one of the two channels can be extended to the dual channel as well.

A two transmitter two receiver channel where independent data is sent on each communication link of the system is considered. We consider a three-link system, termed the "Z" channel, in which one transmitter is connected to both receivers while the other transmitter is only connected to one of the receivers. Thus, the "Z" channel has a three dimensional capacity region. We characterize the capacity region of a special class of degraded "Z" channels and establish an achievable region for the Gaussian "Z" channels. Finally, we use genie-aided techniques previously used for the interference and broadcast channels to obtain an outer bound for general "Z" channels.

We provide an overview of the extensive results on the Shannon capacity of single-user and multiuser multiple-input multiple-output (MIMO) channels. Although enormous capacity gains have been predicted for such channels, these predictions are based on somewhat unrealistic assumptions about the underlying time-varying channel model and how well it can be tracked at the receiver, as well as at the transmitter. More realistic assumptions can dramatically impact the potential capacity gains of MIMO techniques. For time-varying MIMO channels there are multiple Shannon theoretic capacity definitions and, for each definition, different correlation models and channel information assumptions that we consider. We first provide a comprehensive summary of ergodic and capacity versus outage results for single-user MIMO channels. These results indicate that the capacity gain obtained from multiple antennas heavily depends on the available channel information at either the receiver or transmitter, the channel signal-to-noise ratio, and the correlation between the channel gains on each antenna element. We then focus attention on the capacity region of the multiple-access channels (MACs) and the largest known achievable rate region for the broadcast channel. In contrast to single-user MIMO channels, capacity results for these multiuser MIMO channels are quite difficult to obtain, even for constant channels. We summarize results for the MIMO broadcast and MAC for channels that are either constant or fading with perfect instantaneous knowledge of the antenna gains at both transmitter(s) and receiver(s). We show that the capacity region of the MIMO multiple access and the largest known achievable rate region (called the dirty-paper region) for the MIMO broadcast channel are intimately related via a duality transformation. This transformation facilitates finding the transmission strategies that achieve a point on the boundary of the MIMO MAC capacity region in terms of the transmission strategies of the MIMO broadcast dirty-paper region and vice-versa. Finally, we discuss capacity results for multicell MIMO channels with base station cooperation. The base stations then act as a spatially diverse antenna array and transmission strategies that exploit this structure exhibit significant capacity gains. This section also provides a brief discussion of system level issues associated with MIMO cellular. Open problems in this field abound and are discussed throughout the paper.

We consider a turbo-coded system employed on a flat-fading channel where the transmitter and receiver adapt the encoder, decoder, modulation scheme, and transmit power to the state of the channel. Assuming instantaneous and error-free channel gain and phase knowledge at the transmitter and the receiver, we determine the optimal adaptation strategy that maximizes the throughput of this system, while achieving a given bit-error rate under an average power constraint. Our optimized adaptive modulation strategy is based on an extensive set of existing turbo-coded modulation schemes. We find that adapting both the turbo encoder (rate) and the transmit power can achieve performance within 3 dB of the fading channel capacity.

We consider a multiuser multiple-input multiple- output (MIMO) Gaussian broadcast channel (BC), where the transmitter and receivers have multiple antennas. Since the MIMO BC is in general a nondegraded BC, its capacity region remains an unsolved problem. We establish a duality between what is termed the "dirty paper" achievable region (the Caire-Shamai (see Proc. IEEE Int. Symp. Information Theory, Washington, DC, June 2001, p.322) achievable region) for the MIMO BC and the capacity region of the MIMO multiple-access channel (MAC), which is easy to compute. Using this duality, we greatly reduce the computational complexity required for obtaining the dirty paper achievable region for the MIMO BC. We also show that the dirty paper achievable region achieves the sum-rate capacity of the MIMO BC by establishing that the maximum sum rate of this region equals an upper bound on the sum rate of the MIMO BC.

We consider a multiuser multiple input multiple output (MIMO) Gaussian broadcast channel (BC), where the transmitter and receivers have multiple antennas. Since the MIMO broadcast channel is in general a non-degraded broadcast channel, its capacity region remains an unsolved problem. We establish a duality between what is termed the "dirty paper" achievable region (the Caire-Shamai achievable region) for the MIMO broadcast channel and the capacity region of the MIMO multiple-access channel (MAC), which is easy to compute. Using this duality, we greatly reduce the computational complexity required for obtaining the dirty paper achievable region for the MIMO BC. The duality also enables us to translate previously known results for the MIMO MAC to the MIMO BC. We also show that the dirty paper achievable region achieves the sum-rate capacity of the MIMO BC by establishing that the maximum sum rate of this region equals an upper-bound on the sum rate of the MIMO BC.

We motivate the need for a complexity based design for performing joint iterative equalization and decoding. This joint iterative process, which requires the exchange of soft information, incurs a huge complexity increase over hard-decision based algorithms. We introduce complexity as a design parameter and provide two different methodologies. The first approach is a combination of SOVA (soft output Viterbi algorithm) and DFSE (decision feedback sequence estimation), and is called soft-output DFSE (SO-DFSE). The second approach, called soft-decision DFSE (SD-DFSE) generalizes the notion of reliability to soft-decisions through the use of appropriately chosen functions. By varying the design parameters in both approaches, the module can range from being as simple as a soft output DFE to being as complex as a SOVA or APP (a posteriori probability). We conclude by presenting performance curves of iterative algorithms that utilize these modules.

We provide an information theoretic perspective on the problem of throughput maximization in a block flat fading wireless data system with codeword lengths restricted to be less than the fade block duration. We assume no channel state information at the transmitter (CSIT) and perfect channel state information at the receiver (CSIR). We explore the tradeoffs between using a single codebook vs. multiple codebooks (rate-splitting) on single input single output (SISO) channels, and scalar coding vs. vector coding for diagonal multiple input multiple output (MIMO) channels. For all log-concave scalar channel fade distributions, we show that using multiple codebooks increases the average throughput of the system when the multiple codewords are transmitted simultaneously in time, frequency and space over the same channel. Splitting the channel orthogonally in time, frequency, or among the inputs of a MIMO system and then transmitting different codewords on each orthogonal sub-channel significantly reduces the achievable average throughput.

We obtain optimal resource allocation policies for a single user single-carrier system and a multiple-access multi-carrier-CDMA system when the transmitter adapts to the variations in the short-term mean (slow fade) in a combined slow and fast fading (composite fading) environment. For the single user system, we maximize the average throughput achieved by the user, while In the uplink MC-CDMA system, we maximize the sum of average rates of the users in the system. For each system, we find the optimal resource allocation policies for two scenarios. The first is when is system is designed for voice transmission, where the bit error rate (BER) of each user, averaged over the fast fade, is maintained at a desired value. The second is when the system is designed for data transmission, where the BER of each user is maintained below a desired value for a given percentage of time. We find that, for the single-user system, the solution for both the voice and data transmission cases is waterfilling, and that waterfilling is the asymptotically optimal solution to multi-user problems in both scenarios, i.e. is nearly optimal for a large number of users. We also find that, when dealing with a voice system, the solution is independent of the distributions of the slow and fast fades and similar to the solutions obtained for noncomposite fading environments (fast or slow fading).

We consider the capacity of a narrowband point to point communication system employing multiple-element antenna arrays at both the transmitter and the receiver with covariance feedback. Under covariance feedback the receiver is assumed to have perfect channel state information (CSI) while at the transmitter the channel matrix is modeled as consisting of zero mean complex jointly Gaussian random variables with known covariances. Specifically we assume a channel matrix with i.i.d. rows and correlated columns, a common model for downlink transmission. We determine the optimal transmit precoding strategy to maximize the Shannon capacity of such a system. We also derive closed form necessary and sufficient conditions on the spatial covariance for when the maximum capacity is achieved by beamforming. The conditions for optimality of beamforming agree with the notion of water-filling over multiple degrees of freedom.

This paper studies the decorrelation property of the constituent codes in space-time turbo codes (STTCs), where different constituent codes are transmitted over different antennas. We show that the time correlation between constituent codes falls of with respect to STTC block length N as 1//spl radic/N for large N, and hence goes to zero as N/spl rarr//spl infin/. We then use this result to obtain analytical expressions for the frame error rate (FER) of STTCs in flat fading. The decorrelation property of STTCs helps explain the exceptional performance of STTCs on slowly varying flat fading channels.