This work establishes regularity conditions for consistency and asymptotic normality of the multiple parameter maximum likelihood estimator (MLE) from censored data, where the censoring mechanism is in the form of 1-bit measurements. The underlying distribution of the uncensored data is assumed to belong to the exponential family, with natural parameters expressed as a linear combination of the predictors, known as generalized linear model (GLM). As part of the analysis, the Fisher information matrix is also derived for both censored and uncensored data, which helps to quantify the impact of censoring and assess the performance of the MLE. The choice of a GLM allows one to consider a variety of practical examples where 1-bit estimation is of interest. In particular, it is shown how the derived results can be used to analyze two practically relevant scenarios: the Gaussian model with both unknown mean and variance, and the Poisson model with an unknown mean.

This paper proposes a novel coding scheme to ensure resilience in millimeter-wave networks, where links are highly sensitive to blockages. The proposed scheme deploys multilevel codes to control the received information and provide different reliability guarantees for different information streams based on their priority. Unlike traditional multilevel coding designs, the proposed scheme maintains low design and operational complexity as the number of paths in the network increases. The achievable rate region of the proposed scheme is characterized and shown to be information-theoretical optimal for the case of two priority levels.

In this work, we consider the problem of distributed matrix-vector product, where a server distributes the task of the computation among n worker nodes. In particular, it is assumed thatTmatrix-vector products have to be computed, where the matrix remains constant, whereas the vector changes each time. It is assumed thatLout of thenworkers are compromised (but non-communicating) and may return incorrect results to the task assigned to them. Moreover, these compromised workers are unreliable, that is, each compromised worker may return an incorrect and correct result with probabilities α and 1 − α, respectively, at any given time. The server aims to identify this set of unreliable compromised workers so that it can remove them from future computations. This work proposes and analyzes three probabilistic group testing schemes to achieve this: (i) a noise-level-independent non-adaptive scheme, (ii) a noise-level-dependent non-adaptive scheme, and (iii) a noise-level-dependent two-stage adaptive scheme. In particular, the third scheme is shown to be order-optimal, up to a constant multiplicative factor, for certain regimes of α andL. Using the proposed group testing schemes, sparse parity-check codes are constructed, which are used in the considered distributed computing framework for encoding, decoding, and identifying the unreliable workers. This methodology has two distinct features: (i) the computational cost of identifying the set ofLunreliable workers at the server is considerably lower than existing distributed computing methods in the literature, and (ii) the encoding and decoding functions are computationally efficient.

This paper explores Bayesian lower bounds on the minimum mean squared error (MMSE) that belong to the well-known Ziv-Zakai family. The Ziv-Zakai technique relies on connecting the bound to an$\mathsf M$-ary hypothesis testing problem. There are three versions of the Ziv-Zakai bound (ZZB): the first version relies on the so-calledvalley-filling function, the second one is a relaxation of the first bound which omits the valley-filling function, and the third one, namely the single-point ZZB (SZZB), replaces the integration present in the first two bounds with a single point maximization. The first part of this paper focuses on providing the most general version of the bounds. It is shown that these bounds hold without any assumption on the distribution of the estimand. This makes the bounds applicable to discrete and mixed distributions. Then, the SZZB is extended to an$\mathsf M$-ary setting and a version of it that holds for the multivariate setting is provided. In the second part, general properties of these bounds are provided. First, unlike the BayesianCramér-Rao bound, it is shown that all the versions of the ZZBtensorize. Second, a characterization of thehigh-noiseasymptotic is provided, which is used to argue about the tightness of the bounds. Third, a completelow-noiseasymptotic is provided under the assumptions of mixed-input distributions and Gaussian additive noise channels. In the low-noise, it is shown that the ZZB is generally tight, but there are examples for which the SZZB is not tight. In the third part, the tightness of the bounds is evaluated. First, it is shown that in the low-noise regime the ZZB without the valley-filling function, and, therefore, also the ZZB with the valley-filling function, are tight for mixed-input distributions and Gaussian additive noise channels. Second, for discrete inputs it is shown that the ZZB with the valley-filling function is always sub-optimal, and equal to zero without the valley-filling function. Third, unlike for the ZZB, an example is shown for which the SZZB is tight to the MMSE for discrete inputs. Fourth, sufficient and necessary conditions for the tightness of the bounds are provided. Finally, some examples are provided in which the bounds in the Ziv-Zakai family outperform other well-known Bayesian lower bounds, namely the Cramér-Rao bound and the maximum entropy bound.

Achieving ultra-reliable low-latency communications (URLLC) is critical for the operation of data-intensive applications and for ensuring seamless connectivity. Millimeter-wave (mmWave) technology is expected to support URLLC by expanding the available spectrum and providing multi-gigabit services. However, a well-recognized challenge is that mmWave communication links are susceptible to blockage, which may lead to communication disruptions. Conventional approaches, such as interleaving and feedback mechanisms provide resilience against such blockages at the cost of incurring additional delay, which may be too large to support URLLC effectively. This calls for novel techniques to develop resilient transmission mechanisms that can support URLLC. This paper develops gracefully resilient transmission mechanisms by deploying multilevel codes over space and over time. These codes allow the control of the received information and they accommodate different quality of service requirements of different information streams. Our evaluations, carried out also within the ns-3 network simulator, show that deploying these codes leads to attractive trade-offs between rate, delay, and outage probability.

Millimeter-wave (mmWave) spectrum is expected to support data-intensive applications that require ultra-reliable low-latency communications (URLLC). However, mmWave links are highly sensitive to blockage, which may lead to disruptions in the communication. Traditional techniques that build resilience against such blockages (among which are interleaving and feed-back mechanisms) incur delays that are too large to effectively support URLLC. This calls for novel techniques that ensure resilient URLLC. In this paper, we propose to deploy multilevel codes over space and over time. These codes offer several benefits, such as they allow to control what information is received and they provide different reliability guarantees for different information streams based on their priority. We also show that deploying these codes leads to attractive trade-offs between rate, delay, and outage probability. A practically-relevant aspect of the proposed technique is that it offers resilience while incurring a low operational complexity.

This paper investigates the rate-distortion function, under a squared error distortion$D$, for an n-dimensional random vector uniformly distributed on an$(n-1)$-sphere of radius$R$. First, an expression for the rate-distortion function is derived for any values of$n, D$, and$R$. Second, two types of asymptotics with respect to the rate-distortion function of a Gaussian source are characterized. More specifically, these asymptotics concern the low-distortion regime (that is,$D\rightarrow 0$) and the high-dimensional regime (that is,$n\rightarrow\infty$).

In this work, we consider the sparsity-constrained community-based group testing problem, where the population follows a community structure. In particular, the community consists of$F$families, each with$M$members. A number$k_{f}$out of the$F$families are infected, and a family is said to be infected if$k_{m}$out of its$M$members are infected. Furthermore, the sparsity constraint allows at most$\rho_{T}$individuals to be grouped in each test. For this sparsity-constrained community model, we propose a probabilistic group testing algorithm that can identify the infected population with a vanishing probability of error and we provide an upper-bound on the number of tests. When$k_{m}=\Theta(M)$and$M=\omega(\log(FM))$, our bound outperforms the existing sparsity-constrained group testing results trivially applied to the community model. If the sparsity constraint is relaxed, our achievable bound reduces to existing bounds for community-based group testing. Moreover, our scheme can also be applied to the classical dilution model, where it outperforms existing noise-level-independent schemes in the literature.

Classification is a fundamental task in many applications on which data-driven methods have shown outstanding performances. However, it is challenging to determine whether such methods have achieved the optimal performance. This is mainly because the best achievable performance is typically unknown and hence, effectively estimating it is of prime importance. In this paper, we consider binary classification problems and we propose an estimator for the false positive rate (FPR) of the Bayes classifier, that is, the optimal classifier with respect to accuracy, from a given dataset. Our method utilizes soft labels, or real-valued labels, which are gaining significant traction thanks to their properties. We thoroughly examine various theoretical properties of our estimator, including its consistency, unbiasedness, rate of convergence, and variance. To enhance the versatility of our estimator beyond soft labels, we also consider noisy labels, which encompass binary labels. For noisy labels, we develop effective FPR estimators by leveraging a denoising technique and the Nadaraya-Watson estimator. Due to the symmetry of the problem, our results can be readily applied to estimate the false negative rate of the Bayes classifier.

