In many practical learning problems, training samples are not i.i.d., and there is an intrinsic dependency among samples. Therefore, theoretical study of learning with dependent data has recently gained attention. In this paper, we provide a uniform convergence bound for the class of Lipschitz functions with bounded values at zero, under the assumption that the data samples are scalar and have a possibly dependent joint Gaussian distribution. Since other than Lipschitzness, there is no heavy assumption such as convexity or boundedness on the function class, the results are applicable for many practical models including neural networks. We showcase the strength and applicability of our theorems by numerical simulation and real-data analysis.

We propose a novel framework for incorporating unlabeled data into semi-supervised classification problems, where scenarios involving the minimization of either i) adversarially robust or ii) non-robust loss functions have been considered. Notably, we allow the unlabeled samples to deviate slightly (in total variation sense) from the in-domain distribution. The core idea behind our framework is to combine Distributionally Robust Optimization (DRO) with self-supervised training. As a result, we also leverage efficient polynomial-time algorithms for the training stage. From a theoretical standpoint, we apply our framework on the classification problem of a mixture of two Gaussians in $\mathbb{R}^d$, where in addition to the $m$ independent and labeled samples from the true distribution, a set of $n$ (usually with $n\gg m$) out of domain and unlabeled samples are gievn as well. Using only the labeled data, it is known that the generalization error can be bounded by $\propto\left(d/m\right)^{1/2}$. However, using our method on both isotropic and non-isotropic Gaussian mixture models, one can derive a new set of analytically explicit and non-asymptotic bounds which show substantial improvement on the generalization error compared ERM. Our results underscore two significant insights: 1) out-of-domain samples, even when unlabeled, can be harnessed to narrow the generalization gap, provided that the true data distribution adheres to a form of the "cluster assumption", and 2) the semi-supervised learning paradigm can be regarded as a special case of our framework when there are no distributional shifts. We validate our claims through experiments conducted on a variety of synthetic and real-world datasets.

The aim of this paper is to address the challenge of gradual domain adaptation within a class of manifold-constrained data distributions. In particular, we consider a sequence of $T\ge2$ data distributions $P_1,\ldots,P_T$ undergoing a gradual shift, where each pair of consecutive measures $P_i,P_{i+1}$ are close to each other in Wasserstein distance. We have a supervised dataset of size $n$ sampled from $P_0$, while for the subsequent distributions in the sequence, only unlabeled i.i.d. samples are available. Moreover, we assume that all distributions exhibit a known favorable attribute, such as (but not limited to) having intra-class soft/hard margins. In this context, we propose a methodology rooted in Distributionally Robust Optimization (DRO) with an adaptive Wasserstein radius. We theoretically show that this method guarantees the classification error across all $P_i$s can be suitably bounded. Our bounds rely on a newly introduced {\it {compatibility}} measure, which fully characterizes the error propagation dynamics along the sequence. Specifically, for inadequately constrained distributions, the error can exponentially escalate as we progress through the gradual shifts. Conversely, for appropriately constrained distributions, the error can be demonstrated to be linear or even entirely eradicated. We have substantiated our theoretical findings through several experimental results.

In this paper, we propose sample complexity bounds for learning a simplex from noisy samples. A dataset of size $n$ is given which includes i.i.d. samples drawn from a uniform distribution over an unknown arbitrary simplex in $\mathbb{R}^K$, where samples are assumed to be corrupted by a multi-variate additive Gaussian noise of an arbitrary magnitude. We prove the existence of an algorithm that with high probability outputs a simplex having a $\ell_2$ distance of at most $\varepsilon$ from the true simplex (for any $\varepsilon>0$). Also, we theoretically show that in order to achieve this bound, it is sufficient to have $n\ge\tilde{\Omega}\left(K^2/\varepsilon^2\right)e^{\Omega\left(K/\mathrm{SNR}^2\right)}$ samples, where $\mathrm{SNR}$ stands for the signal-to-noise ratio and is defined as the ratio of the maximum component-wise standard deviation of the simplex (signal) to that of the noise vector. This result solves an important open problem in this area of research, and shows as long as $\mathrm{SNR}\ge\Omega\left(\sqrt{K}\right)$ the sample complexity of the noisy regime has the same order to that of the noiseless case. Our proofs are a combination of the so-called sample compression technique in (Ashtiani et al., 2018), mathematical tools from high-dimensional geometry, and Fourier analysis. In particular, we have proposed a general Fourier-based technique for recovery of a more general class of distribution families from additive Gaussian noise, which can be further used in a variety of other related problems.

