Inspired by prior work by Tian and by Cao and Xu, this paper presents an efficient computer-aided framework to characterize the fundamental limits of coded caching systems under the constraint of linear coding. The proposed framework considers non-Shannon-type inequalities which are valid for representable polymatroids (and hence for linear codes), and leverages symmetric structure and problem-specific constraints of coded caching to reduce the complexity of the linear program. The derived converse bounds are tighter compared to previous known analytic methods, and prove the optimality of some achievable memory-load tradeoff points under the constraint of linear coding placement and delivery. These results seem to indicate that small, structured demand subsets combined with minimal common information constructions may be sufficient to characterize optimal tradeoffs under linear coding.

The nonlinear effects from the RF circuits impact the channel capacity in wireless communication systems, particularly in scenarios where the power amplifiers introduce significant distortions in the output signals. In this work, an analysis of the channel capacity is presented by considering a complex-valued scalar nonlinear AWGN model with both peakamplitude and average-power constraints. Unlike prior works that focus on idealized linear models, realistic power amplifier nonlinearities are incorporated in this analysis. By following Smith's approach, the structure of the optimal input distribution is found to have discrete amplitude and independent uniform phase. While the presented analysis is general without relying on specific nonlinear models, we demonstrate the validity of the analysis by evaluating two commonly used power amplifier models - the Saleh model and the third-order polynomial model. We observe that the nonlinearity effectively limits the input peak-amplitude and thus the capacity is bounded at high SNR. This work brings practical constraints into fundamental communication analysis and offers insights into system performance under hardware nonlinearities.

This paper presents a new achievable scheme for the K-user Linear Computation Broadcast Channel (K-LCBC). A K-LCBC comprises data stored on a server and$K$users, each aiming to retrieve a desired linear function of the data by leveraging their prior locally available side information in the form of another linear function of the data. The proposed scheme is based on a subspace decomposition derived from representable polymatroid spaces. This decomposition enables the server to effectively design multicast messages that simultaneously benefit multiple users and allow users to eliminate interference using their available side information. This work extends existing results for the 3-LCBC by introducing a linear programming framework to optimize multicast opportunities across an arbitrary number of users. The proposed approach can be used to derive achievable scheme for the K-user coded caching problem with linear coded placement and scalar linear function retrieval, which was our original motivation to investigate the K-LCBC.

Integrated sensing and communication is regarded as a key enabler for next-generation wireless networks. To optimize the transmitted waveform for both sensing and commu-nication, various performance metrics must be considered. This work focuses on sensing, and specifically on the mean square error (MSE) of channel estimation. Given the complexity of deriving the MSE, the Bayesian Cramer-Rae Bound (BCRB) is commonly recognized as a lower bound on the minimum MSE. However, the BCRB is not applicable to channels with discrete or mixed distributions. To address this limitation, a new lower bound based on a Poincare inequality is proposed and applied to fading MIMO AWGN channels with blockage probability, and the behavior of the lower bound at high SNR is precisely characterized.

Maddah-Ali and Niesen (MAN) showed that coded caching can effectively mitigate peak-time network load by leveraging local caches at the end users. In the MAN model, a server stores multiple files, populates the local caches, and serves single-file requests from cache-aided users via an error-free shared link. The delivered multicast messages in the MAN scheme to serve the users' requests require all users to stay active and expose demand information. To preserve demand privacy and accommodate for offline users, the hotplug caching model with demand privacy against colluding users was introduced and an achievable schemes based on the “privacy keys” idea was proposed at ISIT 2023. This ISIT 2024 paper proposes three new achievable schemes for this model which use Maximum Distance Separable codes coupled with the “virtual users” idea. These new schemes turn out to be exactly optimal under certain conditions, and otherwise optimal to within a constant factor.

Coded caching, introduced by Maddah-Ali and Niesen (MAN), is a model where a server broadcasts multicast packets to users with a local cache that is leveraged so as to reduce the peak network communication load. The original MAN model does not consider missing demands (i.e., some users may not request a file) or privacy issues (i.e., decoding the multicast packets may expose the users’ demands). The former issue was captured by the hotplug model with offline users, where the server starts sending multicast packets after having received a certain number of file requests. The latter issue was addressed by devoting part of the cache to store privacy keys to help users decode their requested file while remaining completely ignorant about the demands of the remaining users. This paper investigates the problem of private demands against colluding users in the hotplug model with offline users. Two achievable schemes are proposed based on Maximum Distance Separable (MDS) codes. They achieve lower subpacketization, and lower load in the small memory regime compared to baseline schemes that trivially include demand privacy or offline users in known schemes.

This paper considers the single antenna, static, scalar Gaussian broadcast channel in the finite blocklength regime. Second order achievable and converse rate regions are presented. Both a global reliability and per-user reliability requirements are considered. The two-user case is analyzed in detail, and generalizations to the$K$-user case are also discussed. The largest second order achievable regions presented here require both superposition and rate splitting in the code construction, as opposed to the (infinite blocklength, first order) capacity region which does not require rate splitting. Indeed, the finite blocklength penalty causes superposition alone to under-perform other coding techniques in some parts of the region. In addition, the proposed scheme uses joint simultaneous decoding as opposed to successive interference cancellation. Interestingly, in the two-user case with per-user reliability requirements, the capacity achieving superposition encoding order (with the codeword intended for the user with the smallest received SNR as cloud center) does not necessarily give the largest second order region. Instead, the message of the user with the smallest point-to-point second order capacity should be encoded in the cloud center in order to obtain the largest second order region for the proposed scheme.

This paper studies the fundamental limits of the shared-link coded caching problem with correlated files, where a server with a library of${\mathsf N}$files communicates with${\mathsf K}$users who can locally cache${\mathsf M}$files. Given an integer${\mathsf r}\in [{\mathsf N}]$, correlation is modelled as follows: each${\mathsf r}$-subset of files contains a unique common block. The tradeoff between the cache size and the average transmitted load over the uniform demand distribution is studied. First, a converse bound under the constraint of uncoded cache placement (i.e., each user directly stores a subset of the library bits) is derived. Then, a caching scheme for the case where every user demands a distinct file (possible for${\mathsf N}\geq {\mathsf K}$) is shown to be optimal under the constraint of uncoded cache placement. This caching scheme is further proved to be decodable and optimal under the constraint of uncoded cache placement when (i)${\mathsf K} {\mathsf r} {\mathsf M}\leq 2 {\mathsf N}$or${\mathsf K} {\mathsf r} {\mathsf M}\geq ({\mathsf K}-1) {\mathsf N}$or${\mathsf r}\in \{1,2, {\mathsf N}-1, {\mathsf N}\}$, and (ii) when the number of distinct demanded files is no larger than four. Finally, a new delivery scheme based on interference alignment which jointly serves the users’ demands is shown to be order optimal to within a factor of 2 under the constraint of uncoded cache placement. As an extension, the above exact and order optimal results can be extended to the worst-case load. As by-products, an extension of the proposed scheme for${\mathsf M}= {\mathsf N}/ {\mathsf K}$is shown to reduce the load of state-of-the-art schemes for the coded caching problem where the users can request multiple files; the proposed scheme for distinct demands can be extended to the coded distributed computing problem with a central server, which achieves the optimal transmission load over the binary field.

We consider the design of practical codes for a symmetric two-user fading Gaussian Broadcast Channel (BC) with feedback. We construct a two-phase coding scheme with the help of deep Neural Networks (NNs) that seeks to optimize the encoder and decoders jointly. Interpreting a communication system as an autoencoder (denoted by AE), we train the AE under various scenarios of noiseless feedback signals. Performance evaluation is presented for Rayleigh distributed channel state, which reveals the existence of a trained NN-based two-phase model that outperforms state-of-the-art codes in the low SNR regime. Considering the availability of feedback signals, we train the AE with different inputs, and observe that feedback consisting of received signals appears to be more beneficial than channel states to boost reliability under the proposed scheme. We provide initial interpretations of the encoding scheme which uses channel state feedback.

Coded caching is a technique that leverages locally cached contents at the users to reduce the network’s peak-time communication load. Coded caching achieves significant performance gains compared to uncoded caching schemes and is thus a promising technique to boost performance in future networks. In the original model introduced by Maddah-Ali and Niesen (MAN), a server stores multiple files and is connected to multiple cache-aided users through an error-free shared link; once the local caches have been filled and all users have sent their demand to the server, the server can start sending coded multicast messages to satisfy all users’ demands. A practical limitation of the original MAN model is that it halts if the server does not receive all users’ demands, which is the limiting case of asynchronous coded caching when the requests of some users arrive with infinite delay. This paper formally defines a coded caching system where some users are offline. Achievable and converse bounds are proposed for this novel setting and shown to meet under certain conditions; otherwise, they are within a constant multiplicative gap of two. Interestingly, when optimality can be be shown, the optimal load-memory tradeoff only depends on the number active users, and not on the total (active plus offline) number of users.

This work investigates a system where each user aims to retrieve a scalar linear function of the files of a library, which are Maximum Distance Separable coded and stored at multiple distributed servers. The system needs to guaranteerobust decodingin the sense that each user must decode its demanded function with signals received from any subset of servers whose cardinality exceeds a threshold. In addition, (a) the content of the library must be kept secure from a wiretapper who obtains all the signals from the servers; (b) any subset of users together can not obtain any information about the demands of the remaining users; and (c) the users’ demands must be kept private against all the servers even if they collude. Achievable schemes are derived by modifying existing Placement Delivery Array (PDA) constructions, originally proposed for single-server single-file retrieval coded caching systems without any privacy or security or robustness constraints. It is shown that the PDAs describing the original Maddah-Ali and Niesen’s coded caching scheme result in a load-memory tradeoff that is optimal to within a constant multiplicative gap, except for the small memory regime when the number of file is smaller than the number of users. As by-products, improved order optimality results are derived for three less restrictive systems in all parameter regimes.

Coded caching is a promising technique to smooth out network traffic by storing part of the library content at the users’ local caches. The seminal work on coded caching for single file retrieval by Maddah-Ali and Niesen (MAN) showed the existence of a global caching gain that scales with the total memory in the system, in addition to the known local caching gain in uncoded systems. This paper formulates a novel cache-aided matrix multiplication retrieval problem, relevant for data analytics and machine learning applications. In the considered problem, each cache-aided user requests the product of two matrices from the library. A structure-agnostic solution is to treat each possible matrix product as an independent file and use the MAN coded caching scheme for single file retrieval. This paper proposes two structure-aware schemes, which partition each matrix in the library by either rows or columns and let a subset of users cache some sub-matrices, that improve on the structure-agnostic scheme. For the case where the library matrices are “fat” matrices, the structure-aware row-partition scheme is shown to be order optimal under some constraint.

In the coded caching problem, as originally formulated by Maddah-Ali and Niesen, a server communicates via a noiseless shared broadcast link to multiple users that have local storage capability. In order for a user to decode its demanded file from the coded multicast transmission, the demands of all the users must be globally known, which may violate the privacy of the users. To overcome this privacy problem, Wan and Caire recently proposed several schemes that attain coded multicasting gain while simultaneously guarantee information theoretic privacy of the users’ demands. In Device-to-Device (D2D) networks, the demand privacy problem is further exacerbated by the fact that each user is also a transmitter, which appears to be needing the knowledge of the files demanded by the remaining users in order to form its coded multicast transmission. This paper shows how to solve this seemingly infeasible problem. The main contribution of this paper is the development of new achievable and converse bounds for D2D coded caching that are to within a constant factor of one another when privacy of the users’ demands must be guaranteed even in the presence of colluding users (i.e., when some users share cached contents and demanded file indices). First, a D2D private caching scheme is proposed, whose key feature is the addition of virtual users in the system in order to “hide” the demands of the real users. By comparing the achievable D2D private load with an existing converse bound for the shared-link model without demand privacy constraint, the proposed scheme is shown to be order optimal, except for the very low memory size regime with more files than users. Second, in order to shed light into the open parameter regime, a new achievable scheme and a new converse bound under the constraint of uncoded cache placement (i.e., when each user stores directly a subset of the bits of the library) are developed for the case of two users, and shown to be to within a constant factor of one another for all system parameters. Finally, the two-user converse bound is extended to any number of users by a cut-set type argument. With this new converse bound, the virtual users scheme is shown to be order optimal in all parameter regimes under the constraint of uncoded cache placement and user collusion.

Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the users’ local caches. For the shared-link network with end-user-caches, Maddah-Ali and Niesen proposed a two-phase coded caching strategy. In practice, users may communicate with the server through intermediate relays. This paper studies the tradeoff between the memory size M and the network load R for the networks where a server with N files is connected to H relays (without caches), which in turn are connected to K users equipped with caches of M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, converse bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly pushed into the user caches without any coding. In this case, once the cache contents and the users’ demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well-known “acyclic index coding converse bound” results in converse bounds that are not tight for combination networks with end-user-caches. A novel converse bound that leverages the network topology is proposed, which is the tightest converse bound known to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived. Several novel caching schemes are proposed, based on the Maddah-Ali and Niesen cache placement. These schemes leverage the structure of the combination network or/and perform interference elimination at the end-users. The proposed schemes are proved: (i) to be (order) optimal for some (N, M, H, r) parameters regimes under the constraint of uncoded cache placement, and (ii) to outperform the state-of-the-art schemes in numerical evaluations.