We consider the problem of secure communication over a noiseless 1-2-1 network, an abstract model introduced to capture the directivity characteristic of mmWave communications. We focus on structured networks, which we refer to as 1-2-1 atomic networks. Broadly speaking, these are characterized by a source, a destination, and three layers of intermediate nodes with sparse connections. The goal is for the source to securely communicate to the destination in the presence of an eavesdropper with unbounded computation capabilities, but limited network presence. We derive novel upper and lower bounds on the secrecy capacity of 1-2-1 atomic networks. These bounds are shown to be tighter than existing bounds in some regimes. Moreover, in such regimes, the bounds match and hence, they characterize the secrecy capacity of 1-2-1 atomic networks.

We consider the problem of private approximate nearest neighbor (ANN) search. A user seeks the closest vector to a target query$q$among$M$vectors stored in a system of$N$non-colluding databases. The user aims to retrieve the ANN without revealing information about$q$to any of the$N$databases. We provide an information-theoretic formulation of the problem and propose a scheme based on a tree-structured ANN search mechanism. The proposed scheme uses a coding-theoretic approach to traverse the branch in the tree structure that leads to the approximately closest vector to$q$while guaran-teeing perfect information-theoretic privacy. We prove that our approach achieves a communication cost of$O(N^{2}M^{\frac{1}{N-1})}$for$N$databases. For large$M$, this communication cost is lower than competing cryptographic ANN search protocols.

Image search and retrieval tasks can perpetuate harmful stereotypes, erase cultural identities, and amplify social disparities. Current approaches to mitigate these representational harms balance the number of retrieved items across population groups defined by a small number of (often binary) attributes. However, most existing methods overlook intersectional groups determined by combinations of group attributes, such as gender, race, and ethnicity. We introduce Multi-Group Proportional Representation (MPR), a novel metric that measures representation across intersectional groups. We develop practical methods for estimating MPR, provide theoretical guarantees, and propose optimization algorithms to ensure MPR in retrieval. We demonstrate that existing methods optimizing for equal and proportional representation metrics may fail to promote MPR. Crucially, our work shows that optimizing MPR yields more proportional representation across multiple intersectional groups specified by a rich function class, often with minimal compromise in retrieval accuracy. Code is provided at https://github.com/alex-oesterling/multigroup-proportional-representation.

This paper studies the problem of data permutation recovery, where the goal is to estimate the ordering of an$n$-dimensional data vector given a noisy observation of it. The focus is on scenarios where the noise is additive Gaussian with an arbitrary known covariance matrix. The goal is to characterize the probability of error and its behavior when a linear decoder (that is, a linear estimator followed by a sorting operation) is employed. First, a general expression is derived for the probability of error when a linear decoder is used. The derived expression holds for any continuous distribution of the input data vector, and when the noise has memory. Then, the rates of convergence of the probability of error in the low-noise and high-noise regimes are investigated when a simple linear decoder is used. It is shown that in the low-noise regime, the probability of error can quadratically increase with$n$, and in the high-noise regime it behaves as$1-1/n!$for several distributions of interest. Finally, upper and lower bounds on the probability of correctness with respect to$n$are derived for the case of an i.i.d. data distribution and show that the rate of convergence is at least exponential in$n$. The results showcase that the permutation recovery problem is noise dominated, which motivates the study of more relaxed versions of the permutation recovery problem that are also discussed.

The interference from active to passive users is a well-recognized challenge in millimeter-wave (mmWave) communications. We propose a method that enables to limit the interference on passive users (whose presence may not be detected since they do not transmit) with a small penalty to the throughput of active users. Our approach abstracts away (in a simple, yet informative way) the physical layer component and it leverages the directivity of mmWave links and the available network path diversity. We provide linear programming formulations, lower bounds on active users rates, numerical evaluations, and we establish a connection with the problem of (information theoretically) secure communication over mmWave networks.

Millimeter-wave (mmWave) networks support a large variety of applications, particularly delay-sensitive applications by providing high-speed communication. A well-recognized challenge in mmWave communications is that mmWave links are susceptible to blockage and thus, communication may get disrupted. In this paper, we design and evaluate low-complexity proactive transmission mechanisms for mmWave networks that are resilient to such disruptions. Our mechanisms build on the multipath environment and on the existence of accurate models for link blockage probabilities in mmWave networks. We propose the deployment of symmetric multilevel codes across paths to achieve an attractive trade-off between the average information rate and a graceful performance degradation. Our numerical evaluations show that our proposed coding schemes indeed provide a graceful performance degradation compared to alternative schemes (such as erasure correcting codes), while significantly reducing the code complexity compared to traditional multilevel code designs.

This work considers a co-located MIMO radar with MTtransmitting and MRreceiving antennas in a so-called massive MIMO regime, that is, where the number of virtual spatial antennas N = MTMRis large. Recently, it has been demonstrated that as N grows to infinity, one can fully characterize the false alarm and detection probabilities with very minimal assumptions on the disturbance vector. In this work, these results are partially refined and a lower bound on the probability of detection is provided for any fixed, finite N under certain randomness models for the noise. This result can serve as a rule of thumb for the design of massive MIMO radar systems by indicating the number of antennas required to attain a desired target detection probability.

The problem of distributed matrix-vector product is considered, where the server distributes the task of the computation among n worker nodes, out of which L are compromised (but non-colluding) and may return incorrect results. Specifically, it is assumed that the compromised workers are unreliable, that is, at any given time, each compromised worker may return an incorrect and correct result with probabilities α and 1−α, respectively. Thus, the tests are noisy. This work proposes a new probabilistic group testing approach t o identify the unreliable/compromised workers with $O\left( {\frac{{L\log (n)}}{\alpha }} \right)$ tests. Moreover, using the proposed group testing method, sparse parity-check codes are constructed and used in the considered distributed computing framework for encoding, decoding and identifying the unreliable workers. This methodology has two distinct features: (i) the cost of identifying the set of L unreliable workers at the server can be shown to be considerably lower than existing distributed computing methods, and (ii) the encoding and decoding functions are easily implementable and computationally efficient.

This paper explores the Ziv-Zakai bound (ZZB), which is a well-known Bayesian lower bound on the Minimum Mean Squared Error (MMSE). First, it is shown that the ZZB holds without any assumption on the distribution of the estimand, that is, the estimand does not necessarily need to have a probability density function. The ZZB is then further analyzed in the high-noise and low-noise regimes and shown to always tensorize. Finally, the tightness of the ZZB is investigated under several aspects, such as the number of hypotheses and the usefulness of the valley-filling function. In particular, a sufficient and necessary condition for the tightness of the bound with continuous inputs is provided, and it is shown that the bound is never tight for discrete input distributions with a support set that does not have an accumulation point at zero.

This work uses non-adaptive probabilistic group testing to find a set of L defective items out of n items. In contrast to traditional group testing, in the considered setup each item can hide itself (or become inactive) during any given test with probability 1−α and is active with probability α. The authors of [Cheraghchi et al.] proposed an efficiently decodable probabilistic group testing scheme which requires $O\left( {\frac{{L\log (n)}}{{{\alpha ^3}}}} \right)$ tests for the per-instance scenario (where the group testing matrix works for any arbitrary, but fixed, set of L defective items) and $O\left( {\frac{{{L^2}\log (n/L)}}{{{\alpha ^3}}}} \right)$ tests for the universal scenario (where the same group testing matrix works for all possible defective sets of L items). The contribution of this work is two-fold: (i) with a slight modification in the construction of the group testing matrix proposed by [Cheraghchi et al.], the corresponding bounds on the number of sufficient tests are improved to $O\left( {\frac{{L\log (n)}}{{{\alpha ^2}}}} \right)$ and $O\left( {\frac{{{L^2}\log (n/L)}}{{{\alpha ^2}}}} \right)$ for the per-instance and universal scenarios respectively, while still using their efficient decoding method; and (ii) it is shown that the same bounds also hold for the fixed pool-size probabilistic group testing scenario, where in every test a fixed number of items are included for testing.