We consider the$K$-user Multiple Input Multiple Output (MIMO) Gaussian interference channel with$M$antennas at each transmitter and$N$antennas at each receiver. It is assumed that channel coefficients are constant real numbers and are available at all transmitters and at all receivers. The main objective of this paper is to characterize the number of Degrees of Freedom (DoF) of this channel. Using the real interference alignment technique introduced in Motahariet al., 2014, we show that$\frac {MN}{M+N} K$degrees of freedom can be achieved for almost all channel realizations. Also, a new upper-bound on the DoF of this channel is provided. This upper-bound coincides with our achievable DoF for$K\geq K_{u} \triangleq \frac {M+N}{\gcd (M,N)}$, where$\gcd (M,N)$denotes the greatest common divisor of$M$and$N$. This gives an exact characterization of DoF for$M\times N$MIMO Gaussian interference channel in the case of$K\geq K_{u}$. Since there is no cooperation between transmit (or receive) antennas of each user in our transmission scheme, this result shows that the DoF benefit of joint processing in collocated antennas vanishes when the number of users is greater than a certain threshold.

The objective of a genome-wide association study (GWAS) is to associate subsequences of individuals’ genomes to the observable characteristics called phenotypes (e.g., high blood pressure). Motivated by the GWAS problem, in this paper we introduce the information-theoretic problem ofassociated subsequence retrieval, where a dataset of N (possibly high-dimensional) sequences of length G, and their corresponding observable (binary) characteristics is given. The sequences are chosen independently and uniformly at random from$\mathcal {X}^{\text {G}}$, where$\mathcal {X}$is a finite alphabet. The observable (binary) characteristic is only related to a specific unknown subsequence of length$L$of the sequences, calledassociated subsequence. For each sequence, if the associated subsequence of it belongs to a universal finite set, then it is more likely to display the observable characteristic (i.e., it is more likely that the observable characteristic is one). The goal is to retrieve the associated subsequence using a dataset of N sequences and their observable characteristics. We demonstrate that as the parameters N, G, and L grow, a threshold effect appears in the curve of probability of error versus the rate which is defined as${{\it\text { Gh}}(\text {L}/\text {G})}/{\text {N}}$, where$\text {h}(\cdot )$is the binary entropy function. This effect allows us to define the capacity of associated subsequence retrieval. We develop an achievable scheme and a matching converse for this problem, and thus characterize its capacity in two scenarios: the zero-error-rate and the$\epsilon $-error-rate.

It is of fundamental importance to find algorithms obtaining optimal performance for learning of statistical models in distributed and communication limited systems. Aiming at characterizing the optimal strategies, we consider learning of Gaussian Processes (GP) in distributed systems as a pivotal example. We first address a very basic problem: how many bits are required to estimate the inner-products of some Gaussian vectors across distributed machines? Using information theoretic bounds, we obtain an optimal solution for the problem which is based on vector quantization. Two suboptimal and more practical schemes are also presented as substitutes for the vector quantization scheme. In particular, it is shown that the performance of one of the practical schemes which is called per-symbol quantization is very close to the optimal one. Schemes provided for the inner-product calculations are incorporated into our proposed distributed learning methods for GPs. Experimental results show that with spending few bits per symbol in our communication scheme, our proposed methods outperform previous zero rate distributed GP learning schemes such as Bayesian Committee Model (BCM) and Product of experts (PoE).

A central machine is interested in estimating the underlying structure of a sparse Gaussian Graphical Model (GGM) from a dataset distributed across multiple local machines. The local machines can communicate with the central machine through a wireless multiple access channel. In this paper, we are interested in designing effective strategies where reliable learning is feasible under power and bandwidth limitations. Two approaches are proposed: Signs and Uncoded methods. In the Signs method, the local machines quantize their data into binary vectors and an optimal channel coding scheme is used to reliably send the vectors to the central machine where the structure is learned from the received data. In the Uncoded method, data symbols are scaled and transmitted through the channel. The central machine uses the received noisy symbols to recover the structure. Theoretical results show that both methods can recover the structure with high probability for a large enough sample size. Experimental results indicate the superiority of the Signs method over the Uncoded method under several circumstances.

Centralized coded caching and delivery is studied for a radio access combination network (RACN), whereby a set of H edge nodes (ENs), connected to a cloud server via orthogonal fronthaul links with limited capacity, serve a total of K user equipments (TIEs) over wireless links. The cloud server is assumed to hold a library of N files, each of size F bits; and each user, equipped with a cache of size μRN F bits, is connected to a distinct set of r ENs each of which equipped with a cache of size μTN F bits, where μT, μR∈ [0, 1] are the fractional cache capacities of the TIEs and the ENs, respectively. The objective is to minimize the normalized delivery time (NDT), which refers to the worst case delivery latency when each user requests a single distinct file from the library. Three coded caching and transmission schemes are considered, namely the MDSIA, soft-transfer and zero-forcing (ZF) schemes. MDS-IA utilizes maximum distance separable (MDS) codes in the placement phase and real interference alignment (IA) in the delivery phase. The achievable NDT for this scheme is presented for r = 2 and arbitrary fractional cache sizes μTand μR, and also for arbitrary value of r and fractional cache size μTwhen the cache capacity of the TIE is above a certain threshold. The soft-transfer scheme utilizes soft-transfer of coded symbols to ENs that implement ZF over the edge links. The achievable NDT for this scheme is presented for arbitrary r and arbitrary fractional cache sizes μTand μR. The last scheme utilizes ZF between the ENs and the TIEs without the participation of the cloud server in the delivery phase. The achievable NDT for this scheme is presented for an arbitrary value of r when the total cache size at a pair of TIE and EN is sufficient to store the whole library, i.e., μT+μR≥ 1. The results indicate that the fronthaul capacity determines which scheme achieves a better performance in terms of the NDT, and the soft-transfer scheme becomes favorable as the fronthaul capacity increases.