Recent push for low-latency and high-reliability systems requires derivation of fundamental trade-offs between reliability and rates in multi-user systems with hard deadlines and reliability constraints. Towards this goal, this paper provides a second-order analysis of superposition coding and other orthogonal access schemes for the two-user static Gaussian broadcast channel. Numerical evaluations show that, since reliability and rates are intertwined when a hard-deadline is imposed, the scheduling of resources among users, including the level of reliability for each user, must be done jointly at the physical layer in order to optimize the overall system performance.

This paper investigates the ultimate performance limits of distributed multi-server systems with cache-aided users, where the users aim to retrieve a linear function of the files of a library that are replicated at multiple non-colluding servers. In addition to correct decoding, the following conditions are imposed: (a) the content of the library must be kept secure from a wiretapper who obtains all the signals sent by the servers; (b) any subset of users together can not obtain any information about the demands of the remaining users; and (c) the users’ demands must be kept private against any individual server. A Distributed Key Superposition (DKS) scheme is proposed, which uses the idea of superposition of security and privacy keys to guarantee conditions (a) and (b) simultaneously, as in the single server setup. Condition (c) is guaranteed by the fact that each server is responsible for delivering a fraction of the requested linear function, and insuring that the privacy keys used by a server are generated and pushed to the user caches by another server. Interestingly, the achievable load-memory tradeoff with the additional constraint (c) is the same as the single server case if there are at least two servers.

This paper proposes a linear coding scheme for the two-user fading additive white Gaussian noise broadcast channel, under the assumptions that: (i) perfect Channel State Information (CSI) is available at the receivers; and (ii) unit delayed CSI along with channel output feedback (COF) is available at the transmitter. The proposed scheme is derived from a control-theoretic perspective that generalizes the communication scheme for the point-to-point (P2P) fading Gaussian channel under the same assumptions by Liu et al. [1]. The proposed scheme asymptotically achieves the rates of a posterior matching scheme, from the same authors, for a certain choice of parameters.

Coded caching aims to minimize the network's peak-time communication load by leveraging the information pre-stored in the users' local cache. The original single file retrieval setting by Maddah-Ali and Niesen has been recently extended to general Scalar Linear Function Retrieval (SLFR) by Wan et al., who proposed a linear scheme that surprisingly achieves the same optimal load (under the constraint of uncoded cache placement) as in single file retrieval. This paper's goal is to characterize the conditions under which a general SLFR linear scheme is optimal and gain practical insights into why the specific choices made by Wan et al. work. This paper shows that the optimal decoding coefficients are necessarily the product of two terms, one only involving the encoding coefficients and the other only the demands. In addition, the relationships among the encoding coefficients are shown to be captured by the cycles of a certain graph. Thus, a general linear scheme for SLFR can be found by solving a spanning tree problem.

This paper formulates the shared-link cache-aided matrix multiplication retrieval problem. Matrix multiplication is an essential building block for distributed computing applications. Different from the original coded caching single file retrieval model, in the considered problem each cache-aided user requests the product of two matrices from a library that contains N matrices. A trivial solution, agnostic to the structure of matrix multiplication, is to treat each of the N2possible matrix products as a file in the original single file retrieval coded caching problem. Such a solution can be improved by leveraging the correlation among the entries in the matrix product. In this paper, two structure-aware schemes are proposed, which partition each library matrix either by rows or by columns, and let a subset of users cache some sub-matrices; in the delivery, coded multicast messages are created to leverage the cached content and the correlation among the entries in the requested matrix products. These schemes outperform two baseline schemes, where one sends packets without coding and the other lets each user directly recover the two input matrices. Order optimality results are derived in some parameter regimes.

This paper investigates the ultimate performance limits of Linear Function Retrieval (LFR) by cache-aided users from distributed coded servers. Each user aims to retrieve a linear function of the files of a library, which are Maximum Distance Separable (MDS) coded and stored at multiple servers. The system needs to guarantee robust decoding in the sense that each user must decode its demanded function with signals from any subset of servers whose cardinality exceeds a threshold. In addition, the following conditions must be met: (a) the content of the library must be kept secure from a wiretapper who obtains all the signals sent by the servers; (b) any subset of users together can not obtain any information about the demands of the remaining users; and (c) the users' demands must be kept private against all the servers even if they collude. A scheme that uses the superposition of security and privacy keys is proposed to meet all those conditions. The achieved load-memory tradeoff is the same as that achieved in single-server case scaled by the inverse of the MDS code rate used to encode the files, and the same optimality guarantees as in single-server setup are obtained.

This work investigates the problem of cache-aided content Secure and demand Private Linear Function Retrieval (SP-LFR), where three constraints are imposed on the system: (a) each user is interested in retrieving an arbitrary linear combination of the files in the server’s library; (b) the content of the library must be kept secure from a wiretapper who obtains the signal sent by the server; and (c) no subset of colluding users together can obtain information about the demands of the remaining users. A procedure is proposed to derive an SP-LFR scheme from a given Placement Delivery Array (PDA), which is known to give coded caching schemes with low subpacketization for systems with neither security nor privacy constraints. This procedure uses the superposition of security keys and privacy keys, in both the cache placement and transmitted signal, to guarantee content security and demand privacy, respectively. In particular, among all PDA-based SP-LFR schemes, the memory-load pairs achieved by the PDA describing the Maddah-Ali and Niesen’s scheme are Pareto optimal and have the lowest subpacketization. Moreover, the achieved load-memory tradeoff is optimal to within a constant multiplicative gap, except for the small memory regime (i.e., when the cache size is between 1 and 2) and the number of files is smaller than the number of users. Remarkably, the memory-load tradeoff does not worsen compared to the best known schemes that guarantee either only content security in all regimes or only demand privacy in the regime mentioned above.

Coded caching has the potential to greatly reduce network traffic by leveraging the cheap and abundant storage available in end-user devices so as to create multicast opportunities in the delivery phase. In the seminal work by Maddah-Ali and Niesen (MAN), the shared-link coded caching problem was formulated, where each user demands one file (i.e., single file retrieval). This article generalizes the MAN caching problem formulation from single file retrieval on the binary filed to general scalar linear function retrieval on an arbitrary finite field. The proposed novel scheme is linear, based on MAN uncoded cache placement, and leverages ideas from interference alignment. Quite surprisingly, the worst-case load of the proposed scheme among all possible demands is the same as the one of the scheme by Yu, Maddah-Ali, and Avestimehr (YMA) for single file retrieval. The proposed scheme has thus the same optimality guarantees as YMA, namely, it is optimal under the constraint of uncoded cache placement, and is optimal to within a factor 2 otherwise. Some extensions of the proposed scheme are then discussed. It is shown that the proposed scheme works not only on arbitrary finite field, but also on any commutative ring. The key idea of this article can be also extended to all scenarios to which the original MAN scheme has been extended, including but not limited to demand-private retrieval and Device-to-Device networks.

Maddah-Ali and Niesen (MAN) in 2014 showed that coded caching in single bottleneck-link broadcast networks allows serving an arbitrarily large number of cache-equipped users with a total link load (bits per unit time) that does not scale with the number of users. Since then, the general topic of coded caching has generated enormous interest both from the information theoretic and (network) coding theoretic viewpoint, and from the viewpoint of applications. Building on the MAN work, this paper considers a particular network topology referred to as cache-aided Fog Radio Access Network (Fog-RAN), that includes a Macro-cell Base Station (MBS) co-located with the content server, several cache-equipped Small-cell Base Stations (SBSs), and many users without caches. Some users are served directly by the MBS broadcast downlink, while other users are served by the SBSs. The SBSs can also exchange data via rounds of direct communication via a side channel, referred to as “sidelink”. For this novel Fog-RAN model, the fundamental tradeoff among (a) the amount of cache memory at the SBSs, (b) the load on the downlink (from MBS to directly served users and SBSs), and (c) the aggregate load on the sidelink is studied, under the standard worst-case demand scenario. We propose a converse bound whose key novelty is to jointly bound the downlink load an the sidelink load. For the achievability, by leveraging the network topology, we propose two classes of memory-loads point, where the SBS sidelink load is minimum and the MBS downlink load is minimum, respectively. By memory-sharing between these two classes of memory-loads points, some exact or order optimality results are obtained. Several existing models (e.g., Device-to-Device coded caching, single bottleneck-link coded caching with shared caches, single bottleneck-link caching coded caching with cache-less users) are recovered as special cases of this network model and by-product results of independent interest are given. Finally, the role of topology-aware versus topology-agnostic caching is discussed.

In order to preserve the privacy of the users demands from other users, in this paper we formulate a novel information theoretic Device-to-Device (D2D) private caching model by adding a trusted server. In the delivery phase, the trusted server collects the users demands and sends a query to each user, who then broadcasts packets according to this query. Two D2D private caching schemes (uncoded and coded) are proposed in this paper, which are shown to be order optimal.

This paper studies a variant of the Pliable Index CODing (PICOD) problem, i.e., an index coding problem where a user can be satisfied by decoding any message that is not in its side information set, where communication is decentralized, i.e., it occurs among users rather than by the central server, and secure, i.e., each user is allowed to decode only one message outside its side information set and must not be able to collect any information about any other message that is not its decoded one. Given the difficulty of the general version of this problem, this paper focuses on the case where the side information sets are `s circular shifts', namely, user u's side information set is the set of messages indexed by {u, u +1,...,u + s - 1} for some fixed s and where the indices are intended modulo the cardinality of the message set. This particular setting has been studied in the `decentralized non-secure' and in the `centralized secure' settings, thus allows one to quantify the cost of decentralized communication under security constraints on the number of transmissions. Interestingly, the decentralized vs the centralized secure setting incurs a multiplicative gap of approximately three. This is in contrast to the cases without security constraint, where the multiplicative gap is known to be at most two.

The fading broadcast channel (BC) with additive white Gaussian noise (AWGN) channel, channel output feedback (COF) and channel state information (CSI) is considered. Perfect CSI is available at the receivers, and unit delayed CSI along with COF at the transmitter. Under the assumption of memoryless fading, a posterior matching scheme that incorporates the additional CSI feedback into the coding scheme is presented. With COF, the achievable rates depend on the joint distribution of the fading process. Numerical examples show that the capacity region of two-user fading AWGN-BC is enlarged by COF. The coding scheme is however suboptimal since some parts of the achievable rate region are outperformed by superposition coding without COF.

This paper considers cache-aided device-to-device (D2D) networks where a trusted server helps to preserve the privacy of the users' demands. Specifically, the trusted server collects the users' demands before the delivery phase and sends a query to each user, who then broadcasts multicast packets according to this query. Recently the Authors proposed a D2D private caching scheme that was shown to be order optimal except for the very low memory size regime, where the optimality was proved by comparing to a converse bound without privacy constraint. The main contribution of this paper is a novel converse bound for the studied model where users may collude (i.e., some users share cache contents and demanded files, and yet cannot infer what files the remaining users have demanded) and under the placement phase is uncoded. To the best of the Author's knowledge, such a general bound is the first that genuinely accounts for the demand privacy constraint. The novel converse bound not only allows to show that the known achievable scheme is order optimal in all cache size regimes (while the existing converse bounds cannot show it), but also has the potential to be used in other variants of demand private caching.