Classification is a fundamental task in science and engineering on which machine learning methods have shown outstanding performances. However, it is challenging to determine whether such methods have achieved the Bayes error rate, that is, the lowest error rate attained by any classifier. This is mainly due to the fact that the Bayes error rate is not known in general and hence, effectively estimating it is paramount. Inspired by the work by Ishida et al. (2023), we propose an estimator for the Bayes error rate of supervised multi-class classification problems. We analyze several theoretical aspects of such estimator, including its consistency, unbiasedness, convergence rate, variance, and robustness. We also propose a denoising method that reduces the noise that potentially corrupts the data labels, and we improve the robustness of the proposed estimator to outliers by incorporating the median-of-means estimator. Our analysis demonstrates the consistency, asymptotic unbiasedness, convergence rate, and robustness of the proposed estimators. Finally, we validate the effectiveness of our theoretical results via experiments both on synthetic data under various noise settings and on real data.

It is well known that central order statistics exhibit a central limit behavior and converge to a Gaussian distribution as the sample size grows. This paper strengthens this known result by establishing an entropic version of the central limit theorem that ensures a stronger mode of convergence using the relative entropy. This upgrade in convergence is shown at the expense of extra regularity conditions, which can be considered as mild. To prove this result, ancillary results on order statistics are derived, which might be of independent interest. For instance, a rather general bound on the moments of order statistics, and an upper bound on the mean squared error of estimating the$p \in (0,1)$-th quantile of an unknown cumulative distribution function, are derived. Finally, a discussion on the necessity of the derived conditions for convergence and on the rate of convergence and monotonicity of the relative entropy is provided.

Consider a pair of random vectors$( {\mathbf{X}}, {\mathbf{Y}}) $and the conditional expectation operator$ \mathbb {E}[ {\mathbf{X}}| {\mathbf{Y}}={\mathbf{y}}]$. This work studies analytical properties of the conditional expectation by characterizing various derivative identities. The paper consists of two parts. In the first part of the paper, a general derivative identity for the conditional expectation is derived. Specifically, for the Markov chain$ {\mathbf{U}}\leftrightarrow {\mathbf{X}}\leftrightarrow {\mathbf{Y}}$, a compact expression for the Jacobian matrix of$ \mathbb {E}[ \psi ( {\mathbf{Y}}, {\mathbf{U}})| {\mathbf{Y}}= {\mathbf{y}}]$for a smooth function$\psi $is derived. In the second part of the paper, the main identity is specialized to the exponential family and two main applications are shown. First, it is demonstrated that, via various choices of the random vector$ {\mathbf{U}}$and function$\psi $, one can recover and generalize several known identities (e.g., Tweedie’s formula) and derive some new ones. For example, a new relationship between conditional expectations and conditional cumulants is established. Second, it is demonstrated how the derivative identities can be used to establish new lower bounds on the estimation error. More specifically, using one of the derivative identities in conjunction with a Poincaré inequality, a new lower bound on the minimum mean squared error, which holds for all prior distributions on the input signal, is derived. The new lower bound is shown to be tight in the high-noise regime for the additive Gaussian noise setting.

It is well known that central order statistics exhibit a central limit behavior and converge to a Gaussian distribution as the sample size n grows. This paper strengthens this known result by establishing an entropic version of the central limit theorem (CLT) that ensures a stronger mode of convergence using the relative entropy. In particular, an order $O(1/\sqrt n )$ rate of convergence is established under mild conditions on the parent distribution of the sample generating the order statistics. To prove this result, ancillary results on order statistics are derived, which might be of independent interest.

Millimeter Wave (mmWave) (and beyond) is expected to play an increasingly important role in our wireless infrastructure by expanding the available spectrum and enabling multi-gigabit services. Despite the promising aspects of mmWave communication, mmWave links are highly sensitive to blockage. In this paper, we develop proactive transmission mechanisms that suitably distribute the traffic across multiple paths in the mmWave network, with the two-fold objective of ensuring resilience against link blockages and achieve high end-to-end packet delivery rate. We present examples of resilience-capacity trade-off curves and show that there exist network topologies for which the worst-case and average approximate capacities are achieved by activating overlapping paths. We also show that this can provide additional benefits, such as decreasing the variance of the achieved rate.

This paper considers a distributed computing framework, where the task of T matrix-vector products is distributed among n worker machines. External adversaries have access to a subset ℒ (the cardinality of which is |ℒ|) of these machines, and can maliciously perturb the result of each of their computations with probability α. To correctly recover each matrixvector product, the master has to identify a set (of a fixed cardinality) of ‘unattacked’ worker machines. Towards this end, this work proposes four schemes that aim at performing such an identification. These schemes are analyzed and compared under different regimes of (|ℒ|,α) for the two cases when |ℒ| is (1) known or (2) unknown at the master.

This paper considers the problem of recovering the ranking of a data vector from noisy observations, up to a distortion. Specifically, the noisy observations consist of the original data vector corrupted by isotropic additive Gaussian noise, and the distortion is measured in terms of a distance function between the estimated ranking and the true ranking of the original data vector. First, it is shown that an optimal (in terms of error probability) decision rule for the estimation task simply outputs the ranking of the noisy observation. Then, the error probability incurred by such a decision rule is characterized in the low-noise regime, and shown to grow sublinearly with the noise standard deviation. This result highlights that the proposed approximate version of the ranking recovery problem is significantly less noise-dominated than the exact recovery considered in [Jeong, ISIT 2021].

This paper studies the minimum mean squared error (MMSE) of estimating X ∈ ℝdfrom the noisy observation Y ∈ ℝk, under the assumption that the noise (i.e., Y|X) is a member of the exponential family. The paper provides a new lower bound on the MMSE. Towards this end, an alternative representation of the MMSE is first presented, which is argued to be useful in deriving closed-form expressions for the MMSE. This new representation is then used together with the Poincaré inequality to provide a new lower bound on the MMSE. Unlike, for example, the Cramér-Rao bound, the new bound holds for all possible distributions on the input X. Moreover, the lower bound is shown to be tight in the high-noise regime for the Gaussian noise setting under the assumption that X is sub-Gaussian. Finally, several numerical examples are shown which demonstrate that the bound performs well in all noise regimes.

The Ziv-Zakai bound is a well-known lower bound on the minimum mean squared error. This article analyzes the performance of this bound in the practically relevant high-noise regime for a broad family of observation models. The goal is to understand whether this bound is tight, and in which scenarios it should be used. It is shown that, while the Ziv-Zakai bound is tight for a certain class of symmetric distributions, in general, it isnottight in the high-noise regime.

This paper considers a diamond network with$n$interconnected relays, namely a network where a source communicates with a destination by hopping information through$n$communicating/interconnected relays. Specifically, the main focus of the paper is on characterizing sufficient conditions under which the$n$+ 1 states (out of the 2npossible ones) in which at most one relay is transmitting suffice to characterize the approximate capacity, that is the Shannon capacity up to an additive gap that only depends on n. Furthermore, under these sufficient conditions, closed form expressions for the approximate capacity and scheduling (that is, the fraction of time each relay should receive and transmit) are provided. A similar result is presented for the dual case, where in each state at most one relay is in receive mode.

This paper considers the problem of recovering the permutation of an n-dimensional random vector X observed in Gaussian noise. First, a general expression for the probability of error is derived when a linear decoder (i.e., linear estimator followed by a sorting operation) is used. The derived expression holds with minimal assumptions on the distribution of X and when the noise has memory. Second, for the case of isotropic noise (i.e., noise with a diagonal scalar covariance matrix), the rates of convergence of the probability of error are characterized in the high and low noise regimes. In the low noise regime, for every dimension$n$, the probability of error is shown to behave proportionally to$\sigma$, where$\sigma$is the noise standard deviation. Moreover, the slope is computed exactly for several distributions and it is shown to behave quadratically in$n$. In the high noise regime, for every dimension$n$, the probability of correctness is shown to behave as$1/\sigma$, and the exact expression for the rate of convergence is also provided.