Current techniques in sequencing a genome allow a service provider (e.g. a sequencing company) to have full access to the genome information, and thus the privacy of individuals regarding their lifetime secret is violated. In this paper, we introduce the problem of private DNA sequencing, where the goal is to keep the DNA sequence private to the sequencer. We propose an architecture, where the task of reading fragments of DNA and the task of DNA assembly are separated, the former is done at the sequencer(s), and the later is completed at a local trusted data collector. To satisfy the privacy constraint at the sequencer and reconstruction condition at the data collector, we create an information gap between these two relying on two techniques: (i) we use more than one non-colluding sequencer, all reporting the read fragments to the single data collector, (ii) adding the fragments of some known DNA molecules, which are still unknown to the sequencers, to the pool. We prove that these two techniques provide enough freedom to satisfy both conditions at the same time.

BACKGROUND: Long reads provide valuable information regarding the sequence composition of genomes. Long reads are usually very noisy which renders their alignments on the reference genome a daunting task. It may take days to process datasets enough to sequence a human genome on a single node. Hence, it is of primary importance to have an aligner which can operate on distributed clusters of computers with high performance in accuracy and speed. RESULTS: In this paper, we presented IMOS, an aligner for mapping noisy long reads to the reference genome. It can be used on a single node as well as on distributed nodes. In its single-node mode, IMOS is an Improved version of Meta-aligner (IM) enhancing both its accuracy and speed. IM is up to 6x faster than the original Meta-aligner. It is also implemented to run IM and Minimap2 on Apache Spark for deploying on a cluster of nodes. Moreover, multi-node IMOS is faster than SparkBWA while executing both IM (1.5x) and Minimap2 (25x). CONCLUSION: In this paper, we purposed an architecture for mapping long reads to a reference. Due to its implementation, IMOS speed can increase almost linearly with respect to the number of nodes in a cluster. Also, it is a multi-platform application able to operate on Linux, Windows, and macOS.

Association mapping of genetic diseases has attracted extensive research interest during the recent years. However, most of the methodologies introduced so far suffer from spurious inference of the associated sites due to population inhomogeneities. In this paper, we introduce a statistical framework to compensate for this shortcoming by equipping the current methodologies with a state-of-the-art clustering algorithm being widely used in population genetics applications. The proposed framework jointly infers the disease-associated factors and the hidden population structures. In this regard, a Markov Chain-Monte Carlo (MCMC) procedure has been employed to assess the posterior probability distribution of the model parameters. We have implemented our proposed framework on a software package whose performance is extensively evaluated on a number of synthetic datasets, and compared to some of the well-known existing methods such as STRUCTURE. It has been shown that in extreme scenarios, up to $10-15$10-15 percent of improvement in the inference accuracy is achieved with a moderate increase in computational complexity.

In the problem of population stratification, each data instance is generated based on a finite mixture model with$K$mixture components and$L$observed variables. Each variable takes its value in a finite state space with cardinality M. The variables are drawn independently in each mixture component. In this paper, we study the problem of the identifiability of parameters in this model, i.e. interpolation of the parameters of a mixture model from its mixture distribution. First we define the notion of informative variables. Then, we prove that the parameters of the problem are identifiable in the worst-case regime, if and only if the number of informative variables is greater than or equal to 2K − 1. As a result, in the worst-case analysis of the identifiability problem of finite mixture models, the number of required informative variables is Θ(K) and it is independent of the state space size.

In the problems of Genome-Wide Association Study (GWAS), the objective is to associate subsequences of individual's genomes to the observable characteristics called phenotypes. The genome containing the biological information of an individual can be represented by a sequence of lengthG. Many observable characteristics of the individuals can be related to a subsequence of a given lengthL, calledcausal subsequence. The environmental affects make the relation between the causal subsequence and the observable characteristics a stochastic function. Our objective in this paper is to detect the causal subsequence of a specific phenotype using a dataset ofNindividuals and their observed characteristics. We introduce an abstract formulation of GWAS which allows us to investigate the problem from an information theoretic perspective. In particular, as the parametersN,G, andLgrow, we observe a threshold effect at [(Gh(L/G))/N], whereh(.) is the binary entropy function. This effect allows us to define the capacity of recovering the causal subsequence by denoting the rate of the GWAS problem as [(Gh(L/G))/N]. We develop an achievable scheme and a matching converse for this problem, and thus characterize its capacity in two scenarios: the zero-error-rate and the ε-error-rate.