In the shared-link coded caching problem, formulated by Maddah-Ali and Niesen (MAN), each cache-aided user demands one file (i.e., single file retrieval). This paper generalizes the MAN problem so as to allow users to request scalar linear functions (aka, linear combinations with scalar coefficients) of the files. We propose a novel coded delivery scheme, based on MAN uncoded cache placement, that allows for the decoding of arbitrary scalar linear functions of the files on arbitrary finite fields. Surprisingly, it is shown that the load for cache-aided scalar linear function retrieval depends on the number of linearly independent functions that are demanded, akin to the cache-aided single-file retrieval problem where the load depends on the number of distinct file requests. The proposed scheme is proved to be optimal under the constraint of uncoded cache placement, in terms of worst-case load, and within a factor 2 otherwise.

This paper studies the secure decentralized Pliable Index CODing (PICOD) problem, where the security constraint forbids users to decode more than one message while the decentralized setting imposes that there is no central transmitter in the system, and thus transmissions occur only among users. A converse bound from the Authors' previous work showed a factor of three difference in optimal code-length between the centralized and the decentralized versions of the problem, under the constraint of linear encoding. This paper first lists all linearly infeasible cases, that is, problems where no linear code can simultaneously achieve both correctness/decodability and security. Then, it proposes linear coding schemes for the remaining cases and shows that their code-length is to within an additive constant gap from the converse bound.

A coded caching scheme, referred to as key superposition, is proposed in the cache-aided content Secure and demand Private Linear Function Retrieval (SP-LFR) setup, where the following conditions are imposed: (a) each user is interested in retrieving an arbitrary linear combination of the files in the server’s library; (b) the content of the library must be kept secure from a wiretapper who obtains the signal sent by the server; and (c) any subset of users together can not obtain any information about the demands of the remaining users. The scheme uses the superposition of security keys and privacy keys in both the placement and delivery phases to guarantee content security and demand privacy, respectively. The achieved load-memory tradeoff is optimal to within a constant multiplicative gap, except for the small memory regime when there are less file than users. The memory-load tradeoff does not increase compared to the best known schemes that only guarantee content security in all regimes or only demand privacy in some regime.

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.

This paper studies the Pliable Index CODing problem (PICOD), which models content-type distribution networks. In the PICOD(t) problem there are m messages, n users and each user has a distinct message side information set, as in the classical Index Coding problem (IC). Differently from IC, where each user has a pre-specified set of messages to decode, in the PICOD(t) a user is “pliable” and is satisfied if it can decode any t messages that are not in its side information set. The goal is to find a code with the shortest length that satisfies all the users. This flexibility in determining the desired message sets makes the PICOD(t) behave quite differently compared to the IC, and its analysis even more challenging. This paper mainly focuses on the complete-S PICOD(t) with m messages, where the set S ⊂ [m] contains the sizes of the side information sets, and the number of users is n = ΣsϵS(m/s), with no two users having the same side information set. Capacity results are shown for: (i) the consecutive complete-S PICOD(t), where S = [smin: smax] for some 0 ≤ smin≤ smax≤ m-t, and (ii) the complement-consecutive complete-S PICOD(t), where S = [0 : m - t]\[smin: smax], for some 0min≤ smax<; m - t. The novel converse proof is inspired by combinatorial design techniques and the key insight is to consider all messages that a user can eventually decode successfully, even those in excess of the t required ones. This allows one to circumvent the need to consider all possible desired message set assignments at the users in order to find the one that leads to the shortest code length. The core of the novel proof is to solve the critical complete-S PICOD(t) with m = 2s + t messages and S = {s}, by showing the existence of a user who can decode s + t messages regardless of the desired message set assignment. All other tight converse results for the complete-S PICOD(t) can be deduced from this critical case. The converse results show the information theoretic optimality of simple linear coding schemes. By similar reasoning, all complete-S PICOD(t) where the number of messages is m ≤ 5 can be fully characterized. In addition, tight converse results are also shown for the PICOD(1) with circulararc network topology hypergraph.

Data shuffling of training data among different computing nodes (workers) has been identified as a core element to improve the statistical performance of modern large-scale machine learning algorithms. Data shuffling is often considered as one of the most significant bottlenecks in such systems due to the heavy communication load. Under a master-worker architecture (where a master has access to the entire dataset and only communication between the master and the workers is allowed) coding has been recently proved to considerably reduce the communication load. This work considers a different communication paradigm referred to as decentralized data shuffling, where workers are allowed to communicate with one another via a shared link. The decentralized data shuffling problem has two phases: workers communicate with each other during the data shuffling phase, and then workers update their stored content during the storage phase. The main challenge is to derive novel converse bounds and achievable schemes for decentralized data shuffling by considering the asymmetry of the workers' storages (i.e., workers are constrained to store different files in their storages based on the problem setting), in order to characterize the fundamental limits of this problem. For the case of uncoded storage (i.e., each worker directly stores a subset of bits of the dataset), this paper proposes converse and achievable bounds (based on distributed interference alignment and distributed clique-covering strategies) that are within a factor of 3/2 of one another. The proposed schemes are also exactly optimal under the constraint of uncoded storage for either large storage size or at most four workers in the system.

Caching is an efficient way to reduce network traffic congestion during peak hours, by storing some content at the user's local cache memory, even without knowledge of user's later demands. Maddah-Ali and Niesen proposed a two-phase (placement phase and delivery phase) coded caching strategy for broadcast channels with cache-aided users. This paper investigates the same model under the constraint that content is placed uncoded within the caches, that is, when bits of the files are simply copied within the caches. When the cache contents are uncoded and the users' demands are revealed, the caching problem can be connected to an index coding problem. This paper focuses on deriving fundamental performance limits for the caching problem by using tools for the index coding problem that were either known or are newly developed in this work. First, a converse bound for the caching problem under the constraint of uncoded cache placement is proposed based on the “acyclic index coding converse bound.” This converse bound is proved to be achievable by the Maddah-Ali and Niesen's scheme when the number of files is not less than the number of users, and by a newly derived index coding achievable scheme otherwise. The proposed index coding achievable scheme is based on distributed source coding and strictly improves on the widely used “composite (index) coding” achievable bound and its improvements, and is of independent interest. An important consequence of the findings of this paper is that advancements on the coded caching problem posed by Maddah-Ali and Niesen are thus only possible by considering strategies with coded placement phase. A recent work by Yu et al has however shown that coded cache placement can at most half the network load compared to the results presented in this paper.

In this paper the capacity region of the Layered Packet Erasure Broadcast Channel (LPE-BC) with Channel Output Feedback (COF) available at the transmitter is investigated. The LPE-BC is a high-SNR approximation of the fading Gaussian BC recently proposed by Tse and Yates, who characterized the capacity region for any number of users and any number of layers when there is no COF. This paper derives capacity inner and outer bounds for the LPE-BC with COF for the case of two users and any number of layers. The inner bounds generalize past results for the two-user erasure BC, which is a special case of the LPE-BC with COF with only one layer. The novelty lies in the use of inter-user & inter-layer network coding retransmissions (for those packets that have only been received by the unintended user), where each random linear combination may involve packets intended for any user originally sent on any of the layers. Analytical and numerical examples show that the proposed outer bound is optimal for some LPE-BCs.

This paper introduces the decentralized Pliable Index CODing (PICOD) problem: a variant of the Index Coding (IC) problem, where a central transmitter serves pliable users with message side information; here, pliable refers to the fact that a user is satisfied by decoding any t messages that are not in its side information set. In the decentralized PICOD, a central transmitter with knowledge of all messages is not present, and instead users share among themselves massages that can only depend on their local side information set. This paper characterizes the capacity of two classes of decentralized complete-S PICOD(t) problems with m messages (where the set S ⊂ [m] contains the sizes of the side information sets, and the number of users is n = Σs∈Sm/s, with no two users having the same side information set): (i) the consecutive case S = [smin: smax] for some 0 ≤ smin≤ smax≤ m -t, and (ii) the complement-consecutive case S = [0 : m-t]\ [smin: smax], for some 0min≤ smax≤ m - t. Interestingly, the optimal code-length for the decentralized PICOD in those cases is the same as for the classical (centralized) PICOD counterpart, except when the problem is no longer pliable, that is, it reduces to an IC problem where every user needs to decode all messages not in its side information set. Although the optimal code-length may be the same in both centralized and decentralized settings, the actual optimal codes are not. For the decentralized PICOD, sparse Maximum Distance Separable (MDS) codes and vector linear index codes are used (as opposed to scalar linear codes).

This paper studies the fundamental limits of the shared-link caching problem with correlated files, where a server with a library of N files communicates with K users who can store M files. Given an integer r G ∈ [N], correlation is modelled as follows: each r-subset of files contains one and one only common block. The tradeoff between the cache size and the average transmitted load is considered. First, a converse bound under the constraint of uncoded cache placement (i.e., each user directly caches a subset of the library bits) is derived. Then, an interference alignment scheme is proposed. The proposed scheme achieves the optimal average load under uncoded cache placement to within a factor of 2 in general, and it is exactly optimal for (i) users demand distinct files, (ii) large or small cache size, namely KrM/N ≤ 2 or KrM/N ≥ K - 1, and (iii) large or small correlation, namely r ∈{1, 2, N - 1, N}. As a by-product, the proposed scheme reduces the (worst-case or average) load of existing schemes for the caching problem with multi-requests.

This paper considers a novel cache-aided Fog Radio Access Network (Fog-RAN) architecture including a Macro-cell Base Station (MBS), several Small-cell Base Stations (SBSs), and users. Some users, not in the reach of any SBS, are directly served by the MBS, while the other users are "offloaded" and receive information only from the SBSs through high throughput links. In order to alleviate the load in the wireless front-haul links between the MBS and the SBSs, caching is employed at the SBSs. The MBS sends coded packets to the SBSs and to the directly served users via wireless multicast transmission on a common downlink channel, modeled as an error-free shared link of fixed capacity. Subsequently, the SBSs communicate among one another in a Device-to-Device (D2D) fashion so as each SBS obtains enough information to decode the files demanded by its connected users. The access links between SBSs and users are assumed to operate at a sufficiently high rate such that they are not the system bottleneck. For this novel Fog-RAN model, the memory-loads tradeoff for the worst-case demands is investigated. The main contributions of this paper are: (i) a novel symmetric inter-file coded cache placement scheme, (ii) a novel D2D delivery scheme to handle the inter-SBS communication phase, that is order optimal when each SBS serves the same number of users, and (iii) a novel asymmetric cache placement with file subpacketization dependent on the network structure, which is exactly optimal in some memory size regimes.

This paper considers the problem of code design for a channel where communications and radar systems coexist, modeled as having both Additive White Gaussian Noise (AWGN) and Additive Radar Interference (ARI). The issue of how to adapt or re-design convolutional codes (decoded by the Viterbi algorithm) and LDPC codes (decoded by the sum-product algorithm and optimized by using the EXIT chart method) to effectively handle the overall non-Gaussian ARI noise is investigated. A decoding metric is derived from the non-Gaussian ARI channel transition probability as a function of the Signal-to-Noise Ratio (SNR) and Interference-to-Noise Ratio (INR). Two design methodologies are benchmarked against a baseline "unaltered legacy system", where a code designed for AWGN-only noise, but used on the non-Gaussian ARI channel, is decoded by using the AWGN-only metric (i.e., as if INR is zero). The methodologies are: M1) codes designed for AWGN-only noise, but decoded with the new metric that accounts for both SNR and INR; and M2) codes optimized for the overall non-Gaussian ARI channel. Both methodologies give better average Bit Error Rate (BER) in the high INR regime compared to the baseline. In the low INR regime, both methodologies perform as the baseline since in this case the radar interference is weak. Interestingly, the performance improvement of M2 over M1 is minimal. In practice, this implies that specifications in terms of channel error correcting codes for commercially available wireless systems need not be changed, and that it suffices to use an appropriate INR-based decoding metric in order to effectively cope with the ARI.