Consider a pair of random vectors $(\mathrm{X}, \mathrm{Y})$ and the conditional expectation operator $\mathbb{E}[\mathrm{X} \mid \mathrm{Y}=\mathrm{y}]$. This work studies analytic properties of the conditional expectation by characterizing various derivative identities. The paper consists of two parts. In the first part of the paper, a general derivative identity for the conditional expectation is derived. Specifically, for the Markov chain $\mathrm{U} \leftrightarrow \mathrm{X} \leftrightarrow \mathrm{Y}$, a compact expression for the Jacobian matrix of $\mathbb{E}[\mathrm{U} \mid \mathrm{Y}=\mathrm{y}]$ is derived. In the second part of the paper, the main identity is specialized to the exponential family. Moreover, via various choices of the random vector U, the new identity is used to recover and generalize several known identities and derive some new ones. As a first example, a connection between the Jacobian of $\mathbb{E}[\mathrm{X} \mid \mathrm{Y}=\mathrm{y}]$ and the conditional variance is established. As a second example, a recursive expression between higher order conditional expectations is found, which is shown to lead to a generalization of the Tweedy’s identity. Finally, as a third example, it is shown that the k-th order derivative of the conditional expectation is proportional to the $(k+1)$-th order conditional cumulant.

This paper proposes a new model for wireless relay networks referred to as “1-2-1 network”, where two nodes can communicate only if they point “beams” at each other, otherwise no signal can be exchanged or interference can be generated. This model is motivated by millimeter wave communications where, due to the high path loss, a link between two nodes can exist only if beamforming gain at both sides is established, while in the absence of beamforming gain the signal is received well below the thermal noise floor. The main contributions in this paper include: (a) the development of a constant gap approximation for the unicast and multicast capacities of the proposed network model, i.e., a characterization of the network unicast and multicast capacities to within an additive gap, which only depends on the number of nodes and is independent of the channel coefficients and operating SNR; and (b) the design of algorithms that run in polynomial time in the number of nodes and compute the approximate unicast and multicast capacities, as well as their corresponding optimal beam scheduling strategies. These results are derived both forfull-duplexandhalf-duplexmodes of operation at the relays: while in full-duplex the transmit and receive beams at a relay can be simultaneously active, in half-duplex only one can be active at each point in time. The relation between the approximate multicast capacity and minimum unicast capacity is explored in full-duplex 1-2-1 networks and shown to be dependent on the network structure and the number of destinations, unlike in classical wireless (i.e., without 1-2-1 constraints) full-duplex networks. Finally, network simplification results are proved for the 1-2-1 network model by exploiting the structure of the linear program that represents the approximate capacity.

In this work, we study bounds on the capacity of full-duplex Gaussian 1-2-1 networks with imperfect beamforming. In particular, different from the ideal 1-2-1 network model introduced in [1], in this model beamforming patterns result in side-lobe leakage that cannot be perfectly suppressed. The 1-2-1 network model captures the directivity of mmWave network communications, where nodes communicate by pointing main-lobe "beams" at each other. We characterize the gap between the approximate capacities of the imperfect and ideal 1-2-1 models for the same channel coefficients and transmit power. We show that, under some conditions, this gap only depends on the number of nodes. Moreover, we evaluate the achievable rate of schemes that treat the resulting side-lobe leakage as noise, and show that they offer suitable solutions for implementation.

This paper considers the Gaussian half-duplex diamond n-relay network, which consists of a broadcast hop between the source and n relays, and of a multiple access hop between the relays and the destination. The n relays do not communicate with each other and operate in half-duplex mode. The main focus of the paper is on answering the following question: What fraction of the approximate capacity of the entire network can be retained by only operating the highest-performing single relay? It is shown that a fraction f = 1/(2 + 2cos (2π/n + 2)) of the approximate capacity of the entire network can always be guaranteed. This fraction is also shown to be tight, that is, there exist Gaussian half-duplex diamond n-relay networks for which exactly an f fraction of the approximate capacity of the entire network can be achieved by using only the highest-performing relay.

This paper considers a noisy data structure recovery problem. Specifically, the goal is to investigate the following question: Given a noisy observation of the data, according to which permutation was the original data sorted? The main focus is on scenarios where data is generated according to an isotropic Gaussian distribution, and the perturbation consists of adding Gaussian noise with diagonal scalar covariance matrix. This problem is posed within a hypothesis testing framework. First, the optimal decision criterion is characterized and shown to be identical to the hypothesis of the observation. Then, by leveraging the structure of the optimal decision criterion, the probability of error is characterized. Finally, the logarithmic behavior (i.e., the exponent) of the probability of error is derived in the regime where the dimension of the data goes to infinity.

This work considers a random sample X1,X2,…,Xndrawn independently and identically distributed from some known parent distribution PXwith X(1)≤ X(2)≤ … ≤ X(n)being the order statistics of the sample. Under the assumption of an invertible cumulative distribution function associated with the parent distribution PX, a distribution-free property is established showing that the f-divergence between the joint distribution of order statistics and the product distribution of order statistics does not depend on PX. Moreover, it is shown that the mutual information between two subsets of order statistics also satisfies a distribution-free property; that is, it does not depend on PX. Furthermore, the decoupling rates between X(r)and X(m)(i.e., rates at which the mutual information approaches zero) are characterized for various choices of (r,m). The work also considers discrete distributions, which do not satisfy the previously-stated invertibility assumption, and it is shown that no such distribution-free property holds: the mutual information between order statistics does depend on the parent distribution PX. Upper bounds on the decoupling rates in the discrete setting are also established.

This paper studies the problem of secure communication over noiseless 1-2-1 networks, an abstract model for networks with directional communication capabilities such as mmWave networks. A secure transmission scheme is designed and shown to achieve a secure rate that is larger than state-of-the-art lower bounds for a class of 1-2-1 network topologies. The proposed scheme leverages the scheduling nature of 1-2-1 networks, the network topology, as well as storage at intermediate nodes to create shared randomness with the source to improve the secure rate. Finally, a novel outer bound is derived and shown to match the achievability bound under certain network conditions, hence characterizing the secure capacity in such regimes.

This paper considers a diamond network with two interfering relays, where the source communicates with the destination via a layer of 2 half-duplex relays that can communicate with each other. The main focus is on characterizing the 3 relay receive/transmit configuration states (out of the 4 possible ones) that suffice to achieve the approximate capacity of the network. Towards this end, the binary linear deterministic approximation of the Gaussian noise channel is analyzed, and explicit scheduling and relaying schemes are presented. These schemes quantify the amount of information that each relay is responsible for sending to the destination, as well as the fraction of time each relay should receive and transmit.

This letter considers an M-ary hypothesis testing problem on an n-dimensional random vector perturbed by the addition of Gaussian noise. A novel expression for the gradient of the error probability, with respect to the covariance matrix of the noise, is derived and shown to be a function of the cross-covariance matrix between the noise matrix (i.e., the matrix obtained by multiplying the noise vector by its transpose) and Bernoulli random variables associated with the correctness event.

This paper investigates the problem of secure communication in a wireline noiseless scenario where a source wishes to communicate to a number of destinations in the presence of a passive external adversary. Different from the multicast scenario, where all destinations are interested in receiving the same message, in this setting different destinations are interested in different messages. The main focus of this paper is on characterizing the secure capacity region, when the adversary has unbounded computational capabilities, but limited network presence. Towards this end, an outer bound on the secure capacity region is derived, and secure transmission schemes are designed and analyzed in terms of achieved rate performance. It is first shown that, for the case of two destinations, the designed scheme matches the outer bound, hence characterizing the secure capacity region. Then, a particular class of networks referred to as two-layer networks is considered, where the source communicates with the destinations by hopping information through one layer of relays. It is shown that the designed scheme is indeed capacity achieving for any two-layer network for which one of the following three conditions is satisfied: (i) the number of destinations is three, (ii) the number of edges eavesdropped by the adversary is one, (iii) the min-cut capacities assume specific values. It is also shown that two-layer networks can be used to model and study a more general class of networks, referred to as separable. The key feature of separable networks is that they can be partitioned into edge disjoint networks that satisfy specific min-cut properties. In particular, it is proved that the secure capacity region of any separable network can be characterized from the secure capacity region of the corresponding two-layer network. Finally, for an arbitrary network topology, a two-phase scheme is designed and its rate performance is compared with the capacity-achieving scheme for networks with two destinations.