Genome-Wide Association Study (GWAS) addresses the problem of associating subsequences of individuals' genomes to the observable characteristics called phenotypes. In a genome of length G, it is observed that each characteristic is only related to a specific subsequence of it with length L, called the causal subsequence. The objective is to recover the causal subsequence, using a dataset of N individuals' genomes and their observed characteristics. Recently, the problem has been investigated from an information theoretic point of view in [1]. It has been shown that there is a threshold effect for reliable learning of the causal subsequence at [[Gh(L/G)]/N] by characterizing the capacity of it. Here h(.) denotes the binary entropy function. However, it is assumed that the dataset is collected from one population and the problem of mixed population datasets is not considered in [1], which is observed in many practical settings. In this paper, we study the mixed population version of GWAS, where we assume that the dataset is gathered from K subpopulations, rather than one. Each subpopulation has a specific causal subsequence for the observed characteristic and the subpopulation origins of individuals are latent. The objective is to recover all the causal subsequences with high accuracy. We investigate the fundamental limits of mixed population GWAS and characterize its capacity. It is observed that for a special class of two subpopulations, the capacity is one-fourth of the capacity of unmixed population case with the same parameters. Also, the capacity of this problem has connections to the capacity region of the Multiple Access Channel (MAC).

Centralized coded caching and delivery is studied for a partially-connected fog radio access network (F-RAN), whereby a set of H edge nodes (ENs) (without caches), connected to a cloud server via orthogonal fronthaul links, serve K users over the wireless edge. The cloud server is assumed to hold a library of N files, each of size F bits; and each user, equipped with a cache of size MF bits, is connected to a distinct set of r ENs; or equivalently, the wireless edge from the ENs to the users is modeled as a partial interference channel. The objective is to minimize the normalized delivery time (NDT), which refers to the worst case delivery latency, when each user requests a single file from the library. An achievable coded caching and transmission scheme is proposed, which utilizes maximum distance separable (MDS) codes in the placement phase, and real interference alignment (IA) in the delivery phase, and its achievable NDT is presented for r = 2 and arbitrary cache size M, and also for arbitrary values of r when the cache capacity is sufficiently large.

Considering cache enabled networks, optimal content placement minimizing the total cost of communication in such networks is studied, leading to a surprising fundamental 0-1 law for non-redundant cache placement strategies, where the total cache sizes associated with each file does not exceed the file size. In other words, for such strategies, we prove that any non-redundant cache placement strategy can be transformed, with no additional cost, to a strategy in which at every node, each file is either cached completely or not cached at all. Moreover, we obtain a sufficient condition under which the optimal cache placement strategy is in fact non-redundant. This result together with the 0-1 law reveals that situations exist, where optimal content placement is achieved just by uncoded placement of whole files in caches.

Fundamental limits of communication is studied in a 4 × 4 interference network, in which the transmitters are equipped with cache memories. Each of the receivers requests one file from a library of N equal-size files. The caches at the transmitters are filled without the knowledge of the user demands, such that all possible demand combinations can be satisfied reliably over the interference channel. The achievable normalized delivery time (NDT) is studied under centralized cache placement. By combining the interference alignment (IA) and zero-forcing (ZF) techniques, a novel caching and transmission scheme is presented, and is shown to be optimal for all possible cache sizes; fully characterizing the NDT for the 4× 4 interference network with caches at the transmitter side.

BACKGROUND: Current development of sequencing technologies is towards generating longer and noisier reads. Evidently, accurate alignment of these reads play an important role in any downstream analysis. Similarly, reducing the overall cost of sequencing is related to the time consumption of the aligner. The tradeoff between accuracy and speed is the main challenge in designing long read aligners. RESULTS: We propose Meta-aligner which aligns long and very long reads to the reference genome very efficiently and accurately. Meta-aligner incorporates available short/long aligners as subcomponents and uses statistics from the reference genome to increase the performance. Meta-aligner estimates statistics from reads and the reference genome automatically. Meta-aligner is implemented in C++ and runs in popular POSIX-like operating systems such as Linux. CONCLUSIONS: Meta-aligner achieves high recall rates and precisions especially for long reads and high error rates. Also, it improves performance of alignment in the case of PacBio long-reads in comparison with traditional schemes.

In this paper, we consider multiple cache-enabled clients connected to multiple servers through an intermediate network. We design several topology-aware coding strategies for such networks. Based on the topology richness of the intermediate network, and types of coding operations at internal nodes, we define three classes of networks, namely, dedicated, flexible, and linear networks. For each class, we propose an achievable coding scheme, analyze its coding delay, and also compare it with an information theoretic lower bound. For flexible networks, we show that our scheme is order-optimal in terms of coding delay and, interestingly, the optimal memory-delay curve is achieved in certain regimes. In general, our results suggest that, in the case of networks with multiple servers, type of network topology can be exploited to reduce service delay.

The diamond channel is a dual-hop communication system composed of a source, and a destination connected through two noninterfering relays. Operating in the half-duplex mode, relays are not capable of simultaneous transmission and reception of signals. This paper studies coding and scheduling schemes achieving within constant gap from the maximum achievable rate possible assuming the scheduling is fixed for all messages and known to all nodes prior to transmission. It is shown that under constant power constraints, a simple transmission scheme for relays is within 0.71 bits of the optimum rate. It is also demonstrated that the proposed scheme can attain the optimum rate, when channels satisfy a certain property. Furthermore, it is proved that under average power constraints, the same scheme can be used to achieve within 3.6 bits of the optimum rate.