This paper studies the Layered Packet Erasure Broadcast Channel (LPE-BC) with Channel Output Feedback (COF), which is a high-SNR approximation of the fading Gaussian BC, proposed by Tse and Yates in 2012 for the case without COF. This model is also a multi-layer generalization of the Binary Erasure Channel (BEC). In a past work, the Authors derived inner and outer bounds to the rate region (set of achievable rates with backlogged arrivals) of the LPE-BC with COF; here, the arrival region (set of exogenous arrival rates for which packet arrival queues are stable) for the same model is analyzed. For the case of K=2 users and Q ≥ 1 layers, the known achievable rate region and the derived arrival region coincide; both strategically employ a. For the case of Q = 2 layers, sufficient conditions are given for the achievable arrival region to coincide with the known converse rate region, thus showing that in those cases the optimal rate and arrival regions coincide.

The Pliable Index CODing (PICOD) problem is a variant of the Index Coding (IC) problem, where the desired messages by the users, who are equipped with message side information, are part of the optimization. This paper studies the PICOD problem where users are subject to a privacy constraint. In particular, the following special class of private PICODs is investigated: 1) the side information structure is circular, and 2) each user can decode one and only one message. The first condition is a special case of the “circular-arc network topology hypergraph” class of PICOD studied in [6], for which an optimal solution was given without the privacy constraint. The second condition was first studied in [9] and was motivated by the need to keep content private in some distribution networks. This paper proposes both converse and achievable bounds. The proposed achievable scheme not only strictly outperforms the existing one for some values of the system parameters, but it is also information theoretically optimal in some settings. For the remaining cases, the proposed linear code is shown to require at most one more transmission than the best possible linear code.

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, motivated by mission-critical and latency-constrained traffic, focuses on delivering different messages to various end-users within hard deadlines on the downlink of a wireless system. A novel deadline outage performance criterion is introduced, which accounts for both the violation of the hard deadline by any of the messages as well as for channel decoding errors due to finite block-length. This formulation allows for the study of scheduling policies under a more refined model of the physical layer channel than is usually assumed in the networking literature. Different scheduling polices under hard deadline constraints are proposed, and the corresponding deadline outage probabilities evaluated. The main result is that, to reduce the deadline outage probability, a scheduling policy should cleverly combine time-sharing and concatenate-and- code.

Maddah-Ali and Niesen's original coded caching scheme for shared-link broadcast networks is now known to be optimal to within a factor two, and has been applied to other types of networks. For practical reasons, this paper considers that a server communicates to cache-aided users through H intermediate relays. In particular, it focuses on combination networks where each of the K = (rH) users is connected to a r distinct r-subsets of relays. By leveraging the symmetric topology of the network, this paper proposes a novel method to generate multicast messages such that each multicast message sent to each relay is useful for the largest possible subset of users connected to this relay. By numerical evaluations, the proposed scheme is shown to reduce the download time compared to the schemes available in the literature. The idea is then extended to decentralized combination networks, more general relay networks, and combination networks with cache-aided relays and users. Also in these cases the proposed scheme outperforms known ones.

Finding the underlying probability distributions of a set of observed sequences under the constraint that each sequence is generated i.i.d by a distinct distribution is considered. The number of distributions, and hence the number of observed sequences, are let to grow with the observation blocklength n. Asymptotically matching upper and lower bounds on the probability of error are derived.

This paper investigates the fundamental tradeoff between cache size and download time in the (H, r, M, N) combination network, where a server with N files is connected to H relays (without caches) and each of the K: = Hr users (with caches of size M files) is connected to a different subset of r relays. Existing schemes fall within two categories: either use the uncoded symmetric cache placement originally proposed for the shared-link model and design delivery phase dependent on the network topology, or effectively divide the combination network into H uncoordinated shared-link networks each serving K':= H-1r-1 users; in either case, the placement phase leverages effectively the connectivity of relay s/users. In this paper, a novel strategy is proposed where the coded cache placement is dependent on network topology. The proposed scheme is shown to be information theoretically optimal for large cache size. In addition, when not exactly optimal, the proposed scheme can also outperform existing schemes.

Pliable Index CODing (PICOD) is a variant of the Index Coding (IC) problem in which a user is satisfied whenever it can successfully decode any one message that is not in its side information set, as opposed to a fixed pre-determined message. has n = Σ The complete-S PICOD with m messages, for S ⊆ [0 : m - 1], has n = Σs∈S(sm) users with distinct side information sets. Past work on PICOD provided tight converse results when either the sender is constrained to use linear codes, or for some special classes of complete-S PICOD. This paper provides a tight information theoretic converse result (i.e., no restriction to linear codes) for the so-called “consecutive complete-S” PICOD, where the set S satisfies S = [smin: smax] for some 0 ≤ smin ≤ smax ≤ m - 1. This result extends existing converse results and shows that linear codes have the smallest possible code lenght given by min (m - smin, 1 + smax). The central contribution is a novel proof technique rooted in combinatorics. The main idea is to consider all the messages a user can eventually successfully decode, in addition to its own desired message. This allows us to circumvent the necessity of essentially considering all possible assignments of desired messages for the users. The keystone of the proof is to show that, for the case of S = {s} and m = 2s + 1, there exists at least one user who can decode s + 1 messages. From this, the extension to the “consecutive complete-S” PICOD follows.

Increasing demands for spectrum have necessitated the coexistence of communications and radar systems within the same band. This paper investigates how an unaltered radar system affects the performance of a communications receiver. For a single-carrier communications system, it is shown that a low power radar signal can be treated as Gaussian noise while a strong radar signal can be subtracted off the received signal, but in doing so one of the two signal dimensions is lost. Complex-valued constellation design problems are next proposed, with the goal of either minimizing the error rate under a power constraint, or maximizing the transmission rate under both error rate and power constraints. Numerically, the designed constellation is shaped as a concentric hexagon for weak radar interference while it morphs into an uneven pulse amplitude modulation for strong interference. A multi-carrier orthogonal frequency division multiplexing communications system is lastly considered. Due to the radar interference, the received signal becomes correlated over time and across carriers. To reduce the complexity of the optimal receiver, several suboptimal decoders are analyzed, among which the one that discards the correlations between subcarriers is numerically found to perform close to the optimal one.

This paper investigates the capacity of a communications channel that, in addition to additive white Gaussian noise, also suffers from interference caused by a co-existing radar transmission. The radar interference (of short duty-cycle and of much wider bandwidth than the intended communication signal) is modeled as an additive term whose amplitude is known and constant, but whose phase is independent and identically uniformly distributed at each channel use. The capacity achieving input distribution, under the standard average power constraint, is shown to have independent modulo and phase. The phase is uniformly distributed in [0, 2π]. The modulo is discrete with countably infinite many mass points, but only finitely many in any bounded interval. From numerical evaluations, a proper-complex Gaussian input is seen to perform quite well for weak radar interference. We also show that for very large radar interference, and for signal to noise ratio equal to S, the capacity is equal to (1/2) log(1+S) and a proper-complex Gaussian input achieves it. It is concluded that the presence of the radar interference results in a loss of half of the degrees of freedom compared with an AWGN channel without radar interference.

This paper considers a Gaussian channel with one transmitter and two receivers. The goal is to maximize the communication rate at the intended/primary receiver subject to a disturbance constraint at the unintended/secondary receiver. The disturbance is measured in terms of the minimum mean square error (MMSE) of the interference that the transmission to the primary receiver inflicts on the secondary receiver. This paper presents a new upper bound for the problem of maximizing the mutual information subject to an MMSE constraint. The new bound holds for vector inputs of any length and recovers a previously known limiting (when the length of the vector input tends to infinity) expression from the work of Bustin et al. The key technical novelty is a new upper bound on the MMSE. This bound allows one to bound the MMSE for all signal-to-noise ratio (SNR) values below a certain SNR at which the MMSE is known (which corresponds to the disturbance constraint). The bound also complements the “single-crossing point property” of the MMSE that upper bounds the MMSE for all SNR values above a certain value at which the MMSE value is known. The MMSE upper bound provides a refined characterization of the phase-transition phenomenon, which manifests, in the limit as the length of the vector input goes to infinity, as a discontinuity of the MMSE for the problem at hand. For vector inputs of size n = 1, a matching lower bound, to within an additive gap of order O(log log(1/MMSE)) (where MMSE is the disturbance constraint), is shown by means of the mixed inputs technique recently introduced by Dytso et al.

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.

This paper provides information theoretic converse proofs for some classes of Pliable Index CODing (PICOD) problems. PICOD is a variant of the index coding problem in which a user is satisfied whenever it can successfully decode any one message that is not in its side information set. Past work on PICOD provided a number of achievable schemes based on linear codes, some of which are known to be optimal when the server is restricted to use linear codes only. This paper proves that for some of those cases linear codes are indeed optimal in an information theoretic sense, i.e., they cannot be beaten by non-linear codes. It also shows the information theoretic optimality for other classes of PICOD problems that were open.

The slotted strongly asynchronous channel with a bursty user consists of a window of An= enαblocks of length n channel uses. A user transmits a randomly selected message among Mn= enRdifferent ones in exactly Kn= envrandomly selected but distinct blocks in the window. The receiver must locate and decode, with vanishing error probability in n, each one of the transmitted messages. The optimal tradeoff between (R, α, ν) is derived.

This paper studies the tradeoff between the memory size M and the download time / rate R* for networks where a server with N files is connected to H relays (without caches), which in turns are connected to K users equipped with caches of size M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, outer bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly copied in the user caches without any coding. In this case, once the cache contents and the user demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well known “acyclic index coding outer bound” results in bounds that are not tight for combination networks with enduser-caches (as opposed to the case without relays) and provides two novel ways to derive the tightest known outer bounds to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived.

This paper studies inner and outer bounds on the degrees of freedom (DoF) region of the multi-antenna two-user Gaussian interference channel with an instantaneous relay (IR) or relay without delay. It is assumed that the two transmitters and the two receivers have M antennas, while the IR receives through Nr antennas and transmits through Nt antennas. In the proposed achievable scheme, which generalizes a known one for the case M = Nr= Ntto any (M, Nr, Nt), the IR performs memoryless linear operations on its received signal so as to neutralize interference at the receivers, and the beamforming matrices used by the IR and the transmitters are jointly designed. This joint design strictly outperforms known achievable schemes. Two outer bounds are derived. An information theoretic outer bound is obtained by giving the receivers or the IR genie side information, so that the DoF region of the resulting enhanced channel is known; this converse is valid for any type of processing at the IR and shows the optimality of the proposed achievable scheme for some (M, Nr, Nt). A linear processing outer bound is obtained when the IR is restricted to performs linear operations, without any memoryless restriction, on its received signal and shows the optimality of the proposed achievable scheme among all linear processing schemes at the IR. As a result of independent interest, the DoF region of the classical multi-antenna two-user Gaussian interference channel without relay when the channel matrices can have any structure is also derived, which generalized available DoF region results that were derived under certain assumptions on the structure of the channel matrices.

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.