This paper investigates the problem of characterizing the capacity of Half-Duplex (HD) line networks, where a source node communicates to a destination node through a multihop path of N relays. If the relays operate in Full-Duplex (FD), it is well known that the capacity of the line network equals the minimum among the point-to-point link capacities in the path. In contrast, this paper considers a different case where the relays operate in HD. In the first part of the paper, it is shown that the approximate capacity (optimal up to a constant additive gap that only depends on the number of nodes in the network) of an HD N-relay line network equals half the minimum of the harmonic means of the point-to-point link capacities of each two consecutive links in the path. It is then proved that the N +1 listen/transmit states (out of the 2Npossible ones) sufficient to characterize the approximate capacity can be found in linear time. In the second part of the paper, it is shown that the problem of finding the path that has the largest HD approximate capacity in a network that can be represented as a graph is NP-hard. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed.

In the traditional index coding problem, a server employs coding to send messages to a set of clients within the same broadcast domain. Each client already has some messages as side information and requests a particular unknown message from the server. All clients learn the coding matrix so that they can decode and retrieve their requested data. Our starting observation comes from the work by Karmoose et al., which shows that learning the coding matrix can pose privacy concerns: it may enable a client to infer information about the requests and side information of other clients. In this paper, we mitigate this privacy concern by allowing each client to have limited access to the coding matrix. In particular, we design coding matrices so that each client needs only to learn some of (and not all) the rows to decode her requested message. We start by showing that this approach can indeed help mitigate that privacy concern. We do so by considering two different privacy metrics. The first one shows the attained privacy benefits based on a geometric interpretation of the problem. Differently, the second metric, referred to as maximal information leakage, provides upper bounds on: (i) the guessing power of the adversaries (i.e., curious clients) when our proposed approach is employed, and (ii) the effect of decreasing the number of accessible rows on the attained privacy. Then, we propose the use of k-limited-access schemes: given an index coding scheme that employs T transmissions, we create a k-limited-access scheme with Tk≥ T transmissions, and with the property that each client needs at most k transmissions to decode her message. We derive upper and lower bounds on Tkfor all values of k, and develop deterministic designs for these schemes, which are universal, i.e., independent of the coding matrix. We show that our schemes are order-optimal for some parameter regimes, and we propose heuristics that complement the universal schemes for the remaining regimes.

This paper presents an estimation framework to assess the performance of the sorting function over data that is perturbed. In particular, the performance is measured in terms of the Minimum Mean Square Error (MMSE) between the values of the sorting function computed on the data without perturbation and the estimate that uses the sorting function applied to the perturbed data. It is first shown that, under certain conditions satisfied by the practically relevant Gaussian noise perturbation, the optimal estimator can be expressed as a linear combination of estimators on the unsorted data. Then, a suboptimal estimator is proposed, and its performance is evaluated and compared to the optimal estimator. Finally, a lower bound on the desired MMSE is derived when data is i.i.d. and has a Gaussian distribution. This is accomplished by solving a new problem that consists of estimating the norm of an unsorted vector from a noisy observation of it.

This paper studies the 1-2-1 half-duplex network model, where two half-duplex nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged or interference can be generated. The main result of this paper is the design of two polynomial-time algorithms that: (i) compute the approximate capacity of the 1-2-1 half-duplex network and, (ii) find the network schedule optimal for the approximate capacity. The paper starts by expressing the approximate capacity as a linear program with an exponential number of constraints. A core technical component consists of building a polynomial-time separation oracle for this linear program, by using algorithmic tools such as perfect matching polytopes and Gomory-Hu trees.

This paper studies the multicast capacity of full-duplex 1-2-1 networks. In this model, two nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged. The main result of this paper is that the approximate multicast capacity can be computed by solving a linear program in the activation times of links connecting pairs of nodes. This linear program has two appealing features: (i) it can be solved in polynomial-time in the number of nodes; (ii) it allows to efficiently find a network schedule optimal for the approximate capacity. Additionally, the relation between the approximate multicast capacity and the minimum approximate unicast capacity is studied. It is shown that the ratio between these two values is not universally equal to one, but it depends on the number of destinations in the network, as well as graph-theoretic properties of the network.

This paper investigates the problem of how to efficiently operate Gaussian half-duplex diamond networks with N relays. It derives sufficient conditions that ensure that the network is operated close to its Shannon capacity, with a linear number in N (instead of exponential) of receive/transmit configuration states. Particularly, these states consist of having either at most one relay receiving or at most one relay transmitting. A transmission scheme is also designed and it is shown that, when the aforementioned conditions are satisfied, it achieves a rate that is to within a constant gap of the Shannon capacity. An appealing feature of the proposed scheme is that it offers guidelines on how to route the information through the relays so that the network operates close to its Shannon capacity.

This paper studies the problem of information theoretic secure communication when a source has private messages to transmit to m destinations, in the presence of a passive adversary who eavesdrops an unknown set of k edges. The information theoretic secure capacity is derived over unit-edge capacity separable networks, for the cases when k = 1 and m is arbitrary, or m = 3 and k is arbitrary. This is achieved by first showing that there exists a secure polynomial-time code construction that matches an outer bound over two-layer networks, followed by a deterministic mapping between two-layer and arbitrary separable networks.

This paper studies a distributed computing setting in which the computing task consists of multiplying a matrix by a vector. A number of worker machines are attacked, i.e., the result of their computation is maliciously perturbed by some adversaries. In particular, the focus is on the case where these adversaries are non-colluding and non-communicating and hence they cannot jointly perturb the results of all the attacked worker machines. First, a condition that ensures that the result of the computing task can be successfully recovered with high probability is derived as a function of the setting parameters. Then, a probabilistic mechanism inspired by group testing is proposed to identify the set of the attacked worker machines, and the corresponding probability of error is derived.

This letter considers the task of estimating the norm of an n-dimensional Gaussian random vector given a noisy/perturbed observation of it. In particular, the focus is on the case of additive Gaussian noise perturbation, which is assumed to be independent of the original vector. First, an expression for the optimal estimator is derived, and then the corresponding minimum mean square error (MMSE) is computed. The regime of large vector size is also analyzed, and it is shown that the MMSE normalized by n equals zero when n → ∞.

This paper explores the network simplification problem in the context of Gaussian half-duplex diamond networks. Specifically, given an N-relay diamond network, this problem seeks to derive fundamental guarantees on the capacity of the best k-relay subnetwork, as a function of the full network capacity. Simplification guarantees are presented in terms of a particular approximate capacity, termed Independent-Gaussian (IG) approximate capacity, that characterizes the network capacity to within an additive gap, which is independent of the channel coefficients and operating SNR. The main focus of this work is when k = N-1 relays are selected out of N relays in a diamond network. First, a simple algorithm is proposed which selects all relays except the one with the minimum IG approximate half-duplex capacity. It is shown that the selected (N -1)-relay subnetwork has an IG approximate half-duplex capacity that is at least 1/2 of the IG approximate half-duplex capacity of the full network and that for the proposed algorithm, this guarantee is tight. Furthermore, this work proves the following tight fundamental guarantee: there always exists a subnetwork of k = N - 1 relays that have an IG approximate half-duplex capacity that is at least equal to (N - 1)/N of the IG approximate half-duplex capacity of the full network. Finally, these results are extended to derive lower bounds on the fraction guarantee when k ∈ [1 : N] relays are selected. The key steps in the proofs lie in the derivation of properties of submodular functions, which provide a combinatorial handle on the network simplification problem for Gaussian half-duplex diamond networks.

This paper starts by assuming a 1-2-1 network, the abstracted noiseless model of mmWave networks that was shown to closely approximate the Gaussian capacity in [1], and studies secure communication. First, the secure capacity is derived for 1-2-1 networks where a source is connected to a destination through a network of unit capacity links. Then, lower and upper bounds on the secure capacity are derived for the case when source and destination have more than one beam, which allow them to transmit and receive in multiple directions at a time. Finally, secure capacity results are presented for diamond 1-2-1 networks when edges have different capacities.