In this paper, we develop the machinery of real interference alignment. This machinery is extremely powerful in achieving the sum degrees of freedom (DoF) of single antenna systems. The scheme of real interference alignment is based on designing single-layer and multilayer constellations used for modulating information messages at the transmitters. We show that constellations can be aligned in a similar fashion as that of vectors in multiple antenna systems and space can be broken up into fractional dimensions. The performance analysis of the signaling scheme makes use of a recent result in the field of Diophantine approximation, which states that the convergence part of the Khintchine-Groshev theorem holds for points on nondegenerate manifolds. Using real interference alignment, we obtain the sum DoF of two model channels, namely the Gaussian interference channel (IC) and the X channel. It is proved that the sum DoF of the K-user IC is (K/2) for almost all channel parameters. We also prove that the sum DoF of the X-channel with K transmitters and M receivers is (K M/K + M - 1) for almost all channel parameters.

The reference-based DNA shotgun assembly problem is studied from an information-theoretic point of view. The entire sequence has to be assembled based on a reference sequence which is a noisy version of the desired one, and a set of short reads sampled from the desired sequence. Two necessary conditions on the underlying parameters for reconstruction are obtained. A reference-based assembly algorithm is proposed, and it is shown that under these conditions the algorithm can reconstruct the sequence with high probability.

We establish the fundamental limits of DNA shotgun sequencing under noisy reads. We show a surprising result: for the i.i.d. DNA model, noisy reads are as good as noiseless reads, provided that the noise level is below a certain threshold which can be surprisingly high. As an example, for a uniformly distributed DNA sequence and a symmetric substitution noisy read channel, the threshold is as high as 19%.

A number of recent source coding techniques compress the source signal into multiple layers such that a destination is able to reconstruct the original signal (with some distortion) even if it has not received all the layers. Implementation of such source coding techniques in wireless networks requires the application of coding mechanisms (such as multilayer coding) which allow unequal error protection for different layers of the transmitted data. In this paper, we study the performance of multilayer coding for quasi-static fading channels where the source and the destination are equipped with multiple antennas and the Channel-State-Information (CSI) is only known at the destination. We limit the study to the scenarios where the destination is only able to perform successive-decoding (joint-decoding is not possible) and the objective is to find the design of a multilayer code which maximizes the average data rate received at the destination. To this end, we first propose a design rule for constructing a proper multilayer code for Multiple-Input-Multiple-Output (MIMO) networks. Furthermore, the paper presents a procedure which uses the proposed design rule to determine the parameters of the multilayer code. The performance of the designed multilayer coding scheme is then studied for different network setups.

A distributed random access network with K users and one Access Point (AP) is considered. It is assumed that users and the AP are equipped with M and N antennas, respectively. Each user independently decides whether to transmit in a time slot or not. We initially focus on two-user random access networks and characterize the network average Degrees of Freedom (DoF)1. For the K-user networks, an upper-bound on the network average DoF is first proposed. Then, it is shown that the proposed upper-bound can be achieved using single stream data transmission for many network configurations. Finally, we show through a few examples that there exist some network configurations where multi-stream data transmission in conjunction with interference alignment is necessary in order to achieve the upper-bound.

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages for two respective receivers via a Gaussian multiple-input multiple-output (MIMO) broadcast channel. An eavesdropper also receives the transmitted signal via another MIMO channel. We first consider the discrete memoryless channel and obtain the capacity region of the degraded channel. The secret dirty paper coding (SDPC) region as an achievable rate region for the general discrete channel is introduced. Relying on the results for the discrete channel, we fully characterize the secrecy capacity region of MIMO broadcast channel. It is shown that the SDPC scheme is optimal. The converse part of the proof relies on the generalized Costa's entropy power inequality and a new channel enhancement strategy in which we only need to enhance the channels of the legitimate receivers, and the channel of the eavesdropper remains unchanged.

DNA sequencing is the basic workhorse of modern day biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence, and these reads are assembled to reconstruct the original sequence. A basic question is: given a sequencing technology and the statistics of the DNA sequence, what is the minimum number of reads required for reliable reconstruction? This number provides a fundamental limit to the performance of any assembly algorithm. For a simple statistical model of the DNA sequence and the read process, we show that the answer admits a critical phenomenon in the asymptotic limit of long DNA sequences: if the read length is below a threshold, reconstruction is impossible no matter how many reads are observed, and if the read length is above the threshold, having enough reads to cover the DNA sequence is sufficient to reconstruct. The threshold is computed in terms of the Renyi entropy rate of the DNA sequence. We also study the impact of noise in the read process on the performance.