In the near future, radar and communication systems will share the spectrum. This motivates the study of how the two systems, which have traditionally operated in different bands, may co-exist. This paper investigates the effect of radar interference (unaltered, beyond the communication system designer's control) on an uncoded communication system, using complex-valued modulation schemes when the Maximum-A-Posteriori (MAP) detector is used. For all commonly used higher order modulation schemes, the Symbol Error Rate (SER) exhibits an "error floor" for the radar interference much larger than the signal power, which can be exactly characterized; in this regime the optimal MAP detector behaves like an interference canceller; interestingly, in this regime the channel behaves as a real-valued phase- fading AWGN channel with receiver CSI, thus indicating a loss of one of the two complex dimensions compared to the complex-valued interference-free channel.

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.

The problem of estimating an arbitrary random vector from its observation corrupted by additive white Gaussian noise, where the cost function is taken to be the minimum mean pth error (MMPE), is considered. The classical minimum mean square error (MMSE) is a special case of the MMPE. Several bounds, properties, and applications of the MMPE are derived and discussed. The optimal MMPE estimator is found for Gaussian and binary input distributions. Properties of the MMPE as a function of the input distribution, signal-to-noiseratio (SNR) and order p are derived. The “single-crossing-point property” (SCPP) which provides an upper bound on the MMSE, and which together with the mutual information-MMSE relationship is a powerful tool in deriving converse proofs in multiuser information theory, is extended to the MMPE. Moreover, a complementary bound to the SCPP is derived. As a first application of the MMPE, a bound on the conditional differential entropy in terms of the MMPE is provided, which then yields a generalization of the Ozarow-Wyner lower bound on the mutual information achieved by a discrete input on a Gaussian noise channel. As a second application, the MMPE is shown to improve on previous characterizations of the phase transition phenomenon that manifests, in the limit as the length of the capacity achieving code goes to infinity, as a discontinuity of the MMSE as a function of SNR. As a final application, the MMPE is used to show new bounds on the second derivative of mutual information, or the first derivative of the MMSE.

This paper studies the impact of block asynchronism on the capacity of a slotted Multiple Access Channel (MAC) whose number of users Knincreases with the blocklength n. In a slotted strong-asynchronous MAC, the Knusers have independent transmission start times that are integer multiples of n (slotted) which are uniformly distributed on a window of length An= enα(strong-asynchronism). All users' messages as well as transmission times need to be reliably decoded at the single receiver. We show that for Kn= enνwith ν > α, not even synchronization is possible when transmitting a single message per user. We also show that for Kn= eνwith ν = o(n), each user can achieve its point-to-point asynchronous capacity, which is a trivial upper bound for the capacity of the MAC. Finally, achievable rates for Kn= enν. with 0 <; ν <; α/2 are derived.

Caching is an efficient way to reduce peak hour network traffic congestion by storing some content at the user's cache without knowledge of later demands. Recently, Maddah-Ali and Niesen proposed a two-phase, placement and delivery phase, coded caching strategy for centralized systems (where coordination among users is possible in the placement phase), and for decentralized systems. This paper investigates the same setup under the assumption that the number of users is larger than the number of files. By using the same uncoded placement strategy of Maddah-Ali and Niesen, a novel coded delivery strategy is proposed to profit from the multicasting opportunities that arise because a file may be demanded by multiple users. The proposed delivery method is proved to be optimal under the constraint of uncoded cache placement for centralized systems with two files. Moreover it is shown to outperform known caching strategies for both centralized and decentralized systems.

This paper considers the minimum mean p-th error (MMPE) estimation problem: estimating a random vector in the presence of additive white Gaussian noise (AWGN) in order to minimize an Lpnorm of the estimation error. The MMPE generalizes the classical minimum mean square error (MMSE) estimation problem. This paper derives basic properties of the optimal MMPE estimator and MMPE functional. Optimal estimators are found for several inputs of interests, such as Gaussian and binary symbols. Under an appropriate p-th moment constraint, the Gaussian input is shown to be asymptotically the hardest to estimate for any p ≥ 1. By using a conditional version of the MMPE, the famous “MMSE single-crossing point” bound is shown to hold for the MMPE too for all p ≥ 1, up to a multiplicative constant. Finally, the paper develops connections between the conditional differential entropy and the MMPE, which leads to a tighter version of the Ozarow-Wyner lower bound on the rate achieved by discrete inputs on AWGN channels.

This work studies the Pliable Index CODing problem (PICOD), a variation of the classical index coding problem where a client is satisfied if it can successfully decode at least one massage not present in its side information set. PICOD models `content-type coding' applications, such as web searches. PICOD significantly differs from classical index coding (where each client desires a specific message not present in its side information set) in the following sense. Past work showed that for PICOD O(log n) broadcast transmissions suffice to satisfy all the n clients, as opposed to the Ω(n) transmissions required by index coding; the key to this exponential improvement in number of transmissions is a probabilistic argument to show that a single transmission can satisfy at least a constant fraction of the clients. This paper elaborates further on this key result as follows. (i) A non-probabilistic analysis provides a lower bound, no smaller than 1/e, on the largest fraction of PICOD clients that can be satisfied by a single transmission in the case where all side information sets have the same cardinality; the new bound is tighter than known ones for any number of messages and clients, and sheds light into how the cardinality of the side information sets affects the number of clients satisfied by a single transmission. (ii) The same argument applied to the case where a message is in the side information set of any given client with probability p ∈ (0, 1) independent of all other messages and clients, and when there are sufficiently many messages, provides an more refined characterization of the performance than known results.

Caching is an effective way to reduce peak-hour network traffic congestion by storing some contents at user's local cache. Maddah-Ali and Niesen (MAN) initiated a fundamental study of caching systems by proposing a scheme (with uncoded cache placement and linear network coding delivery) that is provably optimal to within a factor 4.7. In this paper, when the cache contents and the user demands are fixed, we connect the caching problem to an index coding problem and show the optimality of the MAN scheme under the conditions that (i) the cache placement phase is restricted to be uncoded (i.e, pieces of the files can only copied into the user's cache), and (ii) the number of users is no more than the number of files. As a consequence, further improvements to the MAN scheme are only possible through the use of coded cache placement.

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 shows that for the two-user Gaussian interference channel (G-IC) treating interference as noise without time sharing (TINnoTS) achieves the closure of the capacity region to within either a constant gap, or to within a gap of the order O(log(ln(min(S, I))/y)) up to a set of Lebesgue measure γ ∈ (0, 1], where S is the largest signal to noise ratio on the direct links and I is the largest interference to noise ratio on the cross links. As a consequence, TINnoTS is optimal from a generalized degrees of freedom (gDoF) perspective for all channel gains except for a subset of zero measure. TINnoTS with Gaussian inputs is known to be optimal within 1/2 bit for a subset of the weak interference regime. Rather surprisingly, this paper shows that TINnoTS is gDoF optimal in all parameter regimes, even in the strong and very strong interference regimes where joint decoding of Gaussian inputs is optimal. For approximate optimality of TINnoTS in all parameter regimes, it is critical to use non-Gaussian inputs. This paper thus proposes to use mixed inputs as channel inputs for the G-IC, where a mixed input is the sum of a discrete and a Gaussian random variable. Interestingly, with reference to the Han-Kobayashi achievable scheme, the discrete part of a mixed input is shown to effectively behave as a common message in the sense that, although treated as noise, its effect on the achievable rate region is as if it were jointly decoded together with the desired messages at a non-intended receiver. The practical implication is that a discrete interfering input is a friend, while an Gaussian interfering input is in general a foe. This paper also discusses other practical implications of the proposed TINnoTS scheme with mixed inputs. Since TINnoTS requires neither explicit joint decoding nor time sharing, the results of this paper are applicable to a variety of oblivious or asynchronous channels, such as the block asynchronous G-IC (which is not an information stable channel) and the G-IC with partial codebook knowledge at one or more receivers.

This paper considers the end-to-end mean squared error distortion in reconstructing a memoryless proper-complex Gaussian source transmitted over a set of parallel block-fading Gaussian noise channels, where the fading gains are modeled as correlated Rayleigh distributed random variables with different average powers, thus resulting in asymmetric average received signal noise ratios (SNRs). The distortion exponent (i.e., how fast the average distortion decays to zero as the average received SNR increases) of several coding strategies based on separate source and channel coding is characterized. The definition of distortion exponent commonly used in the literature for SNR-symmetric channels is generalized to the case of SNR-asymmetric channels. It is shown that fading correlation degrades the achievable mean squared error distortion, but does not affect the distortion exponent in the analyzed achievable schemes. The logarithm of the determinant of the fading correlation matrix is found to be a proxy for measuring the performance degradation due to correlation as compared with the case of independent fading. The proposed framework allows one to study any number of correlated parallel channels, contrary to the most of the literature that restricts attention to two channels only, with the same received SNR and with independent fading. In particular, a scheme based on the multiple description coding with more than two descriptions is analyzed; it is shown that determining the distortion exponent in this setting reduces to solving a linear program, which can be done numerically very efficiently. The proposed methodology relies on combining the ideas from linear innovation sequences and properties of determinant of sub-matrices. Interestingly, it is found that SNR-asymmetry is beneficial for multiple description coding when the total average received SNR in decibel is held constant. Even in the SNR-symmetric case, asymmetry in the compression rates is shown to lead to a larger distortion exponent than symmetric rates.

Signal outage, due to shadowing and blockage, is expected to be the main bottleneck in millimeter wave (mmWave) networks. Moreover, the anticipated dense deployment of base stations in mmWave networks is expected to increase the interference from strong line-of-sight base stations too, thus further increasing the probability of outage. To address the issue of reducing outage, this paper explores the possibility of base station co-operation in the downlink of mmWave heterogenous networks. The main focus of this work is showing that, in a stochastic geometry framework that incorporates blockage, co-operation from randomly located base stations decreases the probability of outage/increases the coverage probability. Coverage probabilities are derived accounting for: blockage, different fading distributions on the direct links (but always Rayleigh fading on the interference links), antenna directionality, and different tiers. Numerical results suggest that coverage with base station co-operation in dense mmWave systems (i.e., with high average number of base stations per square meter), without small scale fading on the direct communications links, and with any probability of signal blockage, considerably exceeds coverage without co-operation. In contrast, a small increase in coverage is reported when mmWave networks are less dense, have a high probability of signal blockage and the direct communications links are affected by Rayleigh fading.

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 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.

While a multi-letter limiting expression of the capacity region of the two-user Gaussian interference channel is known, capacity is generally considered to be open as this is not computable. Other computable capacity outer bounds are known to be achievable to within 1/2 bit using Gaussian inputs and joint decoding in the simplified Han and Kobayashi (single-letter) achievable rate region. This work shows that the simple scheme known as “treating interference as noise” without time-sharing attains the capacity region outer bound of the symmetric Gaussian interference channel to within either a constant gap, or a gap of order O(log log(SNR)), for all parameter regimes. The scheme is therefore optimal in the generalized Degrees of Freedom (gDoF) region sense almost surely. The achievability is obtained by using i.i.d. mixed inputs (i.e., a superposition of discrete and Gaussian random variables) in the multi-letter capacity expression, where the optimal number of points in the discrete part of the inputs, as well as the optimal power split among the discrete and continuous parts of the inputs, are characterized in closed form. An important practical implication of this result is that the discrete part of the inputs behaves as a “common message” whose contribution can be removed from the channel output, even though joint decoding is not employed. Moreover, time-sharing may be mimicked by varying the number of points in the discrete part of the inputs.

This paper studies the degrees of freedom (DoF) of the two-user multi-antenna Gaussian interference channel with an instantaneous relay, or relay without delay, where the relay transmitted signal in channel use t can depend on all received signals up to and including that at channel use t. It is assumed that the two transmitters and the two receivers have M antennas, while the relay receives through N antennas and transmits through L antennas. An achievable DoF is derived for all possible values of (M;N;L), based on a linear transmission strategy at the relay that aims to neutralize as much interference as possible at each destination. The proposed scheme is shown to attain the largest DoF among all linear transmission strategies at the relay and to actually be the optimal DoF for certain values of (M;N;L).

Motivated by the ongoing discussion of spectrum scarcity, this paper considers the K-user cognitive interference channel with K - 1 primary/licensed users and one cognitive/secondary user who has non-causal knowledge of the messages of all primary users. This message sharing mechanism is referred to as cognitive-only message sharing. For certain parameter regimes, the sum-capacity of the symmetric Gaussian noise channel is characterized to within an additive constant gap from an outer bound originally derived for a channel model with cumulative message sharing, which consists of one primary user and K-1 cognitive users where cognitive transmitter i ∈ [2 : K] has non-causal knowledge of the messages of the users with index less than i. The approximately optimal achievability scheme is a combination of simultaneous interference neutralization at the primary receivers, dirty-paper coding to remove the effect of interference at the cognitive receiver, and rate-splitting, where the power splits are chosen such that the signals treated as noise are received below the noise floor of the receiver. This shows that “distributed cognition” may not be necessary in the considered network model since (approximately) the same sum-capacity can be achieved by having only one “globally cognitive” user whose role is to manage all the interference in the network.

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.

The study of the two-user Gaussian Interference Channel (IC) where one receiver lacks knowledge of the interfering codebook, also dubbed the IC with an oblivious receiver (IC-OR), is motivated by: (1) in heterogeneous, cognitive, distributed or dynamic networks, assuming that every node posses codebooks of every other node may not be practical, and (2) it is not clear whether and how much lack of codebook knowledge would affect the Han and Kobayashi (HK) achievable scheme, which involves joint decoding of intended and interfering messages and which appears not possible if nodes do not possess all codebooks. To address these issues, we evaluate a simplified HK (where the oblivious receiver treats interference as noise) with mixed inputs at the non-oblivious transmitter, i.e., a mixture of discrete and Gaussian random variables, where the power split between the two and the number of points of the discrete part are carefully chosen as a function of the channel parameters. The oblivious transmitter uses a purely Gaussian input. Surprisingly, for this choice of inputs, the capacity region of the symmetric Gaussian IC-OR is shown to be within 1 over 2 log (12πe) ≈ 3.34 bits of the best known outer bound for the classical Gaussian IC with full codebook knowledge at both receivers. Interestingly, this shows that a simplified HK where one receiver is restricted to treat interference as noise loses at most 1 over 2 log (12πe) ≈ 3.34 bits in performance. Moreover, the discrete part of the input behaves like a “common message” even though it is not jointly decoded (together with the intended messages) at the oblivious receiver.

In multiuser information theory, it is often assumed that every node in the network possesses all codebooks used in the network. This assumption may be impractical in distributed ad hoc, cognitive, or heterogeneous networks. This paper considers the two-user interference channel with one oblivious receiver (IC-OR), i.e., one receiver lacks knowledge of the interfering cookbook, whereas the other receiver knows both codebooks. This paper asks whether, and if so how much, the channel capacity of the IC-OR is reduced compared with that of the classical IC where both receivers know all codebooks. A novel outer bound is derived and shown to be achievable to within a gap for the class of injective semideterministic IC-ORs; the gap is shown to be zero for injective fully deterministic IC-ORs. An exact capacity result is shown for the general memoryless IC-OR when the nonoblivious receiver experiences very strong interference. For the linear deterministic IC-OR that models the Gaussian noise channel at high SNR, nonindependent identically distributed. Bernoulli(1/2) input bits are shown to achieve points not achievable by i.i.d. Bernoulli(1/2) input bits used in the same achievability scheme. For the real-valued Gaussian IC-OR, the gap is shown to be at most 1/2 bit per channel use, even though the set of optimal input distributions for the derived outer bound could not be determined. Toward understanding the Gaussian IC-OR, an achievability strategy is evaluated in which the input alphabets at the nonoblivious transmitter are a mixture of discrete and Gaussian random variables, where the cardinality of the discrete part is appropriately chosen as a function of the channel parameters. Surprisingly, as the oblivious receiver intuitively should not be able to jointly decode the intended and interfering messages (whose codebook is unavailable), it is shown that with this choice of input, the capacity region of the symmetric Gaussian IC-OR is to within 1/2 log (12πe)≈ 3.34 bits (per channel use per user) of an outer bound for the classical Gaussian IC with full codebook knowledge at both receivers.

This paper characterizes the sum-capacity of the ergodic fading Gaussian overlay cognitive interference channel (EGCIFC), a time-varying channel with two source-destination pairs in which a primary/licensed transmitter and a secondary/cognitive transmitter share the same spectrum and where the cognitive transmitter has noncausal knowledge of the primary user's message. The throughput/sum-capacity is characterized under the assumption of perfect knowledge of the instantaneous fading states at all terminals, which are assumed to form an ergodic process. A genie-aided outer bound on the sum-capacity is developed and then matched with an achievable scheme, thereby completely characterizing the sum-capacity of the EGCIFC. The power allocation policy that maximizes the sum-capacity is derived. It is shown that the sum-capacity achieving scheme for an EGCIFC is “separable” in all regimes (i.e., coding across fading states is not necessary), as opposed to the classical interference channel. Extensions to the whole capacity region are discussed. As a capacity achieving scheme for the EGCIFC under certain channel gain conditions, and as a topic of independent interest, the ergodic capacity of a point-to-point multiple-input-single-output channel with per-antenna power constraints and with perfect channel state information at all terminals is also derived.

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 derives a closed-form expression for the capacity of the point-to-point static Gaussian MIMO channel under per-antenna power constraints when the channel matrix is full column rank and the optimal input covariance matrix is full rank. Analytical and numerical examples are given to illustrate the applicability of the result.

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 sum-rate of a class of memoryless, real-valued additive white Gaussian noise interference channels (IC) achievable by treating interference as noise (TIN). We develop and analytically characterize the rates achievable by a new strategy that uses superpositions of Gaussian and discrete random variables as channel inputs. Surprisingly, we demonstrate that TIN is sum-generalized degrees of freedom optimal and can achieve to within an additive gap of O(1) or O(log log(SNR)) to the symmetric sum-capacity of the classical IC. We also demonstrate connections to other channels such as the IC with partial codebook knowledge and the block asynchronous IC.

This paper characterizes the ergodic capacity of the fading multiple-input single-output (MISO) channel with per-antenna power constraints (PerPC) with perfect Channel State Information (CSI) at all terminals. This turns out to be the sum-capacity achieving strategy for the ergodic fading Gaussian overlay cognitive interference channel (EGCIFC) in the strong interference regime. The EGCIFC is a two-user time-varying interference channel in which a primary / licensed transmitter and a secondary / cognitive transmitter share the same spectrum and where the cognitive transmitter has non-causal knowledge of the primary user's message. The MISO and the EGCIFC results are verified numerically for the case of independent Rayleigh fading gains. Different achievable strategies, corresponding to different amount of CSI, are compared to show the performance of the derived PerPC optimal power allocation.

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.

The interference channel with a cognitive relay (IFC-CR) consists of the classical IFC with two independent source-destination pairs whose communication are aided by an additional node, referred to as the CR, that has a priori knowledge of both sources' messages. This a priori message knowledge is termed cognition and idealizes the relay learning the messages of the two sources from their transmissions over a wireless channel. This paper presents improved outer and inner bounds on the capacity region of the general memoryless IFC-CR that are shown to be tight for certain classes of channels. The new outer bound follows from arguments originally devised for broadcast channels, among which Sato's observation that the capacity region of channels with noncooperative receivers only depends on conditional marginal distributions of the channel output, not on their conditional joint distribution. A simplified expression for the inner bound is derived, which contains all previously proposed coding schemes. The new inner and outer bounds coincide for a class of channels satisfying some strong interference condition, i.e., for these channels there is no loss in optimality if both destinations decode both messages. This result parallels analogous results for the classical interference channel and for the cognitive interference channel and is the first known capacity result for the general IFC-CR. Numerical evaluations of the proposed inner and outer bounds are presented for the additive white Gaussian noise case.

This paper considers a variation of the classical two-user interference channel where the communication of two interfering source-destination pairs is aided by an additional node that has a priori knowledge of the messages to be transmitted, which is referred to as the cognitive relay. For this interference channel with a cognitive relay (ICCR), novel outer bounds and capacity region characterizations are derived. In particular, for the class of injective semi-deterministic ICCRs, a sum-rate upper bound is derived for the general memoryless ICCR and further tightened for the linear deterministic approximation (LDA) of the Gaussian noise channel at high SNR, which disregards the noise and focuses on the interaction among the users' signals. The capacity region of the symmetric LDA is completely characterized except for the regime of moderately weak interference and weak links from the CR to the destinations. The insights gained from the analysis of the LDA are then translated back to the symmetric Gaussian noise channel (GICCR). For the symmetric GICCR, an approximate characterization (to within a constant gap) of the capacity region is provided for a parameter regime where capacity was previously unknown. The approximately optimal scheme suggests that message cognition at a relay is beneficial for interference management as it enables simultaneous over the air neutralization of the interference at both destinations.

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.

The capacity region of the cooperative two-user Multiple Access Channel (MAC) in Gaussian noise is determined to within a constant gap for both the Full-Duplex (FD) and Half-Duplex (HD) case. The main contributions are: (a) for both FD and HD: unilateral cooperation suffices to achieve capacity to within a constant gap where only the user with the strongest link to the destination needs to engage in cooperation, (b) for both FD and HD: joint backward decoding is not necessary to achieve capacity to within a constant gap, and (c) for HD: time sharing between the case where the two users do not cooperate and the case where the user with the strongest link to the destination acts as pure relay for the other user suffices to achieve capacity to within a constant gap. These findings show that simple achievable strategies are approximately optimal for all channel parameters with interesting implications for practical cooperative schemes.

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.

Shannon theoretic multi-user capacity problems are traditionally formulated under the assumption that all decoding nodes possess all codebooks. However, for certain networks such as cognitive ones, this may be an unrealistic assumption. We work towards understanding the impact of lack of codebook knowledge at some decoding nodes in the network. We do so by considering a two-user interference channel in which one of the receivers has no information about the codebook of the interfering transmitter, while the other receiver has both codebooks. We derive a novel outer bound for the special class of injective semi-deterministic interference channels which incorporates this codebook knowledge explicitly. For the linear deterministic channel, which models the Gaussian channel at high SNR, we demonstrate the surprising fact that non i.i.d. Bernoulli(1/2) points achieve points on the outer bound not achievable by Bernoulli(1/2) inputs. We then show that this is achievable to within a constant gap by a modified Han-Kobayashi scheme. We characterize the capacity region of the Gaussian noise channel to within 1/2 bit, even though we could not determine the set of optimal input distributions. Numerical evaluations suggest that if the non-oblivious transmitter uses a discrete input a larger sum-rate is achievable compared to the case where both users employ Gaussian codebooks or use time division in strong interference regime at high SNR.

This paper considers the K-user cognitive interference channel with one primary and K - 1 secondary/cognitive transmitters with a cumulative message sharing structure, i.e., cognitive transmitter i, i ϵ [2 : K], non-causally knows all messages of the users with index less than i. We first propose a computable outer bound valid for any memoryless channel and show the sum-rate to be achievable for the symmetric K-user Linear Deterministic Channel. Interestingly, for the K-user channel having only the K-th transmitter know all other messages is sufficient to achieve the sum-capacity, i.e., cognition at transmitters 2 to K-1 is not needed. Next, the sum-capacity of the symmetric Gaussian noise channel is characterized to within a constant additive and multiplicative gap, which depend on K. As opposed to other interference channel models, a single scheme suffices for both the weak and strong interference regimes. Moreover it is only required for transmitters 2 to K-1 to have, in addition to their own message, non-causal message knowledge of the transmitter 1's message.

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.

This work considers different K-user extensions of the two-user cognitive interference channel model. The models differ by the cognitive abilities of the transmitters. In particular, the primary message sharing model, in which only one user is cognitive and knows all messages, and the cumulative message sharing model, in which a user knows the messages of all users with lesser index, are analyzed. The central contribution is the characterization of the sum-capacity of both models under a strong interference condition, which amounts to having one receiver in the network that can decode all transmitted signals without loss of optimality. The sum-capacity is evaluated for the Gaussian noise channel, as well as the conditions on the channel gains that grant strong interference.

The capacity of the Interference Channel with a Cognitive Relay, a channel model which generalizes the broadcast, interference and cognitive interference channels, is still an open question. Towards understanding this complex channel, we first consider the binary linear deterministic model that approximates the Gaussian channel at high SNR. We consider symmetric channel gains and show achievability of a tightened version of a previously known outer bound for almost all channel parameters. Of particular interest in this channel model is how the cognitive relay may be used to simultaneously relay as well as cancel/neutralize interference at the two receivers. The achievability schemes used to prove capacity use combinations of three main strategies at the cognitive relay that we term bit cancellation, bit sharing, and bit (self)cleaning. We highlight the capacity achieving schemes in the different regimes, pointing out some of the interesting new behaviors seen at the cognitive relay.

Inspired by cognitive networks, we consider the linear deterministic three-user cognitive interference channel with one primary and two secondary/cognitive transmitters which approximates the Gaussian channel at high SNR. Outer bounds on the sum-rate are derived and matching transmission schemes are provided in all interference regimes, thereby completely characterizing the sum-capacity. Significant increase in the sum-capacity is demonstrated when comparing the three-user cognitive channel to the classical (non-cognitive) three-user interference channel and to the two-user cognitive channel. The paper discusses extensions to an arbitrary number of users, the relationship between the cognitive channel and the (fully cooperative) broadcast channel, and observations on the behavior of the cognitive transmitters in the different interference scenarios.

The interference channel models a wireless network where several source-destination pairs compete for the same resources. This paper considers a 4-node network, where two nodes are sources and the other two are destinations. All nodes are full-duplex and cooperate to mitigate interference. A sum-rate outer bound is derived, which is shown to unify a number of previously derived outer bounds for special cases of cooperation or feedback. The approach is shown to extend to cooperative interference networks with more than two source-destination pairs and for any partial sum-rate. How the derived bound relates to other channel models including cognitive nodes, i.e., nodes that have non-causal knowledge of the messages of some other node, is also discussed. The bound is evaluated in Gaussian noise.

The capacity of the Gaussian cognitive interference channel, a variation of the classical two-user interference channel where one of the transmitters (referred to as cognitive) has knowledge of both messages, is known in several parameter regimes but remains unknown in general. This paper provides a comparative overview of this channel model as it proceeds through the following contributions. First, several outer bounds are presented: (a) a new outer bound based on the idea of a broadcast channel with degraded message sets, and (b) an outer bound obtained by transforming the channel into channels with known capacity. Next, a compact Fourier-Motzkin eliminated version of the largest known inner bound derived for the discrete memoryless cognitive interference channel is presented and specialized to the Gaussian noise case, where several simplified schemes with jointly Gaussian input are evaluated in closed form and later used to prove a number of results. These include a new set of capacity results for: (a) the “primary decodes cognitive” regime, a subset of the “strong interference” regime that is not included in the “very strong interference” regime for which capacity was known, and (b) the “S-channel in strong interference” in which the primary transmitter does not interfere with the cognitive receiver and the primary receiver experiences strong interference. Next, for a general Gaussian channel the capacity is determined to within one bit/s/Hz and to within a factor two regardless of the channel parameters, thus establishing rate performance guarantees at high and low SNR, respectively. The paper concludes with numerical evaluations and comparisons of the various simplified achievable rate regions and outer bounds in parameter regimes where capacity is unknown, leading to further insight on the capacity region.

In this paper we study the long-term throughput performance of repetition protocols coupled with power control for multiple access block-fading channels. We propose to use the feedback bits to inform the transmitter about the decoding status and the instantaneous channel quality. We determine the throughput of simple and practically inspired protocols; we show remarkable throughput improvements, especially at low and moderate SNR, when compared to protocols where the feedback bits are used for acknowledgment only or for power control only; we show that the throughput is very close to the ultimate ergodic multi-user water-filling capacity for small number of feedback bits and/or retransmissions. For symmetric Rayleigh fading channels, numerical results show that the throughput improvement is mainly due to the ability to perform a power control, rather than to retransmit.

The cognitive interference channel (C-IFC) consists of a classical two-user interference channel in which the message of one user (the "primary" user) is non-causally available at the transmitter of the other user (the "cognitive" user). We obtain the capacity of the semi-deterministic C-IFC: a discrete memoryless C-IFC in which the cognitive receiver output is a noise-less deterministic function of the channel inputs. We then use the insights obtained from the capacity-achieving scheme for the semi-deterministic model to derive new, unified and tighter constant gap results for the complex-valued Gaussian C-IFC. We prove: (1) a constant additive gap (difference between inner and outer bounds) of half a bit/sec/Hz per real dimension, of relevance at high SNRs, and (b) a constant multiplicative gap (ratio between outer and inner bounds) of a factor two, of relevance at low SNRs.

This work proposes a novel outer bound for the Gaussian cognitive interference channel in strong interference at the primary receiver based on the capacity of a multi-antenna broadcast channel with degraded message set. It then shows that for the Z-channel, i.e., when the secondary receiver experiences no interference and the primary receiver experiences strong interference, the proposed outer bound not only is the tightest among known bounds but is actually achievable for sufficiently strong interference. The latter is a novel capacity result that from numerical evaluations appears to be generalizable to a larger (i.e., non-Z) class of Gaussian channels.

The InterFerence Channel with a Cognitive Relay (IFC-CR) consists of a classical two-user interference channel in which the two independent messages are also non-causally known at a cognitive relay node. In this work a special class of IFC-CRs in which the sources do not create interference at the non-intended destinations is analyzed. This special model results in a channel with two non-interfering point-to-point channels whose transmission is aided by an in-band cognitive relay, which is thus referred to as the Parallel Channel with a Cognitive Relay (PC-CR). We determine the capacity of the PC-CR channel to within 3 bits/s/Hz for all channel parameters. In particular, we present several new outer bounds which we achieve to within a constant gap by proper selection of Gaussian input distributions in a simple rate-splitting and superposition coding-based inner bound. The inner and outer bounds are numerically evaluated to show that the actual gap can be far less than 3 bits/s/Hz.

The interference channel with a cognitive relay consists of a classical interference channel with two source-destination pairs and with an additional cognitive relay that has a priori knowledge of the sources' messages and aids in the sources' transmission. We derive a new outer bound for this channel using an argument originally devised for the “more capable” broadcast channel, and show the achievability of the proposed outer bound for a class of channels where there is no loss in optimality if both destinations decode both messages. This result is analogous to the “very strong interference” capacity result for the classical interference channel and for the cognitive interference channel, and is the first capacity known capacity result for the general interference channel with a cognitive relay.

This paper derives an outer bound on the capacity region of a general memoryless interference channel with an arbitrary number of users. The derived bound is the first known outer bound region valid for any memoryless channel besides the cut-set bound, which is loose even in the two-user case. In Gaussian noise, classes of channels for which the proposed bound gives the sum-rate capacity are identified, including degraded channels and a class of Z-channels.

The cognitive interference channel is a two-user interference channel in which one transmitter is non-causally provided with the message of the other transmitter. This channel model has been extensively studied in the past years and capacity results have been proved for certain classes of channels. This paper presents new inner and outer bounds for the capacity region of the cognitive interference channel, as well as new capacity results. Previously proposed outer bounds are expressed in terms of auxiliary random variables for which no cardinality constraint of their alphabet is known. Consequently, it is not possible to evaluate such outer bounds explicitly for a given channel. The outer bound derived in this work is based on an idea originally devised by Sato for channels without receiver cooperation and results in an outer bound that does not contain auxiliary random variables, thus allowing it to be more easily evaluated. The inner bound presented in this work-which includes rate splitting, superposition coding, a broadcast channel-like binning scheme and Gel'fand Pinsker coding-is the largest known to date and is explicitly shown to include all previously proposed achievable rate regions. The novel inner and outer bounds are shown to coincide in certain cases. In particular, capacity is proved for a class of channels in the so-called “better cognitive decoding” regime, which includes the regimes in which capacity was known. Finally, the capacity region of the semi-deterministic cognitive interference channel, in which the signal at the cognitive receiver is an arbitrary deterministic function of the channel inputs, is established.

This paper studies the throughput performance of hybrid automatic repeat request (HARQ) protocols over block fading Gaussian channels. It proposes new protocols that use the available feedback bit(s) not only to request a retransmission, but also to inform the transmitter about the instantaneous channel quality. An explicit protocol construction is given for any number of retransmissions and any number of feedback bits. The novel protocol is shown to simultaneously realize the gains of HARQ and of power control with partial channel state information. Remarkable throughput improvements are shown, especially at low and moderate signal-to-noise ratio (SNR), with respect to protocols that use the feedback bits for retransmission request only. In particular, for the case of a single retransmission and a single feedback bit, it is shown that the repetition is not needed at low SNR where the throughput improvement is due to power control only. On the other hand, at high SNR, the repetition is useful and the performance gain comes from a combination of power control and ability to make up for deep fades.

This paper considers the asymptotic behavior of the outage probability of a two-source block-fading single-antenna Gaussian interference channel in the high-SNR regime by means of the diversity-multiplexing tradeoff. A general setting where the user rates and the average channel gains are not restricted to be symmetric is investigated. This asymmetric scenario allows to analyze networks with “mixed” interference, i.e., when different sources are at different distance from their intended destination, that are not possible under the commonly used symmetric assumption. Inner and outer bounds for the diversity are derived. The outer bound is based on the recent “to within one bit” capacity result of Etkin for the unfaded Gaussian channel and is a re-derivation of a known bound for which an error is pointed out. The inner bound is based on the Han and Kobayashi achievable region both without rate splitting and with a rate spitting inspired by the “to within one bit” capacity result. An analytical comparison of the diversity upper and lower bounds for a general channel seems difficult; by numerical evaluations, the two bounds are shown to coincide for a fairly large set of channel parameters.

An Interference Channel with Generalized Feedback (IFC-GF) models a wireless network where the sources can sense the channel activity. The signal overheard from the channel provides information about the activity of the other sources and thus furnishes the basis for cooperation. This two-part paper studies achievable strategies (Part I) and outer bounds (Part II) for the general discrete memoryless IFC-GF with two source-destination pairs. In Part I, the generalized feedback is used to gain knowledge about the message sent by the other source and then exploited in two ways: a) to relay the messages that can be decoded at both destinations, thus realizing the gains of beam-forming of a distributed multiantenna system, and b) to hide the messages that can not be decoded at the nonintended destination, thus leveraging the interference “precancellation” property of dirty-paper coding. We show that our achievable region generalizes several known achievable regions for the IFC-GF and that it reduces to known achievable regions for the channels subsumed by the IFC-GF model. For the Gaussian channel, it is shown that source cooperation enlarges the achievable rate region of the corresponding IFC without generalized feedback/cooperation.

The loopy belief propagation algorithm (LBP) is known to perform extremely well in many practical problems of probability inference and learning on graphical models, even in presence of multiple loops. Although general necessary conditions for convergence of LBP to a unique fixed point solution are still unknown, various techniques have been explored to understand error propagation when LBP fails to converge. In this paper, we rely on the contractive mapping of message errors to present novel distance bounds between multiple fixed point solutions when LBP does not converge. We give examples of networks where our bounds are tighter than existing ones.

This paper considers the asymptotic behavior of two-source block-fading single-antenna Gaussian Interference Channels in the high-SNR regime by means of the diversity multiplexing tradeoff. We consider a general setting where the users and the average channel gains are not restricted to be symmetric. Our results are not just extensions of previous results for symmetric networks, as our setting covers scenarios that are not possible under the symmetric assumption, such as the case of "mixed" interference, i.e., when difference sources have different distances from their intended receivers. We derive lower bounds on the DMT by considering rate splitting. We show that, rate splitting improves the inner bound with respect to the previous results and coincides with the outer bound for a fairly large set of channel parameters.

We consider the problem of transmitting a Gaussian source over a Rayleigh fading channel where some side-information may be available to the receiver. Our objective is to minimize the average distortion at the receiver. We consider two source models with side-information: 1) the Heegard-Berger model where "side-information may be absent", and 2) successive refinement with degraded side-information. We show that the average distortion problem can be numerically solved by convex optimization techniques. Furthermore, in high SNR, we obtain an analytical solution that shows that the side-information does not affect the distortion exponent, but causes an offset with respect to the case without side information. Numerical results show that our analytical high SNR approximation gives accurate results even at medium SNR.

In this paper, we first present an outer bound for a general interference channel with a cognitive relay, i.e., a relay that has non-causal knowledge of both independent messages transmitted in the interference channel. This outer bound reduces to the capacity region of the deterministic broadcast channel and of the deterministic cognitive interference channel the through nulling of certain channel inputs. It does not, however, reduce to that of certain deterministic interference channels for which capacity is known. As such, we subsequently tighten the bound for channels whose outputs satisfy an “invertibility” condition. This second outer bound now reduces to the capacity of the special class of deterministic interference channels for which capacity is known. The second outer bound is further tightened for the high-SNR deterministic approximation of the Gaussian channel by exploiting the special structure of the interference. We provide an example that suggests that this third bound is tight in at least some parameter regimes for the high-SNR deterministic approximation of the Gaussian channel. Another example shows that the third bound is capacity in the special case where there are no direct links between the non-cognitive transmitters.

This paper considers the end-to-end mean-square distortion in reconstructing a memoryless proper-complex Gaussian source transmitted over parallel block-fading Rayleigh AWGN channels. We characterize the distortion exponent of several source and channel coding strategies; that is, we characterize how fast the distortion decays to zero as the SNR increases. Unlike previous works, we consider networks with different received SNR's and with correlated fading. We generalize the definition of distortion exponent to SNR-asymmetric channels. We show that fading correlation degrades the achievable mean-square distortion but does not affect the distortion exponent. The performance degradation is measured in terms of power-offset; that is, the power increment needed to achieve the same performance as the uncorrelated case. We show that the power-offset is proportional to the determinant of the fading correlation matrix. Our proposed methodology allows us to study any number of parallel channels and we are no longer restricted to two channels (as was commonly done in the previous literature). Finally, we show that determining the distortion exponent of multiple description coding (MDC) schemes in high SNR reduces to solving a linear programming problem.

Interference Channels (IFC) with Generalized Feedback (GF) model wireless channels where every node overhears the transmission of other nodes and uses it to engage in cooperative communication strategies. The overheard signals, instead of being treated as interference, furnish the basis for cooperation among otherwise uncoordinated users. Although cooperative communications is not equivalent to virtual Multi-Input-Multi-Output (MIMO) communications, it has been shown to benefit the rate performance of all the involved source-destination pairs without increasing neither their transmit powers nor the channel bandwidth. This paper develops a new sum-rate outer bound for Gaussian IFC-GFs based on the idea of giving the receivers the least informative GF signal as side information. We compare our new outer bound with bounds available in the literature and numerically show for which network parameters our bound strictly improves on existing ones.

The problem of optimal rate allocation to streams constituting multiple description coding (MDC) has largely been addressed under the assumption that the multiple paths available for transmission are uncorrelated. In this paper, we model the transmission paths as correlated erasure channels and then examine the problem of allocating a given coding rate to the multiple descriptions in order to minimize the average distortion of the reconstructed message. We also investigate the relationship between the optimal average distortion and correlation of channels and prove that the bound on the average distortion will decrease as the correlation increases. Furthermore, we derive a closed-form solution for the contour which determines the region where multiple description coding (MDC) or single description coding (SDC) yields the minimal bound on the average distortion. Relying on this contour, we present a heuristic of the optimal rate allocation problem to determine the number of descriptions and relative rates.

In this paper, we study the throughput performance of incremental redundancy repetition protocols over block fading channels. We propose new protocols that use the available feedback bits not only to request a retransmission, but also to inform the transmitter about the channel quality. We give an explicit protocol construction for any number of retransmissions and any number of feedback bits. We show remarkable throughput improvements, especially at low and moderate SNR, where our protocols can perform power control thanks to the partial channel state obtained through feedback. For the case of a single retransmission and a single feedback bit, we show that the repetition is not needed at low SNR and that the throughput improvement is due to power control only. On the other hand, at high SNR the repetition is useful and the performance comes form a combination of power control and ability to resend.

In this paper, we study the optimal rate allocation of multiple description coding over multiple erasure channels in order to attain the minimum average distortion of the recovered message at the receiver. The results of this investigation are subsequently used to determine conditions under which the optimal rate allocation is characterized by transmission of one description over a single channel, i.e. single description coding. We formulate the optimal rate allocation problem by using rate- distortion theory under the constraint that the total coding rate is fixed and solve the problem by using numerical methods. Furthermore, we derive a closed-form analytical solution to the optimal rate allocation problem under four conditions and verify that the analytical solution is consistent with the numerical results. Also, we present a heuristic that captures the solution to the optimal rate allocation problem and can be used to determine the number of descriptions and relative rates required to achieve optimality.

This work analyzes a particular achievable region for Gaussian interference channels (IFC) derived from the general Han-Kobayashi region. By reformulating the Han-Kobayashi achievable region as the sum of two sets, we characterize the maximum achievable sum-rate with Gaussian inputs and without time-sharing in closed from for any channel parameter. We then show that the computed sum-rate meets the upper bound by Kramer for any IFC with mixed interference, and not only for IFC with strong interference. We then show that for a certain subclass of IFCs with mixed interference, the capacity region contains a line segment of slope -1 of which we characterize the extreme points in term of the power allocation among private and common messages.

This work studies cooperative communication strategies for Interference Channels with Generalized Feedback (IFC-GF). IFC-GF models wireless peer-to-peer networks where several source-destination pairs share the same channel and, because of the broadcast nature of the wireless channel, each transmission can be overheard by the other users. In this model, the interference due to simultaneous communications furnishes the basis for cooperation among otherwise uncoordinated users. For the case of two source-destination pairs, we propose a coding strategy that combines the ideas of (i) information splitting (introduced by Han and Kobayashi for IFC without feedback), (ii) block Markov superposition coding (introduced by Cover and Leung for multiaccess channels with perfect feedback), and (iii) backward decoding (introduced by Willems in the context of multiaccess channels with cribbing encoders). We show that by exploiting the overheard information with the proposed scheme, users achieves collectively higher data rates than the case where the overheard information is neglected. We conclude by showing how our model reduces to well studied multiuser channels.

We consider communication through a cascade of discrete memoryless channels (DMCs). The source and destination node of this cascade are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of a fixed length. We investigate how the processing at the relays must be chosen in order to maximize the capacity of the cascade, that is, the maximum achievable end-to-end rate between the source and the destination. For infinite cascades with fixed intermediate processing length at the relays, we prove that this intermediate processing can be chosen to be identical without loss of optimality, and that the capacity of the cascade coincides with the rate of the best zero-error code of length equal to the block length of the intermediate processing. We further show that for fixed and identical intermediate processing at all relays, convergence of capacity as the length of the cascade goes to infinity is exponentially fast. Finally, we characterize how the block length of the intermediate processing must scale with the length of the cascade to guarantee a constant end-to-end rate. We prove that it is sufficient that the block length scales logarithmically with the network length in order to achieve any rate above the zero-error capacity. We show that in many cases of interest logarithmic growth is also necessary.

We consider communication through a cascade of L identical discrete memoryless channels (DMCs). The source and destination node are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of N symbols. It is well known that for any L and N rarr infin the relays can use a capacity achieving code and communicate reliably as long as the rate of this code is below the capacity of the underlying DMC. The capacity of the cascade is hence equal to the network min-cut capacity. For finite N and L rarr infin, we showed in previous work that the optimal intermediate processing is the highest rate zero-error code of length N for the underlying DMC. The capacity of the cascade coincides with the rate of this zero-error code, and is always below the zero-error capacity. In this work, we characterize how N must scale with L in order to achieve rates in between the zero-error and the min-cut capacity. In particular, we have observed that N = thetas (log L) is sufficient to achieve any rate below the min-cut capacity. Here, we develop a novel upper bound on the capacity of cascades with optimal intermediate processing that applies for any (N, L) pairs and use it to show that N = thetas (log L) is necessary to achieve certain rates above the zero-error capacity. Furthermore, we propose a method to evaluate our upper bound by establishing a connection with the set-cover problem in algorithms

We consider a source that transmits information to a receiver by routing it over a communication network represented by a graph and examine rate benefits that finite complexity processing at the intermediate nodes may offer. We show that there exist configurations where the optimal rate is achieved only when coding across independent information streams (channel coding and routing cannot be separated); that optimal processing is a function of the particular set of channel parameters and not only of the network topology; and that there exists a connection between linear codes and routing for a special class of graphs

In this work, we study coding over a class of two-user broadcast channels (BCs) with additive white Gaussian noise and multiplicative fading known at the receivers only. Joint decoding of low-density parity-check (LDPC) codes is analyzed. The message update rule at the mapping node linking the users' codes is derived and is found to exhibit an interesting soft interference cancellation property. High performance codes are found using the differential evolution optimization technique and extrinsic information transfer analysis adapted to our multiuser setting. The optimized codes have rates very close to the boundary of the achievable region for binary constrained input for both faded and unfaded channels. Simulation results for moderate block lengths show that our codes operate within less than 1 dB of their respective threshold.

We consider multiaccess, broadcast, and interference channels with additive Gaussian noise. Although the set of rate pairs achievable by time-division multiple access (TDMA) is not equal to the capacity region, the TDMA achievable region converges to the capacity region as the power decreases. Furthermore, TDMA achieves the optimum minimum energy per bit. Despite those features, this paper shows that the growth of TDMA-achievable rates with the energy per bit is suboptimal in the low-power regime except in special cases: multiaccess channels where the users' energy per bit are identical and broadcast channels where the receivers have identical signal-to-noise ratios. For the additive Gaussian noise interference channel, we identify a small region of interference parameters outside of which TDMA is also shown to be suboptimal. The effect of fading (known to the receiver) on the suboptimality of TDMA is also explored.

We consider a nonergodic multiple-access Gaussian block-fading channel where a fixed number of independent and identically distributed (i.i.d.) fading coefficients affect each codeword. Variable-rate coding with input power constraint enforced on a per-codeword basis is examined. A centralized power and rate allocation policy is determined as a function of the previous and present fading coefficients. The power control policy that optimizes the expected rates is obtained through dynamic programming and the average capacity region and the average capacity region per unit energy are characterized. Moreover, we study the slope of spectral efficiency curve versus E/sub b//N/sub 0/ (dB), and we quantify the penalty incurred by time-division multiple access (TDMA) over superposition coding in the low-power regime.

We compute the throughput of some multiaccess wireless systems for delay-tolerant data communications, characterized by an infinite population of uncoordinated users accessing a common channel. The channel is affected by block fading, and the channel state is perfectly known to the receiver but unknown to the transmitters. To cope with multiaccess interference (MAI) and fading, the users employ retransmission of erroneously received packets. We consider unspread and randomly spread (code-division multiple-access (CDMA)) systems with decentralized (single-user) decoding and a system where the receiver employs joint multiuser decoding. The following conclusions can be drawn from our analysis: (a) unspread systems with packet retransmission outperforms CDMA systems with conventional detection, but are outperformed by CDMA with linear minimum mean-square error (MMSE) detection. (b) For all systems based on single-user decoding (SUD), there exists a threshold value of (E/sub b//N/sub o/) below which the throughput is maximized by an infinite number of users per dimension transmitting at vanishing rate, and above which the throughput is maximized by a finite average number of users per dimension transmitting at nonvanishing rate. Moreover, as (E/sub b//N/sub o/) increases, the optimal average number of users per dimension tends to one. In this sense, we say that the optimized systems "self-orthogonalize." (c) For the system based on joint multiuser decoding, a simple slotted ALOHA strategy is able to recover the throughput penalty due to fading in the limit for high (E/sub b//N/sub o/), while an incremental redundancy (INR) strategy recovers the fading penalty for any (E/sub b//N/sub o/).

In next-generation wireless communication systems, packet-oriented data transmission will be implemented in addition to standard mobile telephony. We take an information-theoretic view of some simple protocols for reliable packet communication based on "hybrid-ARQ," over a slotted multiple-access Gaussian channel with fading and study their throughput (total bit per second per hertz) and average delay under idealized but fairly general assumptions. As an application of the renewal-reward theorem, we obtain closed-form throughput formulas. Then, we consider asymptotic behaviors with respect to various system parameters. The throughput of automatic retransmission request (ARQ) protocols is compared to that of code division multiple access (CDMA) with conventional decoding. Interestingly, the ARQ systems are not interference-limited even if no multiuser detection or joint decoding is used, as opposed to conventional CDMA.