This paper proposes a new model for wireless relay networks referred to as “1-2-1 network”, where two nodes can communicate only if they point “beams” at each other, while if they do not point beams at each other, no signal can be exchanged or interference can be generated. This model is motivated by millimeter wave communications where, due to the high path loss, a link between two nodes can exist only if beamforming gain at both sides is established, while in the absence of beamforming gain the signal is received well below the thermal noise floor. The main result in this paper is that the 1-2-1 network capacity can be approximated by routing information along at most 2N + 2 paths, where N is the number of relays connecting a source and a destination through an arbitrary topology.

It was recently observed in [1], that in index coding, learning the coding matrix used by the server can pose privacy concerns: curious clients can extract information about the requests and side information of other clients. One approach to mitigate such concerns is the use of k-limited-access schemes [1], that restrict each client to learn only part of the index coding matrix, and in particular, at most k rows. These schemes transform a linear index coding matrix of rank T to an alternate one, such that each client needs to learn at most k of the coding matrix rows to decode its requested message. This paper analyzes k-limited-access schemes. First, a worst-case scenario, where the total number of clients n is 2T-1 is studied. For this case, a novel construction of the coding matrix is provided and shown to be order-optimal in the number of transmissions. Then, the case of a general n is considered and two different schemes are designed and analytically and numerically assessed in their performance. It is shown that these schemes perform better than the one designed for the case n=2T-1.

Social groups open up the opportunity for a new form of caching. This paper investigates how a social group of users can jointly optimize bandwidth usage, by each caching network-coded parts of the data demand, and then opportunistically share these parts among themselves upon meeting. First, the problem is formulated as a linear program (LP) with exponential complexity in the number of users. Then, a heuristic algorithm is proposed, which is inspired by the bipartite set-cover problem and operates in polynomial time. For some scenarios, a worst-case performance guarantee of the heuristic with respect to the optimal LP solution is proved. Finally, the performance of the algorithm is assessed using real-world mobility traces synthesized using the SWIM model and from the MIT Reality Mining project data set. The proposed heuristic offers bandwidth savings up to 65% for a waiting time of 30 minutes and up to 28% performance gains with respect to the alternative solutions. These benefits make the algorithm a feasible candidate solution for bandwidth savings.

The problem of operating a Gaussian Half-Duplex (HD) relay network optimally is challenging due to the exponential number of listen/transmit network states that need to be considered. Recent results have shown that, for the class of Gaussian HD networks with N relays, there always exists a simple schedule, i.e., with at most N+1 active states, that is sufficient for approximate (i.e., up to a constant gap) capacity characterization. This paper investigates how to efficiently find such a simple schedule over line networks. Towards this end, a polynomial-time algorithm is designed and proved to output a simple schedule that achieves the approximate capacity. The key ingredient of the algorithm is to leverage similarities between network states in HD and edge coloring in a graph. It is also shown that the algorithm allows to derive a closed-form expression for the approximate capacity of the Gaussian line network that can be evaluated distributively and in linear time.

Using a broadcast channel to transmit clients' data requests may impose privacy risks. In this paper, we tackle such privacy concerns in the index coding framework. We show how a curious client can infer some information about the requests and side information of other clients by learning the encoding matrix used by the server. We propose an information-theoretic metric to measure the level of privacy and show how encoding matrices can be designed to achieve specific privacy guarantees. We then consider a special scenario for which we design a transmission scheme and derive the achieved levels of privacy in closed-form. We also derive upper bounds and we compare them to the levels of privacy achieved by our scheme, highlighting that an inherent trade-off exists between protecting privacy of the request and of the side information of the clients.

Index coding employs coding across clients within the same broadcast domain. This typically assumes that all clients learn the coding matrix so that they can decode and retrieve their requested data. However, learning the coding matrix can pose privacy concerns: it may enable clients to infer information about the requests and side information of other clients [1]. In this paper, we formalize the intuition that the achieved privacy can increase by decreasing the number of rows of the coding matrix that a client learns. Based on this, we propose the use of k-limited-access schemes: given an index coding scheme that employs T transmissions, we create a k-limited-access scheme with Tk≤ T transmissions, and with the property that each client learns at most k rows of the coding matrix to decode its message. We derive upper and lower bounds on Tkfor all values of k, and develop deterministic designs for these schemes for which Tkhas an order-optimal exponent for some regimes.

This paper presents a practical feasibility study of a novel two-phase three-part-message strategy for half-duplex relaying, which features superposition coding and interference-aware cancellation decoding. Aiming to analyze the performance of the proposed scheme in the non-asymptotic regime, this paper evaluates the spectral efficiency with finite block-length and discrete constellation signaling and compares it with the theoretical performance of Gaussian codes with asymptotically large block-lengths. The performance evaluation is carried out on an LTE simulation test bench. During each transmission phase, the modulation and coding scheme is adapted to the channel link qualities to enhance the overall spectral efficiency. A single-antenna source and relay, and a multi-antenna destination are assumed. The static Gaussian and two frequency selective channel models are considered for the proposed scheme. A spectral efficiency comparison with a baseline scheme (non-cooperative two-hop transmission, i.e., the source-destination link is absent) and with the point-to-point transmission strategy (no relay) is presented. The results confirm that physical-layer cooperation and multi-antennas are critical for performance enhancement in heterogeneous networks. Moreover, they show that physical layer cooperation advantages are within practical reach with existing LTE coded-modulation and interference-mitigation techniques, which are prevalent in modern user-equipment.

This paper characterizes the secret message capacity of three networks where two unicast sessions share some of the communication resources. Each network consists of erasure channels with state feedback. A passive eavesdropper is assumed to wiretap any one of the links. The capacity achieving schemes as well as the outer bounds are formulated as linear programs. The proposed strategies are then numerically evaluated and shown to achieve higher rate performances (up to a double single- or sum-rate) with respect to alternative strategies, where the network resources are time-shared among the two sessions. These results represent a step towards the secure capacity characterization for general networks. They also show that, even in configurations for which network coding does not offer benefits in absence of security, it can become beneficial under security constraints.

This paper investigates the simplification problem in Gaussian Half-Duplex (HD) diamond networks. The goal is to answer the following question: what is the minimum (worst-case) fraction of the total HD capacity that one can always achieve by smartly selecting a subset of k relays, out of the N possible ones? We make progress on this problem for k = 1 and k = 2 and show that for N = k + 1, k ∈ |1, 2} at least k/k+1 of the total HD capacity is always approximately (i.e., up to a constant gap) achieved. Interestingly, and differently from the Full-Duplex (FD) case, the ratio in HD depends on N, and decreases as N increases. For all values of N and k for which we derive worst case fractions, we also show these to be approximately tight. This is accomplished by presenting N-relay Gaussian HD diamond networks for which the best k-relay subnetwork has an approximate HD capacity equal to the worst-case fraction of the total approximate HD capacity. Moreover, we provide additional comparisons between the performance of this simplification problem for HD and FD networks, which highlight their different natures.

Social groups give the opportunity for a new form of caching. In this paper, we investigate how a social group of users can jointly optimize bandwidth usage, by each caching parts of the data demand, and then opportunistically share these parts among them upon meeting. We formulate this problem as a Linear Program (LP) with exponential complexity. Based on the optimal solution, we propose a simple heuristic inspired by the bipartite set-cover problem that operates in polynomial time. Furthermore, we prove a worst case gap between the heuristic and the LP solutions. Finally, we assess the performance of our algorithm using real-world mobility traces from the MIT Reality Mining project dataset.