DNA sequencing is the basic workhorse of modern day biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence, and these reads are assembled to reconstruct the original sequence. By drawing an analogy between the DNA sequencing problem and the classic communication problem, we define an information theoretic notion of sequencing capacity. This is the maximum number of DNA base pairs that can be resolved reliably per read, and provides a fundamental limit to the performance that can be achieved by any assembly algorithm. We compute the sequencing capacity explicitly for a simple statistical model of the DNA sequence and the read process.

We consider the X channel and the 3-user X network with independent and identically distributed fading across antennas and channel uses and with the delayed channel state information at the transmitters (CSIT). We provide new results for degrees of freedom of these channels. Specifically, we show that the single antenna X channel with delayed CSIT can achieve 6/5 degrees of freedom while the 3-user X network can achieve 5/4 degrees of freedom.

This paper studies a multiple access network with two users and one Access Point (AP). It is assumed that the users and the AP are equipped with M and N antennas, respectively. To access the network, each user independently decides whether to transmit in a time slot or not (no coordination between users). Focusing on the high SNR behavior of the system, this paper presents the optimal value of the network average Degrees of Freedom (DoF) in different network settings. To this end, after finding an upper-bound for the network average DoF, we propose a transmission scheme (based on interference alignment) which achieves this upper-bound. Some illustrative examples are also presented in the paper.

In this paper, the impact of noncoordinated interfering signals on a point to point communication is addressed. While the transmitter has no information about the other users' messages, the receiver has full knowledge of the codebooks of the interfering users and can potentially decode some part of the interference. A simple coding strategy is proposed for this channel. Assuming its own data is decoded successfully, the receiver partitions the set of interfering users into two disjoint subsets, namely the set of decodable users and the set of nondecodable users. Then the transmitter's rate is chosen such that the intended signal can be jointly decoded with the set of decodable users. It is proved that the proposed strategy achieves the capacity of the additive Gaussian channel with Gaussian interfering users. A polynomial time algorithm is proposed to compute the achievable rate of the scheme. This algorithm is based a subroutine which separates the set of interfering users into decodable and nondecodable users in polynomial time. The proposed scheme is also applied to the case of -user interference channel and some achievable points are characterized by successive maximization of users' rates.

A two-user Gaussian Interference Channel (GIC) is considered in which encoders are connected through noiseless links with finite capacities. New genie-aided upper bounds on the sum-capacity are developed which incorporate the capacities of the cooperative links. When the GIC is symmetric, with possibly different cooperation link capacities, the sum-capacity is characterized within 2.13 bits gap for all values of the channel parameters. In the achievable scheme, each transmitter sends a private and a common message, and zero-forces the part of the other transmitter's private message, communicated over the conference between the encoders.

In this paper, a dual-hop communication system composed of a source S and a destination D connected through two non-interfering half-duplex relays, R1and R2, is considered. In the literature of Information Theory, this configuration is known as the diamond channel. In this setup, four transmission modes are present, namely: 1) S transmits, and R1and R2listen (broadcast mode), 2) S transmits, R1listens, and simultaneously, R2transmits and D listens. 3) S transmits, R2listens, and simultaneously, R1transmits and D listens. 4) R1, R2transmit, and D listens (multiple-access mode). Assuming a constant power constraint for all transmitters, a parameter Δ is defined, which captures some important features of the channel. It is proven that for Δ=0 the capacity of the channel can be attained by successive relaying, i.e, using modes 2 and 3 defined above in a successive manner. This strategy may have an infinite gap from the capacity of the channel when Δ≠0. To achieve rates as close as 0.71 bits to the capacity, it is shown that the cases of Δ >0 and Δ0, respectively. Furthermore, it is established that under average power constraints the aforementioned strategies achieve rates as close as 3.6 bits to the capacity of the channel.

A new achievability rate region for the secure discrete memoryless Multiple-Access-Channel (MAC) is presented. Thereafter, a novel secure coding scheme is proposed to achieve a positive Secure Degrees-of-Freedom (S-DoF) in the single-antenna MAC. This scheme converts the single-antenna system into a multiple-dimension system with fractional dimensions. The achievability scheme is based on the alignment of signals into a small sub-space at the eavesdropper, and the simultaneous separation of the signals at the intended receiver. Tools from the field of Diophantine Approximation in number theory are used to analyze the probability of error in the coding scheme.

We consider the K user Multiple Input Multiple Output (MIMO) Gaussian interference channel with M antennas at each transmitter and N antennas at each receiver. It is assumed that channel coefficients are fixed and are available at all transmitters and at all receivers. The main objective of this paper is to characterize the total Degrees Of Freedom (DOF) for this channel. Using a new interference alignment technique which has been recently introduced in, we show that MN/M+N K degrees of freedom can be achieved for almost all channel realizations. Also, a new upper-bound on the total DOF for this channel is derived. This upper-bound coincides with our achievable DOF for K ≥ Ku=ΔM+N/gcd(M,N) where gcd(M,N) denotes the greatest common divisor of M and N. This gives an exact characterization of DOF for MIMO Gaussian interference channel in the case of K ≥ Ku.