This paper studies networks that consist of N half-duplex relays assisting the communication between a source and a destination. In ISIT'12 Brahma et al. conjectured that in Gaussian half-duplex diamond networks (i.e., without a direct link between the source and the destination, and with N non-interfering relays), an approximately optimal relay scheduling policy (i.e., achieving the cut-set upper bound to within a constant gap uniformly over all channel gains) has at most N + 1 active states (i.e., at most N + 1 out of the 2Npossible relay listen-transmit configurations have a strictly positive probability). Such relay scheduling policies were referred to as simple. In ITW'13, we conjectured that simple approximately optimal relay scheduling policies exist for any Gaussian half-duplex multi-relay network irrespectively of the topology. This paper formally proves this more general version of the conjecture and shows it holds beyond Gaussian noise networks. In particular, for any class of memoryless half-duplex N-relay networks with independent noises and for which independent inputs are approximately optimal in the cut-set upper bound, an approximately optimal simple relay scheduling policy exists. The key step of the proof is to write the minimum of the submodular cut-set function by means of its Lovász extension and use the greedy algorithm for submodular polyhedra to highlight structural properties of the optimal solution. This, together with the saddle-point property of min-max problems and the existence of optimal basic feasible solutions for linear programs, proves the conjecture. As an example, for N-relay Gaussian networks with independent noises, where each node is equipped with multiple antennas and where each antenna can be configured to listen or transmit irrespectively of the others, the existence of an approximately optimal simple relay scheduling policy with at most N + 1 active states, irrespectively of the total number of antennas in the system, is proved.

This paper studies the two-user causal cognitive interference channel (CCIC), where two transmitters aim to communicate independent messages to two different receivers via a common channel. One source, referred to as the cognitive, is capable of overhearing the other source, referred to as the primary, through a noisy in-band link and thus can assist in sending the primary's data. The authors of this paper recently characterized to within a constant gap the capacity of the symmetric Gaussian CCIC in: 1) the strong interference regime and 2) for a subset of the weak interference regime when the cooperation link is larger than a given threshold. This paper characterizes to within a constant gap the capacity for the symmetric Gaussian CCIC in the regime that was still open. To this end, two novel outer bounds of the types 2Rp + Rcand Rp + 2Rcare derived for the class of injective semideterministic CCICs, where the noises at the different source-destination pairs are independent. These outer bounds, as well as an achievable rate region based on Gelfand-Pinsker binning, superposition coding, and simultaneous decoding at the receivers, are then specialized to the Gaussian noise case. It is shown that the novel outer bounds are necessary to characterize the capacity within a constant gap when the cooperation link is weaker than the direct links, that is, in this regime unilateral cooperation leaves some system resources underutilized.

This paper studies the sum-capacity of the Multiple Input Single Output (MISO) Gaussian broadcast channel where K single-antenna users are served by a base station with N antennas, with N <; K. The generalized Degrees-of-Freedom (gDoF) for this system is derived as the solution of a Maximum Weighted Bipartite Matching (MWBM) problem, where, roughly speaking, each of the N transmit antennas is assigned to a different user. The MWBM problem inspires a user selection algorithm where a subset of N out of K users is served. The proposed algorithm runs in polynomial-time (rather than involving an exhaustive search among all possible subsets of size N out of K users) and extends the classical DoF analysis to more realistic wireless channel configurations where users can experience very different channel gains from the base station. Extensive numerical simulations, run in practically relevant Rayleigh fading environments for different numbers of users and of antennas, show that the throughput achieved by serving the set of N users selected by the MWBM-based algorithm is at most N log(K) bits away from an outer bound to the sum-capacity, where in principle all the K users are served. Comparisons with another widely used user scheduling algorithm are also provided.

This paper presents a practical implementation of a novel three-message transmission strategy for the Gaussian half-duplex relay channel based on Turbo code superposition encoding and interference-aware successive interference cancellation. The impact of finite block-length and discrete input constellations on the Block Error Rate (BLER) performance is evaluated through extensive simulations on an LTE simulation test bench and compared to the theoretical performance of asymptotically large block-length Gaussian codes. For the practically relevant BLER value of 10-2and by varying the direct source-destination link strength, the maximum spectral efficiency gap between theory and the presented implementation is found to be of 0.458 bits/dim when the strength of the source-destination and relay-destination links is the same and of 0.681 bits/dim when the relay-destination link is 5 dB stronger than the source-destination link. These values indicate that practical implementations of high-performing HD relay techniques for future Heterogeneous Network deployments are within reach. A comparison with a baseline strategy without direct source-destination transmission, as currently proposed in the LTE standard for relay scenarios, shows superior performances of the proposed scheme. In particular, the rate gain is of a factor of 2 when the strength of the source-destination and relay-destination links is the same and of a factor of 1.2 when the relay-destination link is 5 dB stronger than the source-destination link, thereby highlighting the critical importance of physical-layer cooperation in broadband wireless systems.

This paper considers a Gaussian network where N half-duplex multiple-antenna relays assist the communication between a source and a destination. A novel antenna switching policy is proposed, where each relays' antenna can be configured to either receive or transmit independently of the others. The rate achieved by noisy network coding is shown to be to within a constant gap from the cut-set bound, where the gap only depends on the total number of antennas in the system. Moreover, the optimal number of different relay antenna configurations needed to attain the constant gap is proved to be at most N + 1, that is, it only depends on the number of relays but not on the total number of antennas. Such a relay scheduling policy is referred to as simple. Through an example, it is shown that independently switching the antennas at the relays not only achieves in general strictly higher rates compared to using the antennas for the same purpose, but can actually provide a strictly larger pre-log factor. This implies that in broadband wireless networks with half-duplex multiple-antenna relays, the relay antennas should be dynamically configured to either transmit of receive depending on the channel conditions.

In ISIT2012 Brahma, Özgür and Fragouli conjectured that in a half-duplex diamond relay network (a Gaussian noise network without a direct source-destination link and with N non-interfering relays) an approximately optimal relay scheduling (achieving the cut-set upper bound to within a constant gap uniformly over all channel gains) exists with at most N + 1 active states (only N + 1 out of the 2Npossible relay listen-transmit configurations have a strictly positive probability). Such relay scheduling policies are said to be simple. In ITW2013 we conjectured that simple relay policies are optimal for any half-duplex Gaussian multi-relay network, that is, simple schedules are not a consequence of the diamond network's sparse topology. In this paper we formally prove the conjecture beyond Gaussian networks. In particular, for any memoryless half-duplex N-relay network for which the cut-set bound is approximately optimal to within a constant gap under some conditions (satisfied for example by Gaussian networks), an optimal schedule exists with at most N + 1 active states. The key step of our proof is to write the minimum of a submodular function by means of its Lovász extension and use the greedy algorithm for submodular polyhedra to highlight structural properties of the optimal solution. This, together with the saddle-point property of min-max problems and the existence of optimal basic feasible solutions in linear programs, proves the claim.

This paper considers the two-user Gaussian Causal Cognitive Interference Channel (GCCIC), which consists of two source-destination pairs that share the same channel and where one full-duplex cognitive source can causally learn the message of the primary source through a noisy link. The GCCIC is an interference channel with unilateral source cooperation that models practical cognitive radio networks. Different achievable strategies are shown to be at most a finite number of bits away from an outer bound for a set of the channel parameters that, roughly speaking, excludes the case of weak interference at both receivers.

This paper studies the two-user interference channel with unilateral source cooperation, which consists of two source-destination pairs that share the same channel and where one full-duplex source can overhear the other source through a noisy in-band link. Novel outer bounds of the type 2R1+ R2and R1+ 2R2are developed for the class of injective semi-deterministic channels with independent noises at the different source-destination pairs. The bounds are then specialized to the Gaussian noise case. Interesting insights are provided about when these types of bounds are active, or in other words, when unilateral cooperation is too weak and leaves some system resources underutilized.

This paper studies the two-user Gaussian interference channel with half-duplex causal cognition. This channel model consists of two source-destination pairs sharing a common wireless channel. One of the sources, referred to as the cognitive, overhears the other source, referred to as the primary, through a noisy link and can therefore assist in sending the primary's data. Due to practical constraints, the cognitive source is assumed to work in half-duplex mode, that is, it cannot simultaneously transmit and receive. This model is more relevant for practical cognitive radio systems than the classical information theoretic cognitive channel model, where the cognitive source is assumed to have a non-causal knowledge of the primary's message. Different network topologies are considered, corresponding to different interference scenarios: (i) the interference-symmetric scenario, where both destinations are in the coverage area of the two sources and hence experience interference, and (ii) the interference-asymmetric scenario, where one destination does not suffer from interference. For each topology the sum-rate performance is studied by first deriving the generalized Degrees of Freedom (gDoF), or "sum-capacity pre-log" in the high-SNR regime, and then showing relatively simple coding schemes that achieve a sum-rate upper bound to within a constant number of bits for any SNR. Finally, the gDoF of the channel is compared to that of the non-cooperative interference channel and to that of the non-causal cognitive channel to identify the parameter regimes where half-duplex causal cognition is useless in practice or attains its ideal ultimate limit, respectively.