The K × 2 multiple input multiple output (MIMO) X-channel with constant channel coefficients available at all transmitters and receivers is considered. A new alignment scheme, named layered interference alignment, is proposed in which both vector and real interference alignment techniques are exploited together with joint processing at receiver sides. Data streams, having fractional multiplexing gains, in the desired directions are sent by transmitters to align the interfering signals at receivers efficiently. To decode the intended messages at receivers, a new number theoretic joint processing technique which exploits the availability of several received antennas, is proposed. This processing is backed up by a recent result in the field of Simultaneous Diophantine Approximation, which is introduced in this paper for the firs time. It is shown that incorporating the layered interference alignment is essential to characterize the total DOF of 2 km/ k+1, in the k × 2 m-antenna X-channel.

In this paper, we first investigate the Degrees Of Freedom (DOF) for the M-user Interference Channel (IC) in static environments with the help of a MIMO relay. The relay stores the received signal during the first time-slot and sends a linearly-transformed version over the next time-slot. Using this scheme, it is shown that Interference Alignment can be done with much less complexity. Having very loose constraints on the channel structure, the proposed method calculates a proper choice for the relay gains such that the M-user IC is able to achieve a DOF of M/2. It is also proved that if the relay's output power scales as P/(log P)twhere P is the power of the transmitters, there is no loss in the achieved DOF. This result is true for all positive and negative ranges of t. In other words, in an M-user IC with quasi-static channel gains, it is possible to achieve M/2 DOF through the use of a MIMO relay whose power grows at a rate slower than that of the transmitters. Similarly, a network of low-power users can benefit from our proposed method if the relay power scales faster than the power of the main transmitters. The results of this paper are valuable when being applied to a practical system. While it is very difficult to use Interference Alignment in M-user IC setup, adding a relay can make alignment more affordable by simplifying the transmitter/receiver structure.

In this paper, a single-hop single-relay system with a direct link between the source and the destination is considered when the relay operates in the half-duplex mode. Motivated by the concept of signal space diversity, this paper introduces signal space cooperation, in which cooperation between the source and the relay is achieved using a novel constellation design. In this approach, the original constellation is expanded so that the expanded constellation consists of all possible combinations of different components of signal points in the original constellation. The expanded constellation enables the relay to extract the required information in order to effectively cooperate in the relay phase, and it helps the destination to efficiently combine received signals during the broadcast phase and the relay phase. The analytical study of the proposed scheme leads to the development of two design criteria for the constellation expansion. Numerical results depict superior performance in comparison with other cooperative schemes, such as the distributed turbo coded cooperative schemes and the trans-modulation scheme.

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages for two respective receivers via a Gaussian MIMO broadcast channel. A wire-tapper also receives the transmitted signal via another MIMO channel. It is assumed that the channels are degraded and the wire-tapper has the worst channel. We establish the capacity region of this scenario. Our achievability scheme is a combination of the superposition of Gaussian codes and randomization within the layers which we will refer to as Secret Superposition Coding. For the outerbound, we use the notion of enhanced channel to show that the secret superposition of Gaussian codes is optimal. It is shown that we only need to enhance the channels of the legitimate receivers, and the channel of the eavesdropper remains unchanged.

In this paper, the degrees of freedom (DOF) of the symmetric 3-user Gaussian interference channel is considered. It is shown that by using un-coded signaling, the achievable DOF is a discontinuous function of the channel parameter. More importantly, for the set of irrational channel gains, which has measure 1 in real numbers, it is proved that the total system's DOF, i.e., 3/2, is achievable. This result is obtained using Hurwitz's theorem in number theory.

In this paper, we first introduce a simple procedure for aligning interference directions in an M×N user MIMO X channel. The scheme is then modified for an M×2 user X channel in which each user is equipped with M + 1 antennas. Next we investigate the degrees of freedom (DOF) for a single antenna X channel in slow fading environments with the help of a simple relay. The relay stores all the received signals and sends their linear combination in subsequent transmissions. Using this scheme, it is shown that adding a relay can help the system to achieve all the available DOF. It is also proved that if the relay's output power scales with P/(log P)s, there is no loss in the achieved DOF as long as s > 0. In other words, in a network with quasi-static channels, it is possible to achieve a higher DOF through the use of randomizing relays whose powers grow at a much slower rate than the main transmitters. Similarly, when there are stricter constraints on the output power scaling of the transmitters, all the DOF can still be utilized, if the relay power can grow with P/(log P)tfor any t > 0. These results suggest that adding relays to a network can be beneficial in terms of simultaneously acquiring higher DOF.

Given a slowly fading channel, the performance of multi-layer coding is studied for single-user scenarios. Both the source and destination are equipped with multiple antennas. The channel state information is perfectly known at the destination but not at the source. The objective is to maximize the average data rate received at the destination when the destination is able to perform successive decoding. This paper, first, proposes a design rule for constructing an infinite-layer code for Multiple Input Multiple Output (MIMO) channels. Furthermore, we present a procedure describing how the introduced design rule is applied to optimally determine the multi-layer code parameters. The achievable rate of the multi-layer coding and successive decoding for the Rayleigh fading 2×2 MIMO channel is also evaluated.