This paper considers the two-user Gaussian causal cognitive interference channel (GCCIC), which consists of two source-destination pairs that share the same channel and where one full-duplex cognitive source can causally learn the message of the primary source through a noisy link. The GCCIC is an interference channel with unilateral source cooperation that better models practical cognitive radio networks than the commonly used model which assumes that one source has perfect noncausal knowledge of the other source's message. First, the sum-capacity of the symmetric GCCIC is determined to within a constant gap. Then, the insights gained from the study of the symmetric GCCIC are extended to more general cases. In particular, the whole capacity region of the Gaussian Z-channel, i.e., when there is no interference from the primary user, and of the Gaussian S-channel, i.e., when there is no interference from the secondary user, are both characterized to within 2 bits. The fully connected general, i.e., no-symmetric, GCCIC is also considered and its capacity region is characterized to within 2 bits when, roughly speaking, the interference is not weak at both receivers. The parameter regimes where the GCCIC is equivalent, in terms of generalized degrees-of-freedom, to the noncooperative interference channel (i.e., unilateral causal cooperation is not useful), to the non-causal cognitive interference channel (i.e., causal cooperation attains the ultimate limit of cognitive radio technology), and to bilateral source cooperation are identified. These comparisons shed light into the parameter regimes and network topologies that in practice might provide an unbounded throughput gain compared to currently available (non cognitive) technologies.

This paper considers the Gaussian half-duplex relay channel (G-HD-RC): a channel model where a source transmits a message to a destination with the help of a relay that cannot transmit and receive at the same time. It is shown that the cut-set upper bound on the capacity can be achieved to within a constant gap, regardless of the actual value of the channel parameters, by either partial-decode-and-forward or compress-and-forward. The performance of these coding strategies is evaluated with both random and deterministic switch at the relay. Numerical evaluations show that the actual gap is less than what analytically obtained, and that random switch achieves higher rates than deterministic switch. As a result of this analysis, the generalized degrees-of-freedom of the G-HD-RC is exactly characterized for this channel. In order to get insights into practical schemes for the G-HD-RC that are less complex than partial-decode-and-forward or compress-and-forward, the exact capacity of the linear deterministic approximation (LDA) of the G-HD-RC at high signal-to-noise-ratio is determined. It is shown that random switch and correlated nonuniform inputs bits are optimal for the LDA. It is then demonstrated that deterministic switch is to within one bit from the capacity. This latter scheme is translated into a coding strategy for the original G-HD-RC and its optimality to within a constant gap is proved. The gap attained by this scheme is larger than that of partial-decode-and-forward, thereby pointing to an interesting practical tradeoff between gap to capacity and complexity.

This paper considers a Gaussian relay network where a source transmits a message to a destination with the help of N half-duplex relays. The information theoretic cut-set upper bound to the capacity is shown to be achieved to within 1.96(N+2) bits by noisy network coding, thereby reducing the previously known gap. This gap is obtained as a special case of a more general constant gap result for Gaussian half-duplex multicast networks. It is then shown that the generalized degrees-of-freedom of this network is the solution of a linear program, where the coefficients of the linear inequality constraints are proved to be the solution of several linear programs referred as the assignment problem in graph theory, for which efficient numerical algorithms exist. The optimal schedule, that is, the optimal value of the 2Npossible transmit-receive configuration states for the relays, is investigated and known results for diamond networks are extended to general relay networks. It is shown, for the case of N=2 relays, that only N+1=3 out of the 2N=4 possible states have a strictly positive probability and suffice to characterize the capacity to within a constant gap. Extensive experimental results show that, for a general N -relay network with N≤8 , the optimal schedule has at most N+1 states with a strictly positive probability. As an extension of a conjecture presented for diamond networks, it is conjectured that this result holds for any half-duplex relay network and any number of relays. Finally, a network with N=2 relays is studied in detail to illustrate the channel conditions under which selecting the best relay is not optimal, and to highlight the nature of the rate gain due to multiple relays.

This paper considers the causal cognitive interference channel that consists of two full-duplex transmitter-receiver pairs sharing the same channel, where one transmitter can causally learn the message of the other transmitter through a noisy link. This channel models unilateral source cooperation. The work focuses on the generalized degrees-of-freedom of the symmetric, i.e. the two interfering links and the two direct links have the same strength, sum-capacity for the Gaussian noise channel. It is shown through evaluation of various achievable schemes that known sum-rate upper-bounds are achievable to within a constant gap regardless of the strength of the channel parameters. The achievable schemes are quite simple in the sense that only superposition coding is used, while it is shown that more complex schemes using binning can achieve a smaller gap.

This paper considers the Gaussian relay channel where the relay node operates in half-duplex mode. The exact capacity of the linear deterministic approximation of the Gaussian channel at high SNR is derived first. This result is then used to inspire an achievable scheme valid for any SNR in the original channel. The scheme is quite simple: it uses successive decoding and does not incur in the typical delay of backward decoding. The achievable rate is then showed to be at most 3 bits away from the cut-set upper bound, which allows to analytically determine the generalized Degrees-of-Freedom of the channel. A closed form expression for the gDoF-optimal fraction of time the relay node transmits is found as well.

This paper studies the Gaussian half duplex relay channel, where the relay node can not transmit and receive at the same time. The main contribution lies in showing that both Partial-Decode-Forward and Compress-Forward achieve the CutSet upper bound to within a constant gap regardless of the channel parameters. This provides a closed form characterization of the Generalized Degrees-of-Freedom (gDoF) of the channel, which for certain channel parameters is strictly smaller than the gDoF of the full duplex channel. Half duplex channels can convey information through the random switch between the receive and retransmit phases; this work shows numerically that random switch achieves larger rates compared to deterministic switch, which is usually considered in the literature.

This paper studies the sum-capacity of the Gaussian half-duplex causal cognitive interference channel, a channel model with two transmitter-receiver pairs where a (cognitive) source cooperates with the other (primary) source in sending data through a shared channel. In contrast to the classical cognitive radio model, here the cognitive source can not transmit and receive at the same time and must causally learn the primary message through a noisy channel. Achievable strategies are developed and shown to match known upper bounds on the symmetric sum-capacity of this channel to within a constant gap for all values of channel parameters. In the process, the generalized degrees of freedom of the channel is characterized.

This paper studies a Gaussian relay network, where the relays can either transmit or receive at any given time, but not both. Known upper (cut-set) and lower (noisy network coding) bounds on the capacity of a memoryless full-duplex relay network are specialized to the half-duplex case and shown to be to within a constant gap of one another. For fairly broad range of relay network sizes, the derived gap is smaller than what is known in the literature, and it can be further reduced for more structured networks such as diamond networks. It is shown that the asymptotically optimal duration of the listen and transmit phases for the relays can be obtained by solving a linear program; the coefficients of the linear constraints of this linear program are the solution of certain `assignment problems' for which efficient numerical routines are available; this gives a general interesting connection between the high SNR approximation of the capacity of a MIMO channel and the `assignment problem' in graph theory. Finally, some results available for diamond networks are extended to general networks. For a general relay network with 2 relays, it is proved that, out of the 4 possible listen/transmit states, at most 3 have a strictly positive probability. Numerical results for a network with K - 2 <; 9 relays show that at most K-1 states have a strictly positive probability, which is conjectured to be true for any number of relays.

In this paper a K user multi-input single-output (MISO) interference channel (IFC) is considered where the interference at each receiver is treated as an additional Gaussian noise contribution (Noisy IFC). We address the MISO downlink (DL) beamformer design and power allocation for maximizing the minimum SINR with per base station power constraints and imposing a minimum quality of service (QoS) requirement for each receiver. We study a distributed iterative algorithm for solving the given beamforming problem based on a combination of duality principles and the property that maxmin SINR problem is strictly related to the total power minimization problem. Finally we show that it is possible to characterize the entire Pareto boundary of the SINR (Rate) region for a K-user MISO IFC solving a sequence of maxmin SINR imposing different set of QoS constraints.