The capacity region of the two-user Gaussian interference channel (IC) is studied. Three classes of channels are considered: weak, one-sided, and mixed Gaussian ICs. For the weak Gaussian IC, a new outer bound on the capacity region is obtained that outperforms previously known outer bounds. The sum capacity for a certain range of channel parameters is derived. For this range, it is proved that using Gaussian codebooks and treating interference as noise are optimal. It is shown that when Gaussian codebooks are used, the full Han–Kobayashi achievable rate region can be obtained by using the naive Han–Kobayashi achievable scheme over three frequency bands (equivalently, three subspaces). For the one-sided Gaussian IC, an alternative proof for the Sato's outer bound is presented. We derive the full Han–Kobayashi achievable rate region when Gaussian codebooks are utilized. For the mixed Gaussian IC, a new outer bound is obtained that outperforms previously known outer bounds. For this case, the sum capacity for the entire range of channel parameters is derived. It is proved that the full Han–Kobayashi achievable rate region using Gaussian codebooks is equivalent to that of the one-sided Gaussian IC for a particular range of channel parameters.

The capacity region of the two-user Gaussian interference channel (IC) is studied. Two classes of channels are considered: weak and mixed Gaussian IC. For the weak Gaussian IC, a new outer bound on the capacity region is obtained that outperforms previously known outer bounds. The sum capacity for a certain range of channel parameters is derived. For this range, it is proved that using Gaussian codebooks and treating interference as noise is optimal. It is shown that when Gaussian codebooks are used, the full Han-Kobayashi (HK) achievable rate region can be obtained by using the naive HK achievable scheme over three frequency bands. For the mixed Gaussian IC, a new outer bound is obtained that outperforms previously known outer bounds. For this case, the sum capacity for the entire range of channel parameters is derived. It is proved that the full HK achievable rate region using Gaussian codebooks is equivalent to that of the one-sided Gaussian IC for a particular range of channel parameters.

In a multiple-antenna system with two transmitters and two receivers, a scenario of data communication, known as the X channel, is studied in which each receiver receives data from both transmitters. In this scenario, it is assumed that each transmitter is unaware of the other transmitter's data (noncooperative scenario). This system can be considered as a combination of two broadcast channels (from the transmitters' points of view) and two multiple-access channels (from the receivers' points of view). Taking advantage of both perspectives, two signaling schemes for such a scenario are developed. In these schemes, some linear filters are employed at the transmitters and at the receivers which decompose the system into either two noninterfering multiple-antenna broadcast subchannels or two noninterfering multiple-antenna multiple-access subchannels. The main objective in the design of the filters is to exploit the structure of the channel matrices to achieve the highest multiplexing gain (MG). It is shown that the proposed noncooperative signaling schemes outperform other known noncooperative schemes in terms of the achievable MG. In particular, it is shown that in some specific cases, the achieved MG is the same as the MG of the system if full cooperation is provided either between the transmitters or between the receivers.

We address data transmission over the M-user Gaussian interference channel, where users send data using single Gaussian codebooks. We first present a polynomial-time algorithm for finding the maximum decodable subset among interfering users, provided the users' rates and powers are given. Given any ordering of users, we characterize an achievable rate vector in which users' rates are successively maximized based on the ordering. It is also shown that in a noncooperative scenario where users refuse to send below their conservative rates, there are achievable vectors that are feasible with respect to the conservative rates vector which can be obtained by using a simple iterative algorithm.

A new structure for multi-base systems is studied in which each user receives data from two nearby base stations, rather than only from the strongest one. This system can be considered as a combination of broadcast and multi-access channels. By taking advantages of both perspectives, an achievable rate region for a discrete memoryless channel modeled by Pr(y1,y2|x1,x2) is derived. In this model, x1and x2represent the transmitted signals by the transmitter one and two, respectively, and y1and y2denote the received signals by the receiver one and two, respectively. In this derivation, it is assumed that each transmitter is unaware of the data of the other transmitter, and therefore x1and x2are independent. To investigate the advantage of this scheme, an efficient signaling method which works at a corner point of the achievable region for multiple-antenna scenarios is developed. In the proposed scheme, each base station only requires the state information of the channels between the other base station and each user. In this paper, the signaling scheme is elaborated for the case that each transmitter/receiver is equipped with three antennas. It is proven that in such a scenario, the multiplexing gain of four is achievable, which outperforms any other conventional schemes

In this paper, we introduce new unblind and blind multiuser detectors for an optical code-division multiple-access system. The detectors have two soft and hard stages. In the soft stage, a soft estimation of the interference is obtained by solving an unconstrained maximum-likelihood problem via the iterative expectation-maximization (EM) algorithm. Then, the hard stage detects the user information bit by solving a one-dimensional Boolean constrained problem conditioned on knowing the interference. Our results reveal that the proposed detectors have very low complexity, and are robust against changes in parameters. Moreover, the numerical results illustrate that despite of their simplicities, our detectors substantially outperform other well-known suboptimum detectors, such as multistage and decorrelating detectors.