The problem of scalar topological interference management with heterogeneous erasures (STIME) is formalized, by adopting a one-shot model that favors ultra low latency communication, partially connected interference network topologies that are motivated by directional transmission, limited channel knowledge at the transmitters that is restricted to the network connectivity, erasures that model sporadic disruptions that are detectable at the receiver, and a performance metric that is closer to Hamming than Shannon, seeking the shortest multiuser-code that is robust to a set of specified erasure patterns for each user. In the absence of erasures, STIME reduces to the scalar TIM (STIM) problem which, based on prior work, corresponds to scalar index coding, and as such admits a well known minrank optimal solution. By the same token, STIME can be viewed as essentially a scalar index coding problem with heterogeneous erasures at each receiver. The optimal solution to STIME is bounded within a factor of 2 based on its connections to STIM for heterogeneous erasures. The bounds are shown to be tight in several cases, e.g., for topologies where alignment graphs have no internal conflicts, for neighboring interference models, and for arbitrary topologies if the erasure thresholds are identical across users. A mapping from any STIME setting to a corresponding STIM setting is identified such that the two problems have the same solution.

An open question recently posed by Fawzi and Ferme [IEEE Transactions on Information Theory 2024], asks whether non-signaling (NS) assistance can increase the capacity of a broadcast channel (BC). We answer this question in the affirmative, by showing that for a certainK-receiver BC model, called Coordinated Multipoint broadcast (CoMP BC) that arises naturally in wireless networks, NS-assistance provides multiplicative gains in both capacity and degrees of freedom (DoF), even achievingK-fold improvements in extremal cases. Somewhat surprisingly, this is shown to be true even for 2-receiver broadcast channels that are semi-deterministic and/or degraded. In a CoMP BC,Bsingle-antenna transmitters, supported by a backhaul that allows them to share data, act as oneB-antenna transmitter, to send independent messages toKreceivers, each equipped with a single receive antenna. A fixed and globally known connectivity matrix specifies for each transmit antenna, the subset of receivers that are connected to (have a non-zero channel coefficient to) that antenna. Besides the connectivity, there is no channel state information at the transmitter. The receivers have perfect channel knowledge. We show that NS-assistance has no DoF advantage in a fully connected CoMP BC. The DoF region is fully characterized for a class of connectivity patterns associated with tree graphs, for which the classical sum-DoF value is shown to be the number of leaf nodes, while the NS-assisted sum-DoF value is the total number of all (non-root) nodes. For arbitrary connectivity patterns, the sum-capacity with NS-assistance is bounded above and below by the min-rank and triangle number of the connectivity matrix, respectively, leading to matching bounds in many cases, e.g., if min(B,K) ≤ 6. While translations to Gaussian settings are demonstrated, for simplicity most of our results are presented under noise-free, finite-field (Fq) models. Converse proofs for classical DoF are found by adapting the Aligned Images bounds to the finite field model. Converse bounds for NS-assisted DoF/capacity extend the same-marginals property to the BC with NS-assistance available to all parties. Beyond the BC setting, even stronger (unbounded) gains in capacity due to NS-assistance are established for certain ‘communication with side-information’ settings, such as the fading dirty paper channel.

This work explores the potential for improvement, due to non-signaling (NS) assistance, in the degrees of freedom (DoF) of a wireless network. The focus is on a$K$-user MISO BC, i.e., a broadcast channel where a transmitter, equipped with$K$antennas, sends independent messages to$K$receivers, each equipped with a single receive antenna. The network has triangular connectivity, so Receiver$k, k\in \{1, 2,\ldots, K\}$, sees in superposition with the signal sent from the$k^{tk}$transmit antenna, a linear combination of signals sent from the first$k$- 1 antennas, with random channel fading coefficients whose values are unknown to the transmitter but known to the receiver. Prior work has shown that such a MISO BC has$K$DoF with perfect channel state information at the transmitter (CSIT), but the DoF collapse to 1 under limited CSIT. The latter corresponds to the setting considered in this work. The main discovery is that NS assistance can increase the DoF of such a$K$-user wireless network, from 1 to$K$, fully compensating for limited CSIT. For simplicity, the result is presented here in a noise-free, finite-field$(\mathrm{F}_{q}$) model, where NS assistance enables a$K$-fold increase in Shannon capacity as$q\rightarrow\infty$.

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

While the exact capacity of large interference networks remains largely intractable, much progress has come about from alternative approaches. In particular, Generalized Degrees of Freedom (GDoF) region characterizations, combined with extremal network theory have significantly advanced the theoretical understanding of the basic scheme of treating interference as (Gaussian) noise (TIN) with power control, producing closed form solutions of the achievable GDoF region via implicit Fourier-Motzkin elimination of power-control variables, as well as extremal characterizations of the relative performance of TIN against other alternatives. The goal of this work is to develop this approach beyond TIN, especially to include successive interference cancellation (SIC). The first contribution is a closed form (i.e., depending only on the channel parameters) characterization of the achievable GDoF region for an SIC scheme for any specified decoding order at each receiver, and anyKuser network topology. This is followed by extremal network theoretic analysis, showing that the maximal sum-GDoF gain from SIC over TIN across all network topologies is precisely min(K,2L+1), when a total of up toLmessages can be successively decoded at every receiver. Remarkably, even when restricted to only weak interference settings where the benefits of SIC are not obvious, the extremal gain of SIC over TIN is shown to be significant, approachingL+1 for largeK. Networks that achieve these extremal gains are explicitly identified. The GDoF analysis is complemented with numerical simulations to illustrate how the insights translate to finite Signal-to-Noise Ratios.

Entanglement is known to significantly improve the performance (separately) of communication and detection schemes that utilize quantum resources. This work explores the simultaneous utility of quantum entanglement for (joint) communication and detection schemes, over channels that are convex combinations of identity, depolarization and erasure operators, both with perfect and imperfect entanglement assistance. The channel state is binary, rapidly time-varying and unknown to the transmitter. While the communication is delay-tolerant, allowing the use of arbitrarily long codewords to ensure reliable decoding, the channel state detection is required to be instantaneous. The detector is neither co-located with the transmitter, nor able to wait for the decoding in order to learn the transmitted waveform. The results of this work appear in the form of communication-rate vs instantaneous-detection-error tradeoffs, with and without quantum entanglement. Despite the challenges that place the two tasks at odds with each other, the results indicate that quantum entanglement can indeed be simultaneously and significantly beneficial for joint communication and instantaneous detection.

Linear computations over quantum many-to-one communication networks offer opportunities for communication cost improvements through schemes that exploit quantum entanglement among transmitters to achieve superdense coding gains, combined with classical techniques such as interference alignment. The problem becomes much more broadly accessible if suitable abstractions can be found for the underlying quantum functionality via classical black box models. This work formalizes such an abstraction in the form of an “N-sum box”, a black box generalization of a two-sum protocol of Song et al. with recent applications to N-server private information retrieval. The N-sum box has a communication cost of N qudits and classical output of a vector of$N~q$-ary digits linearly dependent (via an$N \times 2N$transfer matrix) on$2N$classical inputs distributed among N transmitters. We characterize which transfer matrices are feasible by our construction, both with and without the possibility of additional locally invertible classical operations at the transmitters and receivers. Furthermore, we provide a sample application to Cross-Subspace Alignment (CSA) schemes to obtain efficient instances of Quantum Private Information Retrieval (QPIR) and Quantum Secure Distributed Batch Matrix Multiplication (QSDBMM). We first describe N-sum boxes based on maximal stabilizers and we then consider non-maximal-stabilizer-based constructions to obtain an instance of Quantum Symmetric Private Information Retrieval.

In order to explore how blind interference alignment (BIA) schemes may take advantage of side-information in computation tasks, we study the degrees of freedom (DoF) of aKuser wireless network setting that arises in full-duplex wireless MapReduce applications. In this setting the receivers are assumed to have reconfigurable antennas and channel knowledge, while the transmitters have neither, i.e., the transmitters lack channel knowledge and are only equipped with conventional antennas. The central ingredient of the problem formulation is the message structure arising out of the Shuffle phase of MapReduce, whereby each transmitter has a subset of messages that need to be delivered to various receivers, and each receiver has a subset of messages available to it in advance as side-information. We approach this problem by decomposing it into distinctive stages that help identify key ingredients of the overall solution. The novel elements that emerge from the first stage, called broadcast with groupcast messages, include an outer maximum distance separable (MDS) code structure at the transmitter, and an algorithm for iteratively determining groupcast-optimal reconfigurable antenna switching patterns at the receiver to achieve intra-message (among the symbols of the same message) alignment. The next stage, called unicast with side-information, reveals optimal inter-message (among symbols of different messages) alignment patterns to exploit side-information, and by a relabeling of messages, connects to the desired MapReduce setting.

The optimal quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).Kclassical messages comprised of finite-field symbols are distributed acrossSservers, who also share quantum entanglement in advance. Each servers∈ [S] manipulates its quantum subsystemQsaccording to its own available classical messages and sendsQsto the receiver who then computes the sum of the messages based on a joint quantum measurement. The download cost from Servers∈ [S] is the logarithm of the dimension ofQs. The rateRis defined as the number of instances of the sum computed at the receiver, divided by the total download cost from all the servers. The main focus is on the symmetric setting withK= (Sα) messages where each message is replicated among a unique subset of α servers, and the answers from any β servers may be erased. If no entanglement is initially available to the receiver, then we show that the capacity (maximal rate) is preciselyC= max { min { 2(α−β)/S,S−2β/S}, α−β/S}. The capacity with arbitrary levels of prior entanglement (Δ0) between theSdata-servers and the receiver is also characterized, by including an auxiliary server (Server 0) that has no classical data, so that the communication cost from Server 0 is a proxy for the amount of receiver-side entanglement that is available in advance. The challenge on the converse side resides in the optimal application of the weak monotonicity property, while the achievability combines ideas from classical network coding and treating qudits as classical dits, as well as new constructions based on the N-sum box abstraction that rely on absolutely maximally entangled quantum states.

Building on recent constructions of Quantum Cross Subspace Alignment (QCSA) codes, this work develops a coding scheme for QEXSTPIR, i.e., classical private information retrieval with X -secure storage and$T$-private queries, over a quantum multiple access channel, that is resilient to any set of up to$E$erased servers (equivalently known as unresponsive servers, or stragglers). The scheme is accordingly labeled QECSA, with the ‘$\mathbf{E}$,indicating resilience to erased servers. The novelty of QECSA lies in achieving efficient E-straggler resilience on top of existing QCSA codes that already achieve X-secure storage, T- private queries, and distributed superdense coding gains for communication efficient decoding. The QECSA code structure may be broadly useful for problems such as quantum coded secure distributed computation, where security, straggler resilience, and distributed superdense coding gains are simultaneously required.

The quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).$K$- messages are distributed across$S$servers so that each server knows a subset of the messages. Each server$\mathrm{s}\in[S]$sends a quantum subsystem$\mathcal{Q}_{s}$to the receiver who computes the sum of the messages. The download cost from Server$s\in[S]$is the logarithm of the dimension of$\mathcal{Q}_{s}$. The rate$R$: is defined as the number of instances of the sum computed at the receiver, divided by the total download cost from all the servers. In the symmetric setting with$K=\left(_{\alpha}^{S}\right)$messages where each message is replicated among a unique subset of$\alpha$servers, and the answers from any$\beta$servers may be erased, the rate achieved is$R=\max \left\{\min \left\{\frac{2(\alpha-\beta)}{S}, 1-\frac{2 \beta}{S}\right\}, \frac{\alpha-\beta}{S}\right\}$.

Linear computation broadcast (LCBC) refers to a setting withddimensional data stored at a central server, whereKusers, each with some prior linear side-information, wish to compute various linear combinations of the data. For each computation instance, the data is represented as ad-dimensional vector with elements in a finite field Fpnwherepnis a power of a prime. The computation is to be performed many times, and the goal is to determine the minimum amount of information per computation instance that must be broadcast to satisfy all the users. The reciprocal of the optimal broadcast cost per computation instance is the capacity of LCBC. The capacity is known for up toK= 3 users. Since LCBC includes index coding as a special case, largeKsettings of LCBC are at least as hard as the index coding problem. As such the general LCBC problem is beyond our reach and we do not pursue it. Instead of the general setting (allcases), by focusing on thegenericsetting (almost allcases) this work shows that the generic capacity of the symmetric LCBC (where every user hasm’ dimensions of side-information andmdimensions of demand) for large number of users (K≥dsuffices) isCg= 1/Δg, where Δg= min { max{0,d-m′},dm/m+m′}, is the broadcast cost that is both achievable and unbeatable asymptotically almost surely for largen, among all LCBC instances with the given parametersp,K,d,m,m′. Relative to baseline schemes of random coding or separate transmissions,Cgshows an extremal gain by a factor ofKas a function of number of users, and by a factor of ≈d/4 as a function of data dimensions, when optimized over remaining parameters. For arbitrary number of users, the generic capacity of the symmetric LCBC is characterized within a factor of 2.

The K User Linear Computation Broadcast (LCBC) problem is comprised of d dimensional data (from$\mathbb {F}_{q}$), that is fully available to a central server, and K users, who require various linear computations of the data, and have prior knowledge of various linear functions of the data as side-information. The optimal broadcast cost is the minimum number of q-ary symbols to be broadcast by the server per computation instance, for every user to retrieve its desired computation. The reciprocal of the optimal broadcast cost is called the capacity. The main contribution of this paper is the exact capacity characterization for the$K=3$user LCBC for all cases, i.e., for arbitrary finite fields$\mathbb {F}_{q}$, arbitrary data dimension d, and arbitrary linear side-informations and demands at each user. A remarkable aspect of the converse (impossibility result) is that unlike the 2 user LCBC whose capacity was determined previously, the entropic formulation (where the entropies of demands and side-informations are specified, but not their functional forms) is insufficient to obtain a tight converse for the 3 user LCBC. Instead, the converse exploits functional submodularity. Notable aspects of achievability include sufficiency of vector linear coding schemes, subspace decompositions that parallel those found previously by Yao Wang in degrees of freedom (DoF) studies of wireless broadcast networks, and efficiency tradeoffs that lead to a constrained waterfilling solution. Random coding arguments are invoked to resolve compatibility issues that arise as each user has a different view of the subspace decomposition, conditioned on its own side-information.

The Σ-QMAC problem is introduced, involvingSservers,Kclassical (Fd) data streams, andTindependent quantum systems. Data stream Wk,k∈ [K] is replicated at a subset of servers W(k) ⊂ [S], and quantum system Qt,t∈ [T] is distributed among a subset of servers ε(t) ⊂ [S] such that Servers∈ ε(t) receives subsystem Qt,sof Qt= (Qt,s)s∈ε(t). Servers manipulate their quantum subsystems according to their data and send the subsystems to a receiver. The total download cost is Σt∈[T]Σs∈ε(t)logd|Qt,s| qudits, where |Q| is the dimension of Q. The states and measurements of (Qt)t∈[T]are required to be separable acrosst∈ [T] throughout, but for eacht∈ [T], thesubsystemsof Qtcan be prepared initially in an arbitrary (independent of data) entangled state, manipulated arbitrarily by the respective servers, and measured jointly by the receiver. From the measurements, the receiver must recover the sum of all data streams. Rate is defined as the number of dits (Fdsymbols) of the desired sum computed per qudit of download. The capacity of Σ-QMAC, i.e., the supremum of achievable rates is characterized for arbitrary data and entanglement distributions W, ε. For example, in the symmetric setting withK= (Sα) data-streams, each replicated among a distinct α-subset of [S], andT= (Sβ) quantum systems, each distributed among a distinct β-subset of [S], the capacity of the Σ-QMAC is 1/βTΣmin(α,β)γ=(α+β−S)+ min(β, 2γ) · (αγ) · (S−αβ−γ). Coding based on the N-sum box abstraction is optimal in every case. Notably, for everyS≠ 3 there exists an instance of the Σ-QMAC whereS-party entanglement is necessary to achieve the fully entangled capacity.

Linear computations over quantum many-to-one communication networks offer opportunities for communication cost improvements through schemes that exploit quantum entanglement among transmitters to achieve superdense coding gains, combined with classical techniques such as interference alignment. The problem becomes much more broadly accessible if suitable abstractions can be found for the underlying quantum functionality via classical black box models. This work formalizes such an abstraction in the form of an “N-sum box”, a black box generalization of a two-sum protocol of Song et al. with recent applications to$N$-server private information retrieval. The N- sum box has a communication cost of$N$qudits and classical output of a vector of$N$q-ary digits linearly dependent (via an N x 2N transfer matrix) on 2N classical inputs distributed among$N$transmitters. We characterize which transfer matrices are feasible by our construction, both with and without the possibility of additional locally invertible classical operations at the transmitters and receivers.

The problem of entanglement-assisted summation over a quantum multiple access channel ($\Sigma$-QMAC) is intro-duced, involving$S$servers,$K$classical$(\mathbb{F}_{d})$data streams that are replicated arbitrarily across various subsets of servers, and a receiver who wishes to compute the sum of the$K$data streams. Independent of the data, entangled quantum systems$\mathcal{Q}_{1}, \mathcal{Q}_{2}, \cdots, \mathcal{Q}_{S}$are prepared in advance and distributed to the corresponding servers. Each server$s, s\in[S]$locally manipulates its quantum system$\mathcal{Q}_{s}$according to its classical data and sends$\mathcal{Q}_{s}$to the receiver. The total communication cost is$\log_{d}\vert \mathcal{Q}_{1}\vert +\log_{d}\vert \mathcal{Q}_{2}\vert +\cdots+\log_{d}\vert \mathcal{Q}_{S}\vert$qudits, where$\vert \mathcal{Q}_{s}$denotes the dimension of$\mathcal{Q}_{s}$. Based on a measurement of the composite system$\mathcal{Q}_{1}\mathcal{Q}_{2}\cdots \mathcal{Q}_{S}$, the receiver must recover the desired sum. The rate thus achieved is defined as the number of dits$(\mathbf{F}_{d}$symbols) of the desired sum computed by the receiver per qudit (d-dimsional quantum system) of download. The capacity$C$is the supremum of the set of all achievable rates. As the main result of this work, the precise capacity of$\Sigma$-QMAC is obtained, from which it follows that quantum entanglements allow a factor of 2 gain in capacity (superdense coding gain) relative to capacity with no entanglements, in all cases (any$S, K, \mathbf{F}_{d}$and any data replication pattern) provided that the entanglement-assisted capacity does not exceed 1 dit/qudit (Holevo bound). Coding schemes based on a recent$N$-sum box abstraction are sufficient to achieve capacity.

The symmetric linear (over$\mathbb{F}_{p^{n}}$) computation broadcast (LCBC) problem considered in this work refers to a setting with$d$dimensional data stored at a central server, where$K$users, each with some$m^{\prime}$dimensional prior linear side-information, wish to retrieve various$m$dimensional linear combinations of the data. The goal is to determine the minimum amount of (potentially non-linear) coded information that must be broadcast to satisfy all the users. The reciprocal of the optimal broadcast cost is the capacity of LCBC. The capacity has been found previously for up to$K=3$users. Since LCBC includes index coding as a special case, LCBC settings with large number of users are at least as hard as the index coding problem. Instead of the general setting (all instances), here we make progress by focusing on the generic setting (almost all instances). For the LCBC with$d=4$dimensional data, and 1 dimensional demands and side-information$(m=m^{\prime}=1)$, we establish the generic capacity$C_{g}=\max(1/2,1/K)$, for any number of users$K$. This is the information theoretic capacity of almost all LCBC instances with$d=4, m=1, m^{\prime}=1$as$n\rightarrow\infty$for any field characteristic$p$and any number of users$K^{1}$

Introduced by Sadeh et al., the K-star-graph private information retrieval (PIR) problem, so-labeled because the storage graph is a star-graph with K leaf nodes, is comprised of K messages that are stored separately (one-each) at K dedicated servers, and a universal server that stores all K messages, for a total of K + 1 servers. While it is one of the simplest PIR settings to describe, the capacity CKof K-star-graph PIR is open for K ≥ 4. We study the critical K = 4 setting, for which prior work establishes the bounds 2/5 ≤ C4≤ 3/7. As our main contribution, we characterize the exact capacity of 4-star-graph PIR as C4= 5/12, thus improving upon both the prior lower-bound as well as the prior upper-bound. The main technical challenge resides in the new converse bound, whose non-trivial structure is deduced indirectly from the achievable schemes that emerge from the study of a finer tradeoff between the download costs from the dedicated servers versus the universal server. A sharp characterization of this tradeoff is also obtained for K = 4.

The symmetric$2\times 2\times 2$weak interference channel setting with heterogeneous hops is explored from a Generalized Degrees of Freedom (GDoF) perspective, especially under the robust assumption that limits the channel state information at the transmitters (CSIT) to finite precision. Specifically, in the$\ell ^{th}$hop,$\ell \in \{1,2\}$, both direct channels have strength$\alpha _{[\ell]}$, both cross channels have strength$\beta _{[\ell]}$(in logarithmic scale), and$\beta _{[\ell]}\leq 0.5\alpha _{[\ell]}$. Thus, while assuming symmetry within each hop, the model allows heterogeneity across hops$(\alpha _{[{1}]},\beta _{[{1}]}) \neq (\alpha _{[{2}]},\beta _{[{2}]})$. Because$\beta _{[\ell]}\leq 0.5\alpha _{[\ell]}$, each hop corresponds to an interference channel in the weak interference regime where power control and treating interference as noise are known to be sum-GDoF optimal in a 1-hop setting. The main result of this work is the exact sum-GDoF of the symmetric$2\times 2\times 2$weak interference channel for heterogeneous hops under finite precision CSIT. Compared to prior work that assumes homogeneous hops, heterogeneous hops require not only more sophisticated optimal rate-splitting arguments, but also quantize-and-forward ideas which were not needed for homogeneous hops. The converse proof similarly involves generalizations to accommodate hop heterogeneity, as well as new bounds beyond the homogeneous case, based on sum-set inequalities and aligned images arguments. Additional results include sum-GDoF for perfect CSIT, and for a natural dual strong interference setting where$\beta _{[\ell]}\geq 2\alpha _{[\ell]}$.

Motivated by an open problem and a conjecture, this work studies the problem of single server private information retrieval with private coded side information (PIR-PCSI) that was recently introduced by Heidarzadeh et al. The goal of PIR-PCSI is to allow a user to efficiently retrieve a desired message${W}_{{\theta }}$, which is one of$K$independent messages that are stored at a server, while utilizing private side information of a linear combination of a uniformly chosen size-$M$subset (${\mathcal {S}}\subset [K]$) of messages. The settings PIR-PCSI-I and PIR-PCSI-II correspond to the constraints that${\theta }$is generated uniformly from$[K]\setminus {\mathcal {S}}$, and$ {\mathcal {S}}$, respectively. In each case,$({\theta }, {\mathcal {S}})$must be kept private from the server. The capacity is defined as the supremum over message and field sizes, of achievable rates (number of bits of desired message retrieved per bit of download) and is characterized by Heidarzadeh et al. for PIR-PCSI-I in general, and for PIR-PCSI-II for$M>(K+1)/2$as$(K-M+1)^{-1}$. For$2\leq M\leq (K+1)/2$the capacity of PIR-PCSI-II remains open, and it is conjectured that even in this case the capacity is$(K-M+1)^{-1}$. We show the capacity of PIR-PCSI-II is equal to$2/K$for$2 \leq M \leq \frac {K+1}{2}$, which is strictly larger than the conjectured value, and does not depend on$M$within this parameter regime. Remarkably, half the side-information is found to be redundant. We also characterize the infimum capacity (infimum over fields instead of supremum), and the capacity with private coefficients. The results are generalized to PIR-PCSI-I ($\theta \in [K]\setminus \mathcal {S}$) and PIR-PCSI ($\theta \in [K]$) settings.

Using ideas from Generalized Degrees of Freedom (GDoF) analyses and extremal network theory, this work studies the extremal gain of optimal power control over binary (on/off) power control, especially in large interference networks, in search of new theoretical insights. Whereas numerical studies have already established that in most practical settings binary power control is close to optimal, the extremal analysis shows not only that there exist settings where the gain from optimal power control can be quite significant, but also bounds the extremal values of such gains from a GDoF perspective. As its main contribution, this work explicitly characterizes the extremal GDoF gain of optimal over binary power control as$\Theta (\sqrt {K})$for all$K$. In particular, the extremal gain is bounded between$\lfloor \sqrt {K}\rfloor $and$2.5\sqrt {K}$for every$K$. For$K=2,3,4,5,6$users, the precise extremal gain is found to be 1, 3/2, 2, 9/4 and 41/16, respectively. Networks shown to achieve the extremal gain may be interpreted as multi-tier heterogeneous networks. It is worthwhile to note that because of their focus on asymptotic analysis, the sharp characterizations of extremal gains are valuable primarily from a theoretical perspective, and not as contradictions to the conventional wisdom that binary power control is generally close to optimal in practical, non-asymptotic settings.

The problem of clock synchronization is studied in an arbitrary network ${\mathcal{G}} = ({\mathcal{V}},{\mathcal{E}})$ with $|{\mathcal{V}}|$ server nodes and $|{\mathcal{E}}|$ edges. Every pair of adjacent servers has a time discrepancy (edge information) that is only known approximately to one or both of the two adjacent servers. A master node aims to coordinate the otherwise independent clocks of the servers by eliminating the loop-wise offset surplus in the network. The goal is to minimize the communication cost between server nodes and the master node. Optimal schemes are found for the two cases where each time discrepancy is known by 1) both adjacent servers, and 2) only one of the adjacent servers. Notably, the scheme for the first case is robust to a straggler (slow or failed server). An algorithm that outperforms the natural (uncoded) baseline is proposed for the general setting that is a mix of the two cases. Classes of such mixed setting are identified where the algorithm represents the optimal solution.

The linear computation broadcast (LCBC) problem studied in this work is comprised of a d dimensional data vector X that is stored at a server, and 3 users, such that the kthuser, k ∈ [1 : 3], has 1 dimensional demand Wk= XTvkand 1 dimensional side-information ${\text{W}}_k^\prime{\text{ = }}{{\text{X}}^T}{\text{v}}_k^\prime$, that are arbitrary linear combinations of the data vector over a finite field ${\mathbb{F}_q}$. The optimal broadcast cost Δ* is the minimum amount of information that the server must broadcast in order to satisfy all three users' demands. The main result of this work is the exact characterization of Δ*, which is shown to only take one of the values: 0, 1, 1.5, 2, 3 in all cases. In contrast to the 2 user setting previously studied by Sun and Jafar, it turns out that in the 3 user LCBC, scalar linear coding is insufficient to construct optimal achievable schemes, and the entropic formulation (where the entropies of all subsets of $\left\{ {{{\mathbf{W}}_1},{{\mathbf{W}}_2},{{\mathbf{W}}_3},{\mathbf{W}}_1^\prime,{\mathbf{W}}_2^\prime,{\mathbf{W}}_3^\prime} \right\}$ are specified, but not their functional forms) is insufficient to obtain a tight converse. Instead, we need vector coding and functional submodularity, especially in those cases where Δ*= 1.5. Remarkably, for a given dimensional specification d, while Δ*can take different values depending on the realizations of ${{\mathbf{v}}_k},{\mathbf{v}}_k^\prime$, almost all realizations over a large field yield the same Δ*as a function of d, which happens to be 0, 1, 1.5, 2, 2, 3 for d = 1, 2, 3, 4, 5, 6+, respectively.

The increasing prevalence of massive datasets makes the outsourcing of storage and computation tasks to distributed servers a necessity. This raises a number of concerns regarding the security and integrity of stored information, the privacy of accessing desired information, the communication overhead of distributed systems, the latency, reliability, and complexity of distributed computing, and privacy in distributed training and learning systems. Recent breakthroughs from coding, communication, and information-theoretic perspectives have opened up exciting new research avenues for these topics. There are many theoretical and practical open problems. This Special Issue is dedicated to communication theory, coding theory, information theory, signal processing, and networking aspects of privacy in information retrieval, privacy in coded computing over distributed servers, and privacy in distributed learning.

Most of our lives are conducted in the cyberspace. The human notion of privacy translates into a cyber notion of privacy on many functions that take place in the cyberspace. This article focuses on three such functions: how to privately retrieve information from cyberspace (privacy in information retrieval), how to privately leverage large-scale distributed/parallel processing (privacy in distributed computing), and how to learn/train machine learning models from private data spread across multiple users (privacy in distributed (federated) learning). The article motivates each privacy setting, describes the problem formulation, summarizes breakthrough results in the history of each problem, and gives recent results and discusses some of the major ideas that emerged in each field. In addition, the cross-cutting techniques and interconnections between the three topics are discussed along with a set of open problems and challenges.

Blind Interference Alignment (BIA) schemes create and exploit channel coherence patterns without the knowledge of channel realizations at transmitters, while beamforming schemes rely primarily on channel knowledge available to the transmitters without regard to channel coherence patterns. In order to explore the compatibility of these disparate ideas and the possibility of synergistic gains, this work studies the Degrees of Freedom (DoF) of the 2-user${(M_{1}\times N_{1})(M_{2}\times N_{2})}$Multiple-Input Multiple-Output (MIMO) Interference Channel (IC) where Transmitter 1 is equipped with reconfigurable antennas and has no channel knowledge, while Transmitter 2 has partial channel knowledge but no reconfigurable antennas. Taking a fundamental dimensional analysis perspective, the main question is to identify which antenna configurations allow synergistic DoF gains. The main results of this work are two-fold. The first result identifies antenna configurations where both reconfigurable antennas and partial channel knowledge are individually beneficial, as those where$M_{1}< N_{1}< \min (M_{2},N_{2})$. The second result shows that synergistic gains exist in each of these settings, over the best known solutions that rely on either reconfigurable antennas or partial channel knowledge alone. Coding schemes that jointly exploit partial channel knowledge and reconfigurable antennas emerge as a byproduct of the analysis.

Under the assumption of perfect channel state information at the transmitters (CSIT), it is known that structured codes offer significant advantages for secure communication in an interference network, e.g., structured jamming signals based on lattice codes may allow a receiver to decode the sum of the jamming signal and the signal being jammed, even though they cannot be separately resolved due to secrecy constraints, subtract the aggregate jammed signal, and then proceed to decode desired codewords at lower power levels. To what extent are such benefits of structured codes fundamentally limited by uncertainty in CSIT? To answer this question, we explore what is perhaps the simplest setting where the question presents itself — a$Z$interference channel with secure communication. Using sum-set inequalities based on Aligned Images bounds we prove that the GDoF benefits of structured codes are lost completely under finite precision CSIT. The secure GDoF regions of the$Z$interference channel and the$Z$broadcast channel are obtained as a byproduct of the analysis.

We present a condition for 1/2 degree of freedom for each user in constant$K$-user single-antenna interference channels. This condition is sufficient for all and necessary for almost all channel matrices. Moreover, it applies to all channel topologies, i.e., to fully-connected channels as well as channels that have individual links absent, reflected by corresponding zeros in the channel matrix. Moreover, it captures the essence of interference alignment by virtue of being expressed in terms of a generic injectivity condition that guarantees separability of signal and interference. Finally, we provide codebook constructions achieving 1/2 degree of freedom for each user for all channel matrices satisfying the condition we identified.

Motivated by recent interest in federated submodel learning, this work explores the fundamental problem of privately reading from and writing to a database comprised of$K$files (submodels) that are stored across$N$distributed servers according to an$X$-secure threshold secret sharing scheme. One after another, various users wish to retrieve their desired file, locally process the information and then update the file in the distributed database while keeping the identity of their desired file private from any set of up to$T$colluding servers. The availability of servers changes over time, so elastic dropout resilience is required. The main contribution of this work is an adaptive scheme, called ACSA-RW, that takes advantage of all currently available servers to reduce its communication costs, fully updates the database after each write operation even though the database is only partially accessible due to server dropouts, and ensures a memoryless operation of the network in the sense that the storage structure is preserved and future users may remain oblivious of the past history of server dropouts. The ACSA-RW construction builds upon cross-subspace alignment (CSA) codes that were originally introduced for$X$-secure$T$-private information retrieval and have been shown to be natural solutions for secure distributed batch matrix multiplication problems. ACSA-RW achieves the desired private read and write functionality with elastic dropout resilience, matches the best results for private-read from PIR literature, improves significantly upon available baselines for private-write, reveals a striking symmetry between upload and download costs, and exploits storage redundancy to accommodate arbitrary read and write dropout servers up to certain threshold values. It also answers in the affirmative an open question by Kairouz et al. for the case of partially colluding servers (i.e., tolerating collusion up to a threshold) by exploiting synergistic gains from the joint design of private read and write operations.

The distributed matrix multiplication problem with an unknown number of stragglers is considered, where the goal is to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across$N$servers. There are up to$N - R$stragglers but the exact number is not known a priori. Motivated by reducing the computation load of each server, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing task for each server is separated into several subtasks, constructed based on Entangled Polynomial codes by Yu et al. The final results can be obtained from either a larger number of servers with a smaller amount of computation completed per server or a smaller number of servers with a larger amount of computation completed per server. The required finite field size of the proposed solution is less than$2N$. Moreover, the optimal design parameters such as the partitioning of the input matrices are discussed. Our constructions can also be generalized to other settings such as batch distributed matrix multiplication and secure distributed matrix multiplication.

Aligned-Images Sum-set Inequalities are used in this work to study the Generalized Degrees of Freedom (GDoF) of the symmetric layered multi-hop interference channel under the robust assumption that the channel state information at the transmitters (CSIT) is limited to finite precision. First, the sum-GDoF value is characterized for the$2\times 2\times 2$setting that is comprised of 2 sources, 2 relays, and 2 destinations. It is shown that the sum-GDoF does not improve even if perfect CSIT is allowed in the first hop, as long as the CSIT in the second hop is limited to finite precision. The sum GDoF characterization is then generalized to the$2\times 2\times \cdots \times 2$setting that is comprised of$L$hops. Remarkably, for large$L$, the sum-GDoF value approaches that of the one-hop broadcast channel that is obtained by full cooperation among the two transmitters of the last hop, with finite precision CSIT. Previous studies of multi-hop interference networks either identified sophisticated GDoF optimal schemes under perfect CSIT, such as aligned interference neutralization and network diagonalization, that are powerful in theory but too fragile to be practical, or studied robust achievable schemes like classical amplify/decode/compress-and-forward without claims of information-theoretic optimality. In contrast, under finite precision CSIT, we show that the benefits of fragile schemes are lost, while a combination of classical random coding schemes that are simpler and much more robust, namely a rate-splitting between decode-and-forward and amplify-and-forward, is shown to be GDoF optimal. As such, this work represents another step towards bridging the gap between theory (optimality) and practice (robustness) with the aid of Aligned-Images Sum-set Inequalities.

In order to discover larger networks and parameter regimes where sharp Generalized Degrees of Freedom (GDoF) characterizations may be found based on the optimality of robust schemes for interference and broadcast networks with channel state information at the transmitters (CSIT) limited to finite precision, we explore the impact of secrecy constraints. In the absence of secrecy constraints, the largest such parameter regime for$K$user interference networks is the CTIN regime (so named for theConvexity of the GDoF region achieved by Treating Interference as Noise (TIN)) originally discovered by Yi and Caire, whose optimality was established by Chanet al.For the corresponding broadcast networks the largest regime is the SLS (Simple Layered Superposition) regime discovered by Davoodi and Jafar, but only for small networks with$K\leq 3$users. By including secrecy constraints, we identify much larger regimes, the STIN regime and the SLS regime, where GDoF are fully characterized for arbitrary number of users under finite precision CSIT, for interference networks and broadcast networks, respectively. The optimal achievable scheme in both cases is based on TIN along with power control and jamming. Proofs of optimality rely on a combination of secrecy constraints and Aligned Images sum-set inequalities.

Sum-set inequalities based on Aligned-Images bounds have been recently introduced as essential elements of converse proofs for asymptotic/approximate wireless network capacity characterizations under robust assumptions, i.e., assumptions that limit channel knowledge at the transmitters to finite precision. While these sum-set inequalities have produced robust Generalized Degrees of Freedom (GDoF) results for various wireless networks, their scope and limitations in general are not well understood. To explore these limitations, in this work we study the robust secure GDoF of a symmetric 3-user many-to-one interference channel. We identify regimes where existing sum-set inequalities are sufficient, settling the GDoF for those settings. For the remaining regime we conjecture the form of new sum-set inequalities that may be needed, whose validity remains an open problem for future work.

The problem of (information-theoretic) X-secure T-private federated submodel learning represents a setting where a large scale machine learning model is partitioned into K submodels and stored across N distributed servers according to an X-secure threshold secret sharing scheme. Various users wish to successively train (update) the submodel that is most relevant to their local data while keeping the identity of their relevant submodel private from any set of up to T colluding servers. Inspired by the idea of cross-subspace alignment (CSA) for X - secure T -private information retrieval, we propose a novel CSA-RW (read-write) scheme for efficiently (in communication cost) and privately reading from and writing to a distributed database. CSA-RW improves significantly upon available baselines from prior work and is shown to be asymptotically/approximately optimal in download/upload cost. It also answers an open question previously noted by Kairouz et al. by exploiting synergistic gains from the joint design of private read-write.

The distributed matrix multiplication problem with unknown number of stragglers is considered, where the goal is to allow a master to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across$N$servers. We assume there are at most$N-R$stragglers but the exact number is not known a priori. Motivated by reducing the latency, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing job for each server is separated into 2 layers, constructed based on Entangled Polynomial (EP) codes by Yu el al. The final results can be obtained when a larger number of servers complete the task from the first layer or a smaller number of servers complete the tasks from both 2 layers. The required finite field size of the proposed solution is less than$2N$. Moreover, the optimal partitioning of the input matrices is discussed. Our constructions can also be generalized to batch matrix multiplication.

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

Coded distributed matrix multiplication (CDMM) schemes, such as MatDot codes, seek efficient ways to distribute matrix multiplication task(s) to a set of N distributed servers so that the answers returned from any R servers are sufficient to recover the desired product(s). For example, to compute the product of matrices U, V, MatDot codes partition each matrix into $p\gt1$ sub-matrices to create smaller coded computation tasks that reduce the upload/storage at each server by $1 / p$, such that UV can be recovered from the answers returned by any $R=2 p-1$ servers. An important concern in CDMM is to reduce the recovery threshold R for a given storage/upload constraint. Recently, Jeong et al. introduced Approximate MatDot (AMD) codes that are shown to improve the recovery threshold by a factor of nearly 2, from $2 p-1$ to p. A key observation that motivates our work is that the storage/upload required for approximate computing depends not only on the dimensions of the (coded) sub-matrices that are assigned to each server, but also on their precision levels - a critical aspect that is not explored by Jeong et al. Our main contribution is a rudimentary asymptotic dimensional analysis of AMD codes inspired by the Generalized Degrees of Freedom (GDoF) framework previously developed for wireless networks, which indicates that for the same upload/storage, once the precision levels of the task assignments are accounted for, AMD codes are not better than a replication scheme which assigns the full computation task to every server. The dimensional analysis is supported by simple numerical experiments.

The robust principles of treating interference as noise (TIN) when it is sufficiently weak, and avoiding it when it is not, form the background of this work. Combining TIN with the topological interference management (TIM) framework that identifies optimal interference avoidance schemes, we formulate a TIM-TIN problem for multilevel topological interference management, wherein only a coarse knowledge of channel strengths and no knowledge of channel phases is available to transmitters. To address the TIM-TIN problem, we first propose an analytical baseline approach, which decomposes a network into TIN and TIM components, allocates the signal power levels to each user in the TIN component, allocates signal vector space dimensions to each user in the TIM component, and guarantees that the product of the two is an achievable number of signal dimensions available to each user in the original network. Next, a distributed numerical algorithm called ZEST is developed. The convergence of the algorithm is demonstrated, leading to the duality of the TIM-TIN problem in terms of generalized degrees-of-freedom (GDoF). Numerical results are also provided to demonstrate the superior sum-rate performance and fast convergence of ZEST.

The goal of coded distributed computation is to efficiently distribute a computation task, such as matrix multiplication, N-linear computation, or multivariate polynomial evaluation, across S servers through a coding scheme, such that the response from any R servers ( R is called the recovery threshold) is sufficient for the user to recover the desired computed value. Current state-of-art approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC) for N-linear computations or multivariate polynomial evaluations). We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of secure and private information retrieval. CSA codes are characterized by a Cauchy-Vandermonde matrix structure that facilitates interference alignment along Vandermonde terms, while the desired computations remain resolvable along the Cauchy terms. These codes are shown to unify, generalize and improve upon the state-of-art codes for distributed computing. First we introduce CSA codes for matrix multiplication, which yield LCC codes as a special case, and are shown to outperform LCC codes in general in download-limited settings. While matrix-partitioning approaches (EP codes) for distributed matrix multiplication have the advantage of flexible server computation latency, batch processing approaches (CSA, LCC) have significant advantages in communication costs as well as encoding and decoding complexity per matrix multiplication. In order to combine the benefits of these approaches, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches and demonstrate synergistic gains due to cross subspace alignment. Finally, we introduce N-CSA codes for N-linear distributed batch computations and multivariate batch polynomial evaluations. N-CSA codes include LCC codes as a special case, and are in general capable of outperforming LCC codes in download-constrained settings by upto a factor of N. Generalizations of N-CSA codes to include X-secure data and B-byzantine servers are also provided.

The problem of secure distributed batch matrix multiplication (SDBMM) studies the communication efficiency of retrieving a sequence of desired matrix products${\mathbf{AB}} = ({\mathbf{A}}_{1}{\mathbf{B}}_{1},\,\,{\mathbf{A}}_{2}{\mathbf{B}}_{2},\,\,\cdots,\,\,{\mathbf{A}}_{S}{\mathbf{B}}_{S})$from$N$distributed servers where the constituent matrices${\mathbf{A}}=({\mathbf{A}}_{1}, {\mathbf{A}}_{2}, \cdots, {\mathbf{A}}_{S})$and${\mathbf{B}}=({\mathbf{B}}_{1}, {\mathbf{B}}_{2},\cdots,{\mathbf{B}}_{S})$are stored in$X$-secure coded form, i.e., any group of up to$X$colluding servers learn nothing about$\mathbf{ A, B}$. It is assumed that${\mathbf{A}}_{s}\in \mathbb {F}_{q}^{L\times K}, {\mathbf{B}}_{s}\in \mathbb {F}_{q}^{K\times M}, s\in \{1,2,\cdots, S\}$are uniformly and independently distributed and$\mathbb {F}_{q}$is a large finite field. The rate of an SDBMM scheme is defined as the ratio of the number of bits of desired information that is retrieved, to the total number of bits downloaded on average. The supremum of achievable rates is called the capacity of SDBMM. In this work we explore the capacity of SDBMM, as well as several of its variants, e.g., where the user may already have either${\mathbf{A}}$or${\mathbf{B}}$available as side-information, and/or where the security constraint for either${\mathbf{A}}$or${\mathbf{B}}$may be relaxed. We obtain converse bounds, as well as achievable schemes for various cases of SDBMM, depending on the$L, K, M, N, X$parameters, and identify parameter regimes where these bounds match. In particular, the capacity for securely computing a batch of outer products of two vectors is$(1-X/N)^{+}$, for a batch of inner products of two (long) vectors the capacity approaches$(1-2X/N)^{+}$as the length of the vectors approaches infinity, and in general for sufficiently large$K$(e.g.,$K > 2\min (L,M)$), the capacity$C$is bounded as$(1-2X/N)^{+}\leq C < (1-X/N)^{+}$. A remarkable aspect of our upper bounds is a connection between SDBMM and a form of private information retrieval (PIR) problem, known as multi-message$X$-secure$T$-private information retrieval (MM-XSTPIR). Notable features of our achievable schemes include the use of cross-subspace alignment and a transformation argument that converts a scalar multiplication problem into a scalar addition problem, allowing a surprisingly efficient solution.

The goal of coded distributed batch matrix multiplication is to efficiently multiply L instances of λ x κ matrices, A = (A1, · · · , AL), with L instances of κ x μ matrices B = (B1, · · · , BL), by distributing the computation across S servers, such that the response from any R servers (R is called the recovery threshold) is sufficient to compute the L matrix products, AB = (A1B1, A2B2, · · · , ALBL). Existing solutions either compute each AlBl one at a time by partitioning individual matrices and coding across these partitions, or rely only on batch processing, i.e., coding across the batch of matrices without any matrix partitioning. The state-of-art for matrix-partitioning and batch processing approaches is represented by Entangled Polynomial Codes (EP codes), and Lagrange Coded Computing (LCC), respectively. In order to combine the benefits of the two approaches, we propose Generalized Cross-Subspace Alignment Codes (GCSA codes) that unify, generalize and improve upon the state of art. GCSA codes bridge the two extremes by efficiently combining both matrix-partitioning and batch processing, and offer flexibility in how much of each approach is used. Both EP codes and LCC codes can be recovered as special cases of GCSA codes. Remarkably, even without matrix partitioning, GCSA codes demonstrate an advantage over LCC codes in downloadconstrained settings. This is due to cross-subspace alignment, characterized by a Cauchy-Vandermonde code structure that aligns interference along Vandermonde terms, while the desired matrix products remain resolvable along Cauchy terms.

Under the assumption of perfect channel state information at the transmitters (CSIT), it is known that structured codes offer significant advantages in an interference network, e.g., lattice alignment allows a receiver to directly decode the sum of aligned interfering codewords at higher power levels even though individual codewords are not resolvable, subtract the aggregate interference, and then proceed to decode desired codewords at lower power levels. To what extent are such benefits of structured codes fundamentally limited by uncertainty in CSIT? To answer this question, we explore what is perhaps the simplest setting where the question presents itself - a Z interference channel with secure communication. Using sum-set inequalities based on Aligned Images bounds we prove that the GDoF benefits of structured codes are lost completely under finite precision CSIT. The secure GDoF region of the Z interference channel is obtained as a byproduct of the analysis.

A secure multi-party batch matrix multiplication problem (SMBMM) is considered, where the goal is to allow a master to efficiently compute the pairwise products of two batches of massive matrices, by distributing the computation across S servers. Any X colluding servers gain no information about the input, and the master gains no additional information about the input beyond the product. A solution called Generalized Cross Subspace Alignment codes with Noise Alignment (GCSA- NA) is proposed in this work, based on cross-subspace alignment codes. The state of art solution to SMBMM is a coding scheme called polynomial sharing (PS) that was proposed by Nodehi and Maddah-Ali. GCSA-NA outperforms PS codes in several key aspects - more efficient and secure inter-server communication, lower latency, flexible inter-server network topology, efficient batch processing, and tolerance to stragglers.

In this work, we study the impact of imperfect sharing of the Channel State Information (CSI) available at the transmitters on a Network MIMO setting in which a set of M transmit antennas, possibly not co-located, jointly serve two multi-antenna users endowed with N1and N2antennas, respectively. We consider the case where only a subset of k transmit antennas have access to perfect CSI, whereas the other M - k transmit antennas have only access to finite precision CSI. The analysis of this configuration aims to answer the question of how much an extra informed antenna can help. We model this scenario as a Decentralized MIMO Broadcast Channel (BC) and characterize the Degrees-of-Freedom (DoF) region, showing that only k = max(N1, N2) antennas with perfect CSI are needed to achieve the DoF of the conventional BC with ubiquitous perfect CSI.

Significant progress has been made recently in Generalized Degrees of Freedom (GDoF) characterizations of wireless interference channels (IC) and broadcast channels (BC) under the assumption of finite precision channel state information at the transmitters (CSIT), especially for smaller or highly symmetric network settings. A critical barrier in extending these results to larger and asymmetric networks is the inherent combinatorial complexity of such networks. Motivated by other fields such as extremal combinatorics and extremal graph theory, we explore the possibility of an extremal network theory, i.e., a study of extremal networks within particular regimes of interest. As our test application, we study the GDoF benefits of transmitter cooperation in a K user IC over the simple scheme of power control and treating interference as Gaussian noise (TIN) for three regimes of interest - a TIN regime identified by Geng et al. where TIN was shown to be GDoF optimal for the K user interference channel, a CTIN regime identified by Vi and Caire where the GDoF region achievable by TIN is convex without time-sharing, and an SLS regime identified by Davoodi and Jafar where a simple layered superposition (SLS) scheme is shown to be optimal in the K user MISO BC, albeit only for K ≤ 3. The SLS regime includes the CTIN regime, and the CTIN regime includes the TIN regime. As our first result, we show that under finite precision CSIT, TIN is GDoF optimal for the K user IC throughout the CTIN regime. Furthermore, under finite precision CSIT, appealing to extremal network theory we obtain the following results. In the TIN regime as well as the CTIN regime, we show that the extremal GDoF gain from transmitter cooperation over TIN is bounded regardless of the number of users. In fact, the gain is exactly a factor of 3/2 in the TIN regime, and 2 - 1/K in the CTIN regime, for arbitrary number of users K > 1. However, in the SLS regime, the gain is ⊖(log2(K)), i.e., it scales logarithmically with the number of users.

The private search problem is introduced, where a dataset comprised of L i.i.d. records is replicated across N non-colluding servers, and a user wishes to search for all records that match a privately chosen value, without revealing any information about the chosen value to any individual server. Each record contains P symbols, and each symbol takes values uniformly and independently from an alphabet of size K. Considering the large number of records in modern datasets, it is assumed that L is much larger than the alphabet size K. The capacity of private search is the maximum number of bits of desired information that can be retrieved per bit of download. The asymptotic (large K) capacity of private search is shown to be 1 - 1/N, even when the scope of private search is further generalized to allow OR search, AND search, NOT search and sequence search. The results are based on the asymptotic behavior of a new converse bound for private information retrieval with arbitrarily dependent messages. The asymptotic behavior is also applicable to T-colluding servers or (N, T)-MDS coded servers.

We consider the problem of T-Private Information Retrieval with private side information (TPIR-PSI). In this problem, N replicated databases store K independent messages, and a user, equipped with a local cache that holds M messages as side information, wishes to retrieve one of the other K - M messages. The desired message index and the side information must remain jointly private even if any T of the N databases collude. We show that the capacity of TPIR-PSI is (1+ T/N + ⋯ +(T/N)K-M-1)-1. As a special case obtained by setting T = 1, this result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We also consider the problem of symmetric-TPIR with private side information (STPIR-PSI), where the answers from all N databases reveal no information about any other message besides the desired message. We show that the capacity of STPIR-PSI is 1 - T/N if the databases have access to common randomness (not available to the user) that is independent of the messages, in an amount that is at least T/N -T bits per desired message bit. Otherwise, the capacity of STPIR-PSI is zero.

The degrees of freedom (DoF) region is characterized for the 2-user multiple input multiple output (MIMO) broadcast channel (BC), where the transmitter is equipped with M antennas, the two receivers are equipped with N1and N2antennas, and the levels of channel state information at the transmitter (CSIT) for the two users are parameterized by β1, β2, respectively. The achievability of the DoF region was established by Hao, Rassouli and Clerckx, but no proof of optimality was heretofore available. The proof of optimality is provided in this work with the aid of sum-set inequalities based on the aligned image sets (AIS) approach.

The problem of private information retrieval with graph-based replicated storage was recently introduced by Raviv, Tamo and Yaakobi. Its capacity remains open in almost all cases. In this work the asymptotic (large number of messages) capacity of this problem is studied along with its generalizations to include arbitrary T -privacy and X-security constraints, where the privacy of the user must be protected against any set of up to T colluding servers and the security of the stored data must be protected against any set of up to X colluding servers. A general achievable scheme for arbitrary storage patterns is presented that achieves the rate (ρmin-X -T )/N, where N is the total number of servers, and each message is replicated at least ρmintimes. Notably, the scheme makes use of a special structure inspired by dual Generalized Reed Solomon (GRS) codes. A general converse is also presented. The two bounds are shown to match for many settings, including symmetric storage patterns. Finally, the asymptotic capacity is fully characterized for the case without security constraints (X = 0) for arbitrary storage patterns provided that each message is replicated no more than T + 2 times. As an example of this result, consider PIR with arbitrary graph based storage (T = 1, X = 0) where every message is replicated at exactly 3 servers. For this 3-replicated storage setting, the asymptotic capacity is equal to 2/ν2(G) where ν2(G) is the maximum size of a 2-matching in a storage graph G[V, E]. In this undirected graph, the vertices V correspond to the set of servers, and there is an edge uv ∈ E between vertices u, v only if a subset of messages is replicated at both servers u and v.

The problem of X-secure T-private information retrieval from MDS coded storage is studied in this paper, where the user wishes to privately retrieve one out of K independent messages that are distributed over N servers according to an MDS code. It is guaranteed that any group of up to X colluding servers learn nothing about the messages and that any group of up to T colluding servers learn nothing about the identity of desired message. A lower bound of achievable rates is proved by presenting a novel scheme based on cross-subspace alignment and a successive decoding with interference cancellation strategy. For large number of messages (K → ∞) the achieved rate, which we conjecture to be optimal, improves upon the best known rates previously reported in the literature by Raviv and Karpuk, and generalizes an achievable rate for MDS-TPIR previously found by Freij-Hollanti et al. that is also conjectured to be asymptotically optimal. The setting is then expanded to allow unresponsive and Byzantine servers. Finally, the scheme is applied to find a new lower convex hull of (download, upload) pairs of secure and private distributed matrix multiplication that generalizes, and in certain asymptotic settings strictly improves upon the best known previous results.

The two-user computation broadcast problem is introduced as the setting where User 1 wants message W1and has side-information W1', User 2 wants message W2and has side-information (W2', and W1, W1', W2, W2') may have arbitrary dependencies. The rate of a computation broadcast scheme is defined as the ratio H(W1, W2)/H(S), where S is the information broadcast to both users to simultaneously satisfy their demands. The supremum of achievable rates is called the capacity of computation broadcast CCB. It is shown that CCB≤ H(W1, W2)/[H(W1|W1')+H(W2|W2')- min (I(W1; W2, W2'|W1'), I(W2; W1, W1'|W2'))] . For the linear computation broadcast problem, where W1, W1', W2, W2' are comprised of arbitrary linear combinations of a basis set of independent symbols, the bound is shown to be tight. For non-linear computation broadcast, it is shown that this bound is not tight in general. Examples are provided to prove that different instances of computation broadcast that have the same entropic structure, i.e., the same entropy for all subsets of {W1, W1', W2, W2'}, can have different capacities. Thus, extra-entropic structure matters even for two-user computation broadcast. The significance of extra-entropic structure is further explored through a class of non-linear computation broadcast problems where the extremal values of capacity are shown to correspond to minimally and maximally structured problems within that class.

A locally decodable code (LDC) maps K source symbols, each of size Lwbits, to M coded symbols, each of size Lxbits, such that each source symbol can be decoded from N ≤ M coded symbols. A perfectly smooth LDC further requires that each coded symbol is uniformly accessed when we decode any one of the messages. The ratio Lw/Lxis called the symbol rate of an LDC. The highest possible symbol rate for a class of LDCs is called the capacity of that class. It is shown that given K, N, the maximum value of capacity of perfectly smooth LDCs, maximized over all code lengths M, is C* = N(1 + 1/N 1/N2+ · · · 1/NK-1)-1. Furthermore, given K, N, the minimum code length M for which the capacity of a perfectly smooth LDC is C* is shown to be M = NK. Both of these results generalize to a broader class of LDCs, called universal LDCs. The results are then translated into the context of PIRmax, i.e., Private Information Retrieval subject to maximum (rather than average) download cost metric. It is shown that the minimum upload cost of capacity achieving PIRmax schemes is (K - 1) log N. The results also generalize to a variation of the PIR problem, known as Repudiative Information Retrieval (RIR).

The Generalized Degrees of Freedom (GDoF) of the two user interference channel are characterized for all parameter regimes under the assumption of finite precision channel state information at the transmitters (CSIT), when a limited amount of (half-duplex or full-duplex) cooperation is allowed between the transmitters in the form of π DoF of shared messages. In all cases, the number of over-the-air bits that each cooperation bit buys is shown to be equal to either 0, 1, 1/2 or 1/3. The most interesting aspect of the result is the 1/3 slope, which appears only under finite precision CSIT and strong interference, and as such has not been encountered in previous studies that invariably assumed perfect CSIT. Indeed, the achievability and converse for the parameter regimes with 1/3 slope are the most challenging aspects of this work. In particular, the converse relies on non-trivial applications of Aligned Images bounds.

The Generalized Degrees of Freedom (GDoF) of the two user interference channel are characterized for all parameter regimes under the assumption of finite precision channel state information at the transmitters (CSIT), when a limited amount of cooperation is allowed between the transmitters in the form of π DoF of shared messages. In all cases, the number of over-the-air bits that each cooperation bit buys is shown to be equal to either 0, 1, 1/2 or 1/3.

The two-user computation broadcast problem is introduced as the setting where user 1 wants message W1and has side information W'1, user 2 wants message W2and has side information W2', and (W1, W'1, W2, W'2) may have arbitrary dependencies. The goal is to minimize the entropy H(S) of the broadcast information S that simultaneously satisfies both users' demands. It is shown that H(S) > H(W1|W'1) + H(W2|W'2)-min (I(W1; W2, W'2|W'1), I (W2; W1, W'1|W'2)). Furthermore, for the linear computation broadcast problem, where W1, W'1, W2, W'2are comprised of arbitrary linear combinations of a basis set of independent symbols, the bound is shown to be tight.

We study the GDoF gain of transmitter cooperation (TC) over power control and treating interference as noise (TIN) for 3 regimes - a TIN regime where TIN is GDoF optimal for the K user IC, a CTIN regime where the GDoF region achieved by TIN is convex without time-sharing, and an SLS regime where a simple layered superposition scheme is optimal in the K user MISO BC for K≤3. Under finite precision CSIT, appealing to extremal network theory we obtain the following results. In the TIN regime as well as the CTIN regime, the extremal GDoF gain from TC over TIN is Θ (1). In fact, the gain is at most a factor of 2 in the CTIN regime and exactly 3=2 in the TIN regime for K > 1. In the SLS regime, the extremal GDoF gain is Θ(log(K)).

The degrees of freedom (DoF) region is characterized for the 2-user multiple input multiple output (MIMO) broadcast channel (BC), where the transmitter is equipped with M antennas, the two receivers are equipped with N1and N2antennas, and the levels of channel state information at the transmitter (CSIT) for the two users are parameterized by β1, β2, respectively. The achievability of the DoF region was established by Hao, Rassouli and Clerckx, but no proof of optimality was heretofore available. The proof of optimality is provided in this work with the aid of sum-set inequalities based on the aligned image sets (AIS) approach.

The recipients of the 2018 IEEE Communications Society and Information Theory Society Joint Paper Award are Arash Gholami Davoodi and Syed A. Jafar for the paper “Aligned Image Sets Under Channel Uncertainty: Settling Conjectures on the Collapse of Degrees of Freedom Under Finite Precision CSIT” which appeared in the IEEE Transactions on Information Theory, vol. 62, no. 10, pp. 5603–5618, October 2016.

The generalized degrees of freedom of the two-user symmetric multiple input multiple output interference channel are characterized as a function of the channel strength levels and the level of channel state information at the transmitters. In this symmetric setting, each transmitter is equipped with M antennas, each receiver is equipped with N antennas, and both cross links have the same strength parameter α and the same channel uncertainty parameter β. The main challenge resides in the proof of the outer bound which is accomplished by a generalization of the aligned image sets approach.

Generalized degrees of freedom (GDoF) are characterized for the symmetric K-user multiple-input multiple-output interference channel under the assumption that the channel-state information at the transmitters (CSITs) is limited to finite precision. In this symmetric setting, each transmitter is equipped with M antennas, each receiver is equipped with N antennas, each desired channel (i.e., a channel between a transmit antenna and a receive antenna belonging to the same user) has strength ~P, while each undesired channel has strength ~Pα, where P is a nominal SNR parameter. The result generalizes a previous GDoF characterization for the SISO setting (M = N = 1) and is enabled by a significant extension of the aligned image sets bound that is broadly useful. GDoF per user take the form of a W-curve with respect to α for fixed values of M and N. Under finite precision CSIT, in spite of the presence of multiple antennas, all the benefits of interference alignment are lost.

We study the K = 3 user multiple input single output (MISO) broadcast channel (BC) with M = 3 antennas at the transmitter and 1 antenna at each receiver, from the generalized degrees of freedom (GDoF) perspective, under the assumption that the channel state information at the transmitter (CSIT) is limited to the finite precision. In particular, our goal is to identify a parameter regime where a simple layered superposition (SLS) coding scheme achieves the entire GDoF region. With αijrepresenting the channel strength parameter for the link from the jthantenna of the transmitter to the jthreceiver, we prove that the SLS is GDoF optimal without the need for time-sharing if max(αki, αim) ≤ αiiand αki+ αim≤ αii+ αkmfor all i, k ∈ [3], m ∈ [M]. The GDoF region under this condition is a convex polyhedron. The result generalizes to arbitrary M ≥ 3.

X-secure and T-private information retrieval (XSTPIR) is a form of private information retrieval where data security is guaranteed against collusion among up to X servers and the user's privacy is guaranteed against collusion among up to T servers. The capacity of XSTPIR is characterized for an arbitrary number of servers N and arbitrary security and privacy thresholds X and T, in the limit as the number of messages K → ∞. Capacity is also characterized for any number of messages if either N = 3, X = T = 1 or if N ≤ X +T. Insights are drawn from these results, about aligning versus decoding noise, dependence of PIR rate on field size, and robustness to symmetric security constraints. In particular, the idea of cross subspace alignment, i.e., introducing a subspace dependence between Reed-Solomon code parameters, emerges as the optimal way to align undesired terms while keeping desired terms resolvable.

Private information retrieval (PIR) is the problem of retrieving, as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K - 1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N -1) bits per desired message bit. Otherwise, if the amount of common randomness is less than 1/(N -1) bits per message bit, then the capacity of SPIR is zero. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.

We introduce the problem of private computation, comprised of N distributed and non-colluding servers, K independent datasets, and a user who wants to compute a function of the datasets privately, i.e., without revealing which function he wants to compute, to any individual server. This private computation problem is a strict generalization of the private information retrieval (PIR) problem, obtained by expanding the PIR message set (which consists of only independent messages) to also include functions of those messages. The capacity of private computation, C, is defined as the maximum number of bits of the desired function that can be retrieved per bit of total download from all servers. We characterize the capacity of private computation, for N servers and K independent datasets that are replicated at each server, when the functions to be computed are arbitrary linear combinations of the datasets. Surprisingly, the capacity, C=(1+1/N+ ⋯ +1/NK-1)-1, matches the capacity of PIR with N servers and K messages. Thus, allowing arbitrary linear computations does not reduce the communication rate compared to pure dataset retrieval. The same insight is shown to hold even for arbitrary non-linear computations when the number of datasets K → ∞.

We study K-user Interference Channels (IC), K-user MIMO ICs and K-user MIMO Broadcast Channels (BC) with generic channel coefficients where, for some channel coefficients the channel state information at the transmitter(s) (CSIT) is perfect, while for the others the CSIT is available only to finite precision. By generalizing the Aligned Image Sets (AIS) bound we are able to characterize the necessary and sufficient condition for the collapse of sum degrees of freedom (DoF) to 1 in each case. For example, the K=3 user interference channel has sum DoF=1 if and only if the CSIT for at least one of the undesired channel coefficients is limited to finite precision.

We introduce the problem of private computation, comprised of N distributed and non-colluding servers, K datasets, and a user who wants to compute a function of the datasets privately, i.e., without revealing which function he wants to compute to any individual server. This private computation problem is a strict generalization of the private information retrieval (PIR) problem, by expanding the PIR message set (which consists of only independent messages) to also include functions of those messages. The capacity of private computation, C, is defined as the maximum number of bits of the desired function that can be retrieved per bit of total download from all servers. We characterize the capacity of an elemental private computation setting, with N = 2 servers and K = 2 datasets that are replicated at each server, for linear computations. Surprisingly, the capacity, C = 2/3, matches the capacity of PIR with N = 2 servers and K = 2 messages. Thus, allowing arbitrary linear computations does not reduce the communication rate compared to pure dataset retrieval. The same insight is shown to hold at the opposite extreme where the number of datasets K → ∞, the number of servers N can be arbitrary, and arbitrary (including non-linear) computations are allowed.

The private search problem is introduced, where a dataset comprised of L i.i.d. records is replicated across N non-colluding servers, each record takes values uniformly from an alphabet of size K, and a user wishes to search for all records that match a privately chosen value, without revealing any information about the chosen value to any individual server. The capacity of private search is the maximum number of bits of desired information that can be retrieved per bit of download. The asymptotic (large K) capacity of private search is shown to be 1-1/N, even as the scope of private search is further generalized to allow approximate (OR) search over a number of realizations that grows with K. The results are based on the asymptotic behavior of a new converse bound for private information retrieval with arbitrarily dependent messages.

This paper obtains the first degrees of freedom (DoFs) bound that is provably sensitive to network coherence time, i.e., coherence time in an interference network, where all channels experience the same coherence patterns. This is accomplished by a novel adaptation of the aligned image sets bound and settles various open problems noted previously by Naderi and Avestimehr and by Gou et al. For example, a necessary and sufficient condition is obtained for the optimality of 1/2 DoF per user in a partially connected interference network, where the channel state information at the receivers (CSIRs) is perfect, the channel state information at the transmitters (CSITs) is instantaneous but limited to finite precision, and the network coherence time is Tc=1. The surprising insight that emerges is that even with perfect CSIR and instantaneous finite precision CSIT, the network coherence time matters, i.e., it has a DoF impact.

For the $K=2$ user MISO BC, i.e., the wireless broadcast channel where a transmitter equipped with $K=2$ antennas sends independent messages to $K=2$ receivers each of which is equipped with a single antenna, the generalized degrees of freedom (GDoFs) region are characterized for arbitrary channel strength and channel uncertainty levels for each of the channel coefficients. The result is extended to K>2 users under additional restrictions which include the assumption of symmetry.

A (K, N, T, Kc) instance of private information retrieval from MDS coded data with colluding servers (in short, MDS-TPIR), is comprised of K messages and N distributed servers. Each message is separately encoded through a (Kc, N) MDS storage code. A user wishes to retrieve one message, as efficiently as possible, while revealing no information about the desired message index to any colluding set of up to T servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either T or Kcbelongs to {1, N}. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti, and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting (K, N, T, Kc) = (2, 4, 2, 2), which achieves the rate 3/5, exceeding the conjectured capacity, 4/7. Insights from the counterexample lead us to capacity characterizations for various instances of MDS-TPIR, including all cases with (K, N, T, Kc) = (2, N, T, N -1), where N and T can be arbitrary.

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. The information theoretic capacity of PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. T-private PIR is a generalization of PIR to include the requirement that even if any T of the N databases collude, the identity of the retrieved message remains completely unknown to them. Robust PIR is another generalization that refers to the scenario where we have M ≥ N databases, out of which any M-N may fail to respond. For K messages and M ≥ N databases out of which at least some N must respond, we show that the capacity of T-private and Robust PIR is (1 + T/N + T2/N2+ · · · + TK-1/NK-1)-1. The result includes as special cases the capacity of PIR without robustness (M = N) or T-privacy constraints (T = 1).

Private information retrieval (PIR) is the problem of retrieving one message out of K messages from N noncommunicating replicated databases, where each database stores all K messages, in such a way that each database learns no information about which message is being retrieved. The capacity of PIR is the maximum number of bits of desired information per bit of downloaded information among all PIR schemes. The capacity has recently been characterized for PIR as well as several of its variants. In every case it is assumed that all the queries are generated by the user simultaneously. Here we consider multiround PIR, where the queries in each round are allowed to depend on the answers received in previous rounds. We show that the capacity of multiround PIR is the same as the capacity of single-round PIR. The result is generalized to also include T-privacy constraints. Combined with previous results, this shows that there is no capacity advantage from multiround over single-round schemes, non-linear over linear schemes or from E-error over zero-error schemes. However, we show through an example that there is an advantage in terms of storage overhead. We provide an example of a multiround, non-linear, E-error PIR scheme that requires a strictly smaller storage overhead than the best possible with single-round, linear, zero-error PIR schemes.

The main result of this paper is that an orthogonal access scheme, such as time division multiple access achieves the all-unicast degrees of freedom (DoF) region of the topological interference management problem if and only if the network topology graph is chordal bipartite, i.e., every cycle that can contain a chord, does contain a chord. The all-unicast DoF region includes the DoF region for any arbitrary choice of a unicast message set, so e.g., the results of Maleki and Jafar on the optimality of orthogonal access for the sum-DoF of one-dimensional convex networks are recovered as a special case. The result is also established for the corresponding topological representation of the index coding problem.

The generalized degrees of freedom (GDoF) of the two user symmetric multiple input multiple output (MIMO) interference channel (IC) are characterized as a function of the channel strength levels and the level of channel state information at the transmitters (CSIT). In this symmetric setting, each transmitter is equipped with M antennas, each receiver is equipped with N antennas, and both cross links have the same strength parameter α and the same channel uncertainty parameter β. The main challenge resides in the proof of the outer bound which is accomplished by a generalization of the aligned image sets approach.

This work obtains the first degrees of freedom (DoF) bound that is sensitive to network coherence time, i.e., coherence time in an interference network where all channels experience the same coherence patterns. This is accomplished by a novel adaptation of the aligned image sets bound, and settles various open problems noted previously by Naderi and Avestimehr and by Gou et al. For example, a necessary and sufficient condition is obtained for the optimality of 1/2 DoF per user in a partially connected interference network where the channel state information at the receivers (CSIR) is perfect, the channel state information at the transmitters (CSIT) is instantaneous but limited to finite precision, and the network coherence time is Tc = 1. The broader insight that emerges is that even with perfect CSIR and instantaneous finite precision CSIT, network coherence time matters, i.e., it has a DoF impact.

An extension of private information retrieval (PIR) with colluding servers is considered. The N servers are partitioned into M disjoint sets, such that collusion can only occur between servers that belong to the same set. Specifically, the m-th set is comprised of Nmservers, of which any Tmcan collude. The capacity of this PIR problem is shown to be C = (1 + (Σm = 1MNm/Tm)-1 + ⋯ + (Σm = 1MNm/Tm)-(κ-1))-1.

We present sum-set inequalities specialized to the generalized degrees of freedom (GDoF) framework. These are information theoretic lower bounds on the entropy of bounded density linear combinations of discrete, power-limited dependent random variables in terms of the joint entropies of arbitrary linear combinations of new random variables that are obtained by power level partitioning of the original random variables. These bounds generalize the aligned image sets approach, and are useful instruments to obtain GDoF characterizations for wireless networks, especially with multiple antenna nodes, subject to arbitrary channel strength and channel uncertainty levels. To demonstrate the utility of these bounds, we consider various examples of interference and broadcast channels for which we obtain tight GDoF characterizations with the aid of sum-set inequalities.

A (K, N, T, Kc) instance of the MDS-TPIR problem is comprised of K messages and N distributed servers. Each message is separately encoded through an (N, Kc) MDS storage code. A user wishes to retrieve one message, as efficiently as possible, while revealing no information about the desired message index to any colluding set of up to T servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either T or Kcbelongs to {1, N}. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting (K, N, T, Kc) = (2,4, 2, 2), which achieves the rate 3/5, exceeding the conjectured capacity, 4/7.

A private information retrieval (PIR) scheme is a mechanism that allows a user to retrieve any one out of K messages from N non-communicating replicated databases, each of which stores all K messages, without revealing anything (in the information theoretic sense) about the identity of the desired message index to any individual database. If the size of each message is L bits and the total download required by a PIR scheme from all N databases is D bits, then D is called the download cost and the ratio L/D is called an achievable rate. For fixed K, N ϵ ℕ, the capacity of PIR, denoted by C, is the supremum of achievable rates over all PIR schemes and over all message sizes, and was recently shown to be C = (1+1/N +1/N2+⋯+1/NK-1)-1. In this paper, for arbitrary K and N, we explore the minimum download cost DLacross all PIR schemes (not restricted to linear schemes) for arbitrary message lengths L under arbitrary choices of alphabet (not restricted to finite fields) for the message and download symbols. If the same M-ary alphabet is used for the message and download symbols, then we show that the optimal download cost in M-ary symbols is DL= ⌈L/C⌉. If the message symbols are in M-ary alphabet and the downloaded symbols are in M'-ary alphabet, then we show that the optimal download cost in M'-ary symbols, DLϵ {⌈L'/C⌉, ⌈L'/C⌉-1, ⌈L'/C⌉ - 2}, where L' = ⌈L logM'M⌉, i.e., the optimal download cost is characterized to within two symbols.

The benefits of partial and full transmitter cooperation are evaluated for a two user interference channel under finite precision channel state information at the transmitters (CSITs), using the generalized degrees of freedom (GDoFs) metric. Under finite precision CSIT, the benefits of interference alignment are completely lost, so that the X channel obtained by partial transmitter cooperation does no better than the underlying interference channels. Full transmitter cooperation produces a vector broadcast channel, which has a strict GDoF advantage over partial cooperation (X channel) and whose GDoF is fully achieved by interference enhancement.

The generalized degrees of freedom (GDoF) characterization of the symmetric K user interference channel is obtained under finite precision channel state information at the transmitters (CSIT). The symmetric setting is where each cross channel is capable of carrying α DoF, while each direct channel is capable of carrying 1 DoF. Remarkably, under finite precision CSIT the symmetric K user interference channel loses all the GDoF benefits of interference alignment. The GDoF per user diminish with the number of users everywhere except in the very strong (optimal for every receiver to decode all messages) and very weak (optimal to treat all interference as noise) interference regimes. The result stands in sharp contrast to prior work on the symmetric setting under perfect CSIT, where the GDoF per user remain undiminished due to interference alignment. The result also stands in contrast to prior work on a subclass of asymmetric settings under finite precision CSIT, i.e., the topological interference management problem, where interference alignment plays a crucial role and provides substantial GDoF benefits.

In the private information retrieval (PIR) problem, a user wishes to retrieve, as efficiently as possible, one out of K messages from N non-communicating databases (each holds all K messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For K messages and N databases, we show that the PIR capacity is (1+1/N+1/N2+· · ·+1/NK-1)-1. A remarkable feature of the capacity achieving scheme is that if we eliminate any subset of messages (by setting the message symbols to zero), the resulting scheme also achieves the PIR capacity for the remaining subset of messages.

In order to gain new insights into multiple-input- multiple-output (MIMO) interference networks, the optimality of Σk=1KMk/2 (half the cake per user) degrees of freedom is explored for a K-user MIMO interference channel where the cross-channels have arbitrary rank constraints, and the kth transmitter and receiver are equipped with Mkantennas each. The result consolidates and significantly generalizes results from prior studies by Krishnamurthy et al., of rank-deficient interference channels where all users have M antennas; and by Tang et al., of full rank interference channels where the kth user pair has Mkantennas. The broader outcome of this paper is a novel class of replication-based outer bounds for arbitrary rank-constrained MIMO interference networks where replicas of existing users are added as auxiliary users and the network connectivity is chosen to ensure that any achievable scheme for the original network also works in the new network. The replicated network creates a new perspective of the problem, so that even simple arguments such as user cooperation become quite powerful when applied in the replicated network, giving rise to stronger outer bounds, than when applied directly in the original network. Remarkably, the replication-based bounds are broadly applicable not only to MIMO interference channels with arbitrary rank-constraints, but much more broadly, even beyond Gaussian settings.

In the private information retrieval (PIR) problem a user wishes to retrieve, as efficiently as possible, one out of K messages from N non-communicating databases (each holds all K messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For K messages and N databases, we show that the PIR capacity is (1 + 1/N + 1/N2+ ⋯+1/NK-1)-1. A remarkable feature of the capacity achieving scheme is that if it is projected onto any subset of messages by eliminating the remaining messages, it also achieves the PIR capacity for that subset of messages.

This work bridges the gap between sharply contrasting results on the degrees of freedom of the K user broadcast channel where the transmitter is equipped with K transmit antennas and each of the K receivers is equipped with a single antenna. This channel has K DoF when channel state information at the transmitter (CSIT) is perfect, but as shown recently, it has only 1 DoF when the CSIT is limited to finite precision. By considering the full range of partial CSIT assumptions parameterized by β ∈ [0,1], such that the strength of the channel estimation error terms scales as ~ SNR-βrelative to the channel strengths which scale as ~ SNR, it is shown that this channel has 1 - β + Kβ DoF. For K = 2 users with arbitrary βijparameters, the DoF are shown to be 1 + mini,jβij. To explore diversity of channel strengths, the results are further extended to the symmetric Generalized Degrees of Freedom setting where the direct channel strengths scale as ~ SNR and the cross channel strengths scale as ~ SNRα, α ∈ [0,1], β ∈ [0,α]. Here, the roles of α and β are shown to counter each other on equal terms, so that the sum GDoF value in the K user setting is (α - β) + K(1 - (α-β )) and for the 2 user setting with arbitrary βij, is 2 - α + mini,jβij.

The generalized degrees of freedom (GDoF) characterization of the symmetric K-user interference channel is obtained under finite precision channel state information at the transmitters (CSIT). The symmetric setting is where each cross channel is capable of carrying α degrees of freedom (DoF) while each direct channel is capable of carrying 1 DoF. Remarkably, under finite precision CSIT the symmetric K-user interference channel loses all the GDoF benefits of interference alignment. The GDoF per user diminish with the number of users everywhere except in the very strong (optimal for every receiver to decode all messages) and very weak (optimal to treat all interference as noise) interference regimes. The result stands in sharp contrast to prior work on the symmetric setting under perfect CSIT, where the GDoF per user remain undiminished due to interference alignment. The result also stands in contrast to prior work on a subclass of asymmetric settings under finite precision CSIT, i.e., the topological interference management problem, where interference alignment plays a crucial role and provides substantial GDoF benefits.

In this work, we first establish that for the class of interference channels identified by Geng et al. where treating interference as noise (TIN) is optimal from the generalized degrees-of-freedom (GDoF) perspective, if the number of antennas at each node is scaled by a common constant factor, then the GDoF region scales by the same factor almost surely, and the TIN scheme remains optimal for the entire GDoF region. Next, we demonstrate that for K-user MIMO interference channels with different antenna numbers for transmitters and receivers, there exist non-trivial parameter regimes where a simple scheme of zero-forcing strong interference and treating the others as noise achieves the sum GDoF.

Stotz and Bölcskei, 2015, identified an explicit condition for K/2 degrees of freedom (DoF) in constant single-antenna interference channels (ICs). This condition is expressed in terms of linear independence—over the rationals—of monomials in the off-diagonal entries of the IC matrix and is satisfied for almost all IC matrices. There is, however, a prominent class of IC matrices that admits K/2 DoF but fails to satisfy this condition. The main contribution of the present paper is a more general condition for K/2 DoF (in fact for 1/2 DoF for each user) that, inter alia, encompasses this example class. While the existing condition by Stotz and Bölcskei is of algebraic nature, the new condition is canonical in the sense of capturing the essence of interference alignment by virtue of being expressed in terms of a generic injectivity condition that guarantees separability of signal and interference.

Blind interference alignment (BIA) refers to interference alignment schemes that are designed only based on channel coherence pattern knowledge at the transmitters (the “blind” transmitters do not know the exact channel values). Private information retrieval (PIR) refers to the problem where a user retrieves one out of K messages from N non-communicating databases (each holds all K messages) without revealing anything about the identity of the desired message index to any individual database. In this paper, we identify an intriguing connection between PIR and BIA. Inspired by this connection, we characterize the information theoretic optimal download cost of PIR, when we have K = 2 messages and the number of databases, N, is arbitrary.

A conjecture made by Lapidoth et al. at Allerton 2005 (also an open problem presented at ITA 2006) states that the degrees of freedom (DoF) of a two user broadcast channel, where the transmitter is equipped with two antennas and each user is equipped with one antenna, must collapse under finite precision channel state information at the transmitter (CSIT). That this conjecture, which predates interference alignment, has remained unresolved, is emblematic of a pervasive lack of understanding of the DoF of wireless networks-including interference and X networks-under channel uncertainty at the transmitter(s). In this paper, we prove that the conjecture is true in all non-degenerate settings (e.g., where the probability density function of unknown channel coefficients exists and is bounded). The DoF collapse even when perfect channel knowledge for one user is available to the transmitter. This also settles a related recent conjecture by Tandon et al. The key to our proof is a bound on the number of codewords that can cast the same image (within noise distortion) at the undesired receiver whose channel is subject to finite precision CSIT, while remaining resolvable at the desired receiver whose channel is precisely known by the transmitter. We are also able to generalize the result along two directions. First, if the peak of the probability density function is √ allowed to scale as O(( √P)α), representing the concentration of probability density (improving CSIT) due to, e.g., quantized feedback at rate (α/2) log(P), then the DoF is bounded above by 1+α, which is also achievable under quantized feedback. Second, we generalize the result to arbitrary number of antennas at the transmitter, arbitrary number of single-antenna users, and complex channels. The generalization directly implies a collapse of DoF to unity under non-degenerate channel uncertainty for the general K-user interference and M × N user X networks as well.

In a K-user Gaussian interference channel, it has been shown by Geng et al. that if for each user, the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in decibel scale), then power control and treating interference as noise (TIN) is optimal from the perspective of generalized degrees of freedom (GDoF) and achieves the entire channel capacity region to within a constant gap. In this paper, we generalize the optimality of TIN to compound networks. We show that for a K-user compound Gaussian interference channel, if in every possible state for each receiver, the channel always satisfies the TIN-optimality condition identified by Geng et al., then the GDoF region of the compound channel is the intersection of the GDoF regions of all possible network realizations, which is achievable by power control and TIN. Furthermore, we demonstrate that for a general K-user compound interference channel, regardless of the number of states of each receiver, we can always construct a counterpart K-user regular interference channel that has the same TIN region as the original compound channel. The regular interference channel has only one state for each receiver, which may be different from all of the original states. Solving the GDoF-based power control problem for the compound channel is equivalent to solving the same problem in its regular counterpart. Exploring the power control problem further we develop a centralized power control scheme for K-user compound interference channels, to achieve all the Pareto optimal GDoF tuples. Finally, based on this scheme, we devise an iterative power control algorithm which requires at most K updates to obtain the globally optimal power allocation for any feasible GDoF tuple.

It has been recently shown by Geng et al. that in a K-user Gaussian interference network, if for each user, the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all signal strengths measured in dB scale), then power control and treating interference as noise (TIN) is sufficient to achieve the entire generalized degrees of freedom (GDoF) region. Motivated by the intuition that the deterministic model of Avestimehr et al. (Avestimehr-Diggavi-Tse deterministic model) is particularly suited for exploring the optimality of TIN, the results of Geng et al. are first re-visited under the ADT deterministic model, and are shown to directly translate between the Gaussian and deterministic settings. Next, we focus on the extension of these results to parallel interference networks, from a sum-capacity/sum-GDoF perspective. To this end, we interpret the explicit characterization of the sum capacity/sum GDoF of a TIN optimal network (without parallel channels) as a minimum weighted matching problem in combinatorial optimization, and obtain a simple characterization in terms of a partition of the interference network into vertex-disjoint cycles. Aided by insights from the cyclic partition, the sum-capacity optimality of TIN for K-user parallel interference networks is characterized for the ADT deterministic model, leading ultimately to the corresponding GDoF results for the Gaussian setting. In both the cases, subject to a mild invertibility condition, the optimality of TIN is shown to extend to parallel networks in a separable fashion.

In this paper, we propose a novel “genie chains” approach to obtain information theoretic degrees of freedom (DoF) outer bounds for MIMO wireless interference networks. This new approach creates a chain of mappings from genie signals provided to a receiver to the exposed signal spaces at that receiver, and then the exposed signal spaces serve as the genie signals for the next receiver in the chain subject to certain linear independence requirements. Our approach essentially converts an information theoretic DoF outer bound problem into a linear algebra problem. Several applications of the genie chains approach are presented.

The benefits of partial and full transmitter cooperation are evaluated for a two user interference channel under finite precision channel state information at the transmitters (CSIT), using the generalized degrees of freedom (GDoF) metric. Under finite precision CSIT, the benefits of interference alignment are completely lost, so that the X channel obtained by partial transmitter cooperation does no better than the underlying interference channels. Full transmitter cooperation produces a vector broadcast channel (BC) which has a strict GDoF advantage over partial cooperation (X channel) and whose GDoF are fully achieved by interference enhancement.

We consider 2-user symmetric interference channels with confidential messages. For the linear deterministic model of this channel, we develop inner and outer bounds for the symmetric secure rate, which are shown to match and characterize the symmetric secure capacity for a wide range of channel parameters. For the achievability, we present a cooperative jamming scheme based on interference alignment principle, which is optimal for all regimes where the symmetric secure capacity is established. For the converse, a tighter outer bound than all previously existing ones is provided for the regime where the symmetric secure capacity is still open.

By introducing a novel outer bound, we find Σk=1kMk/2 degrees of freedom (half the cake per user) for a K-user multiple-inputmultiple-output (MIMO) interference channel (IC) where the cross-channels have arbitrary rank constraints, and the kthtransmitter and receiver are equipped with Mkantennas each. The result consolidates and significantly generalizes results from prior studies by Krishnamurthy et al., of rank-deficient interference channels where all users have M antennas; and by Tang et al., of full rank interference channels where the kthuser pair has Mkantennas.

For the K-user interference channel, Geng et al. identify a general condition under which power control and treating interference as noise (TIN) is optimal from the perspective of generalized degrees of freedom (GDoF). In this work, we show that for a K-user compound interference channel, if in every possible state for each receiver, the channel satisfies the TIN-optimality condition of Geng et al., then power control and TIN achieves the entire GDoF region of the compound channel. For an arbitrary compound interference channel, we find a non-trivial counterpart regular interference channel, such that the two have the same TIN region, and the GDoF-optimal power control problems for the two are equivalent.

It has been shown recently by Sun et al. that in a K user parallel Gaussian interference network, if over each sub-channel, for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all signal strengths measured in dB scale), then separate coding over each sub-channel and treating interference as noise (TIN) is sufficient to achieve the sum generalized degrees of freedom (GDoF), subject to a mild invertibility condition [1]. In this work, we show that the weighted sum GDoF is similarly separable, i.e., separate coding and TIN is sufficient to achieve the weighted sum GDoF, subject to a similar mild invertibility condition. This is proved by translating the weighted GDoF optimization problem to the sum GDoF problem of a class of compound parallel Gaussian interference networks, giving rise to new weighted GDoF outer bounds that are strictly stronger than what is implied by the sum GDoF bounds obtained previously.

In many wireless networks, link strengths are affected by many topological factors, such as different distances, shadowing, and intercell interference, thus resulting in some links being generally stronger than other links. From an information theoretic point of view, accounting for such topological aspects is still a novel approach, that has been recently fueled by strong indications that such aspects can crucially affect transceiver and feedback design, as well as the overall performance. This paper here takes a step in exploring this interplay between topology, feedback, and performance. This is done for the two user broadcast channel with random fading, in the presence of a simple two-state topological setting of statistically strong versus weaker links, and in the presence of a practical ternary feedback setting of alternating channel state information at the transmitter [alternating channel state information at the transmitter (CSIT)] where for each channel realization, this CSIT can be perfect, delayed, or not available. In this setting, the work derives generalized degrees-of-freedom bounds and exact expressions, that capture performance as a function of feedback statistics and topology statistics. The results are based on novel topological signal management schemes that account for topology in order to fully utilize feedback. This is achieved for different classes of feedback mechanisms of practical importance, from which we identify specific feedback mechanisms that are best suited for different topologies. This approach offers further insight on how to split the effort-of channel learning and feeding back CSIT-for the strong versus for the weaker link. Further intuition is provided on the possible gains from topological spatio-temporal diversity, where topology changes in time and across users.

It is shown that in the K-user interference channel, if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in decibel scale), then the simple scheme of using point-to-point Gaussian codebooks with appropriate power levels at each transmitter and treating interference as noise (TIN) at every receiver (in short, TIN scheme) achieves all points in the capacity region to within a constant gap. The generalized degrees of freedom (GDoF) region under this condition is a polyhedron, which is shown to be fully achieved by the same scheme, without the need for time-sharing. The results are proved by first deriving a polyhedral relaxation of the GDoF region achieved by TIN, and then providing a dual characterization of this polyhedral region via the use of potential functions, and finally proving the optimality of this region in the desired regime.

In a K-user Gaussian interference channel, it has been shown that if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in decibel scale), then treating interference as noise (TIN) is optimal from the perspective of generalized degrees of freedom (GDoF) and achieves the entire channel capacity region to within a constant gap. In this paper, we show that for such TINoptimal interference channels, even if the message set is expanded to include an independent message from each transmitter to each receiver, operating the new channel as the original interference channel and treating interference as noise is still optimal for the sum capacity up to a constant gap. Furthermore, we extend the result to the sum-GDoF optimality of TIN in the general setting of X channels with arbitrary numbers of transmitters and receivers.

We characterize the degrees of freedom (DoF) of multiple-input and multiple-output (MIMO) interference channels with rank-deficient channel matrices. For the two-user rank-deficient MIMO interference channel, we provide a tight outer bound to show that the previously known achievable DoF in the symmetric case is optimal and generalize the result to fully asymmetric settings. For the K-user rank-deficient interference channel, we improve the previously known achievable DoF and provide a tight outer bound to establish optimality in symmetric settings. In particular, we show that for the K-user rank-deficient interference channel, when all nodes have M antennas, all direct channels have rank D0, all cross channels are of rank D, and the channels are otherwise generic, the optimal DoF value per user is min(D0, M - (min(M, (K - 1)D)/2)). Notably for interference channels, the rank-deficiency of direct channels does not help and the rank deficiency of cross-channels does not hurt. The main technical challenge is to account for the spatial dependences introduced by rank deficiencies in the interference alignment schemes that typically rely on the independence of channel coefficients.

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

An interference alignment perspective is used to identify the simplest instances (minimum possible number of edges in the alignment graph, not more than 2 interfering messages at any destination) of index coding problems where non-Shannon information inequalities are necessary for capacity characterization. In particular, this includes the first known example of a multiple unicast (one destination per message) index coding problem where non-Shannon information inequalities are shown to be necessary. The simplest multiple unicast example has 7 edges in the alignment graph and 11 messages. The simplest multiple groupcast (multiple destinations per message) example has 6 edges in the alignment graph, 6 messages, and 10 receivers. For both the simplest multiple unicast and multiple groupcast instances, the best outer bound based on only Shannon inequalities is 2/5, which is tightened to 11/28 by the use of the Zhang-Yeung non-Shannon type information inequality, and the linear capacity is shown to be 5/13 using the Ingleton inequality. Conversely, identifying the minimal challenging aspects of the index coding problem allows an expansion of the class of solved index coding problems up to (but not including) these instances.

We study the degrees of freedom (DoF) of the layered 2 × 2 × 2 multiple-input-multiple-output (MIMO) interference channel where each node is equipped with arbitrary number of antennas, the channels between the nodes have arbitrary rank constraints, and subject to the rank-constraints the channel coefficients can take arbitrary values. The DoF outer bounds reveal a fundamental rank-matching phenomenon, reminiscent of impedance matching in circuit theory. It is well known that the maximum power transfer in a circuit is achieved not for the maximum or minimum load impedance but for the load impedance that matches the source impedance. Similarly, the maximum DoF in the rank-constrained 2 × 2 × 2 MIMO interference network is achieved not for the maximum or minimum ranks of the destination hop, but when the ranks of the destination hop match the ranks of the source hop. In fact, for mismatched settings of interest, the outer bounds identify a DoF loss penalty that is precisely equal to the rank-mismatch between the two hops. For symmetric settings, we also provide achievability results to show that along with the min-cut max-flow bounds, the rank-mismatch bounds are the best possible, i.e., they hold for all channels that satisfy the rank-constraints and are tight for almost all channels that satisfy the rank-constraints. Limited extensions-from sum-DoF to DoF region, from 2 unicasts to X message sets, from 2 hops to more than 2 hops and from 2 nodes per layer to more than 2 nodes per layer-are considered to illustrate how the insights generalize beyond the elemental 2 × 2 × 2 channel model.

We consider the topological interference management problem for a downlink hexagonal cellular network, where the channel state information at the transmitters is limited to just the network topology. Recent work by Jafar showed that if interference is limited to only near the cell boundary, then, an aligned frequency reuse pattern achieves the optimal value of 6/7 degrees of freedom (DoF) per cell, as opposed to the conventional frequency reuse baseline of 1/3 DoF per cell. We generalize the setting to include interference from multiple layers of adjacent cells and characterize how the gains of the optimal solution over basic frequency reuse diminish with increasing number of interference layers. Next, we focus on single-layer interference and explore the sensitivity of the idealized assumptions behind the connectivity model of Jafar, which achieves higher DoF but only at the cost of a higher effective noise floor than the baseline, and under idealized placements of users. A modified connectivity model that operates at a comparable noise-floor to the baseline is then studied, and its DoF are shown to be bounded above by 6/11 and below by 1/2. Through numerical simulations, we compare the solutions that achieve 6/7, 1/2, and 1/3 DoF per cell and find that, while both the 6/7 and the 1/2 DoF solutions beat the baseline 1/3 figure, between them, the 1/2 DoF aligned frequency reuse pattern is more robust for small cell networks particularly for random users' distribution on the cell boundaries.

A conjecture made by Lapidoth, Shamai and Wigger at Allerton 2005 (also an open problem presented at ITA 2006) states that the degrees of freedom (DoF) of a two user broadcast channel, where the transmitter is equipped with 2 antennas and each user is equipped with 1 antenna, must collapse under finite precision channel state information at the transmitter (CSIT). That this conjecture, which predates interference alignment, has remained unresolved, is emblematic of a pervasive lack of understanding of the degrees of freedom of wireless networks-including interference and X networks-under channel uncertainty at the transmitter(s). In this work we prove that the conjecture is true in all non-degenerate settings (e.g., where the probability density function of unknown channel coefficients exists and is bounded). The DoF collapse even when perfect channel knowledge for one user is available to the transmitter. This also settles a related recent conjecture by Tandon et al. Reminiscent of Korner and Marton's work on the images of a set, the key to our proof is a bound on the number of codewords that can cast the same image (within noise distortion) at the undesired receiver, while remaining resolvable at the desired receiver. We are also able to generalize the result to arbitrary number of users, including the K user interference channel. Remarkably, for the K user interference channel, this work and the earlier work by Cadambe and Jafar reveal two contrasting sides of the same coin. Both works close a gap between the best previously known DoF inner bound of 1 and the best previously known DoF outer bound of K/2. However, while Cadambe and Jafar do so in the optimistic direction, showing that K/2 is optimal under perfect CSIT, here we close the gap in the pessimistic direction, showing that 1 DoF is optimal under finite precision CSIT.

Seeking fundamental insights into multi-hop multi-flow networks we study the simplest non-trivial setting, a 2 × 2 × 2 MIMO interference network comprised of two sources, two relays and two destinations, wherein all nodes have M antennas, all first-hop channels are of rank D1, and all second hop channels are of rank D2. For this setting, we show that the optimal sum DoF is min(4D1, 4D2, 2M - |D1- D2|). While 4D1, 4D2are the obvious min-cut bottlenecks that are active when either hop is severely rank-deficient, what is remarkable is that under moderate rank-deficiencies the DoF are limited not by the higher or the lower of the two ranks D1, D2, but only by the difference of the two ranks |D1- D2|. This suggests an interesting "rank-matching" design principle for multi-hop networks, reminiscent of "impedance matching", wherein the goal is not necessarily to increase or decrease the rank of each hop, but rather to use linear processing at intermediate hops to create effectively a two-hop setting with matching ranks.

In many wireless networks, link strengths are affected by many topological factors such as different distances, shadowing and inter-cell interference, thus resulting in some links being generally stronger than other links. From an information theoretic point of view, accounting for such topological aspects has remained largely unexplored, despite strong indications that such aspects can crucially affect transceiver and feedback design, as well as the overall performance. The work here takes a step in exploring this interplay between topology, feedback and performance. This is done for the two user broadcast channel with random fading, in the presence of a simple two-state topological setting of statistically strong vs. weaker links, and in the presence of a practical ternary feedback setting of alternating channel state information at the transmitter (alternating CSIT) where for each channel realization, this CSIT can be perfect, delayed, or not available. In this setting, the work derives generalized degrees-of-freedom bounds and exact expressions, that capture performance as a function of feedback statistics and topology statistics. The results are based on novel topological signal management (TSM) schemes that account for topology in order to fully utilize feedback. This is achieved for different classes of feedback mechanisms of practical importance, from which we identify specific feedback mechanisms that are best suited for different topologies. This approach offers further insight on how to split the effort - of channel learning and feeding back CSIT - for the strong versus for the weaker link. Further intuition is provided on the possible gains from topological spatio-temporal diversity, where topology changes in time and across users.

In a K-user Gaussian interference channel, it has been shown that if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in dB scale), then treating interference as noise (TIN) is optimal from the perspective of generalized degrees-of-freedom (GDoF) and achieves the entire channel capacity region to within a constant gap. In this work, we show that for such TIN-optimal interference channels, even if the message set is expanded to include an independent message from each transmitter to each receiver, operating the new channel as the original interference channel and treating interference as noise is still optimal for the sum capacity up to a constant gap.

We consider the interference channel with K transmitters and K receivers all having a single antenna, wherein the K × K transfer matrix representing this channel has rank D (D <; K) . The degrees of freedom (DoF) of such channels are not known as the rank deficiency in the transfer matrix creates algebraic dependencies between the channel coefficients. We present a modified version of the [CJ08] alignment scheme, to handle these dependencies while aligning interference, and state the sufficient conditions for achieving half rate per user using this scheme. The difficulties in proving these sufficient conditions are shown for K = 4 and K = 5. We also show that these sufficient conditions are not satisfied for K ≥ 6.

It has been shown recently by Geng et al. that in a K user Gaussian interference network, if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all signal strengths measured in dB scale), then power control and treating interference as noise (TIN) is sufficient to achieve the entire generalized degrees of freedom (GDoF) region. Motivated by the intuition that the deterministic model of Avestimehr et al. (ADT deterministic model) is particularly suited for exploring the optimality of TIN, the results of Geng et al. are first re-visited under the ADT deterministic model, and corresponding TIN optimality results are obtained. Next, we focus on the extension of these results to ADT deterministic parallel interference networks, from a sum-capacity perspective. To this end, we interpret the explicit characterization of the sum-capacity of a TIN optimal network (without parallel channels) as a minimum weighted matching problem in combinatorial optimization, and obtain a simple characterization in terms of a partition of the interference network into vertex-disjoint cycles. Aided by insights from the cyclic partition, the sum-capacity optimality of TIN for K user parallel interference networks is characterized for the ADT deterministic model. Subject to a mild invertibility condition the optimality of TIN is shown to extend to parallel networks in a separable fashion.

The topological interference management problem refers to the study of the DoF of partially connected wireless communication networks with no channel state information at the transmitters (no CSIT) beyond the network topology, i.e., a knowledge of which channel coefficients are non-zero. While the problem is originally studied with single input sources and single output destinations (SISO), in this work we explore the implications of multiple inputs and multiple outputs (MIMO), highlighting fundamental differences and new phenomena.

Starting from the elemental 2 × 2 × 2 interference channel, there has been much progress in the understanding of multihop multiflow wireless networks through degrees of freedom (DoF) studies that have produced important ideas such as (aligned) interference neutralization. However, much of this progress has been limited to layered connectivity models that are essentially motivated by the assumption that wireless networks can only operate in half-duplex mode. Motivated by recent breakthroughs in full-duplex radio technology, in this work, we expand the 2 × 2 × 2 interference channel model beyond layered connectivity in order to study the impact of full-duplex operation. In particular, we study the impact of intra-layer connectivity between relays that are in the same layer, the impact of direct inter-layer connectivity between sources and destinations, and the impact of intermediate inter-layer connectivity that connects sources or destinations, not directly to each other, but to relay nodes in non-adjacent layers in a 2 × 2 × 2 × 2 interference channel. We show that intra-layer links and intermediate inter-layer interference links do not cause a collapse of DoF, whereas direct interference links do cause a collapse of DoF.

This correspondence corrects an error in our paper titled, "On the Optimality of Beamforming with Quantized Feedback", published in the IEEE Transactions on Communications, vol. 55, no. 12, pp. 2288-2302, Dec. 2007.

This paper studies linear interference networks, both wired and wireless, with no channel state information at the transmitters except a coarse knowledge of the end-to-end one-hop topology of the network that only allows a distinction between weak (zero) and significant (nonzero) channels and no further knowledge of the channel coefficients' realizations. The network capacity (wired) and degrees of freedom (DoF) (wireless) are found to be bounded above by the capacity of an index coding problem for which the antidote graph is the complement of the given interference graph. The problems are shown to be equivalent under linear solutions. An interference alignment perspective is then used to translate the existing index coding solutions into the wired network capacity and wireless network DoF solutions, as well as to find new and unified solutions to different classes of all three problems.

This paper explores how degrees of freedom (DoF) results from wireless networks can be translated into capacity or linear capacity results for their finite field counterparts that arise in network coding applications. The main insight is that scalar (SISO) finite field channels over Fpn are analogous to n × n vector (MIMO) channels in the wireless setting, but with an important distinction-there is additional structure due to finite held arithmetic, which enforces commutativity of matrix multiplication and limits the channel diversity to n, making these channels similar to diagonal channels in the wireless setting. Within the limits imposed by the channel structure, the DoF optimal precoding solutions for wireless networks can be translated into capacity or linear capacity optimal solutions for their finite held counterparts. This is shown through the study of capacity of the 2-user X channel and linear capacity of the 3-user interference channel. Besides bringing the insights from wireless networks into network coding applications, the study of finite held networks over Fpn also touches upon important open problems in wireless networks (finite SNR, finite diversity scenarios) through interesting parallels between p and SNR, and n and diversity.

The index coding problem is studied from an interference alignment perspective providing new results as well as new insights into, and generalizations of, previously known results. An equivalence is established between the capacity of multiple unicast index coding (where each message is desired by exactly one receiver), and groupcast index coding (where a message can be desired by multiple receivers), which settles the heretofore open question of insufficiency of linear codes for the multiple unicast index coding problem by equivalence with groupcast settings, where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message in the index coding problem are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate 1/(L + 1) per message when each destination desires at least L messages, are similarly obtained. Finally, capacity optimal solutions are presented to a series of symmetric index coding problems inspired by the local connectivity and local interference characteristics of wireless networks. The solutions are based on vector linear coding.

We show that the three-user MT× MRMultiple-Input Multiple-Output (MIMO) interference channel where each transmitter is equipped with MTantennas and each receiver is equipped with MRantennas has (M) d(M, N) =Δmin (M/2-1/κ, N/2+1/κ) degrees of freedom (DoF) normalized by time, frequency, and space dimensions, where =Δmin(MT, MR), N =Δmax(MT, MR), κ =Δ⌈M/N-M⌉. While the DoF outer bound of d(M, N) is established for every MT, MRvalue, the achievability of d(M, N) DoF is established in general subject to a normalization with respect to spatial extensions, i.e., the scaling of the number of antennas at all nodes. In particular, we show that qd(M, N) DoF are achievable for the three-user qMT × qMR MIMO interference channel, for some positive integer q, which may be seen as a spatial extension factor. q is the scaling factor needed to make the value qd(M, N) an integer. Given spatial extensions, the achievability relies only on linear beamforming based interference alignment schemes and requires neither channel extensions nor channel variations in time or frequency. In the absence of spatial extensions, it is shown through examples how essentially the same interference alignment scheme may be applied over time-extensions over either constant or time-varying channels. The central new insight to emerge from this paper is the notion of subspace alignment chains as the DoF bottlenecks. The subspace alignment chains are instrumental both in identifying the extra dimensions to be provided by a genie to a receiver for the DoF outer bound, as well as in the construction of the optimal interference alignment schemes. The DoF value d(M, N) is a piecewise linear function of M, N, with either M or N being the bottleneck within each linear segment, whereas the other value contains some redundancy, i.e., it can be reduced without reducing the DoF. The corner points of these piecewise linear segments correspond to two sets, A={1/2, 2/3, 3/4, ...}and B={1/3, 3/5, 5/7, ...}. The set A contains all those values of M/N and only those values of M/N for which there is redundancy in both M and N, i.e., either can be reduced without reducing the DoF. The set B contains all those values of M/N and only those values of M/N for which there is no redundancy in either M or N, i.e., neither can be reduced without reducing the DoF. Because A and B represent settings with maximum and minimum redundancy, essentially they are the basis for the DoF outer bounds and inner bounds, respectively. Our results settle the question of feasibility of linear interference alignment, introduced previously by Cenk et al., for the three-user MT× MRMIMO interference channel, completely for all values of MT, MR. In particular, we show that the linear interference alignment problem (MT× MR, d)3(as defined in previous paper by Cenk et al.) is feasible if and only if d ≤ d(M, N). With the exception of the values M/N ∈ B, and only with that exception, we show that for every M/N value there are proper systems (as defined by Cenk et al.) that are not feasible. Evidently the redundancy contained in all other values of M/N manifests itself as superfluous variables that are not discounted in the definition of proper systems, thus creating a discrepancy between proper and feasible systems. Our results show that M/N ∈ A are the only values for which there is no DoF benefit of joint processing among co-located antennas at the transmitters or receivers. This may also be seen as a consequence of the maximum redundancy in the M/N ∈ A settings.

This paper explores the use of selection diversity for interference alignment systems. Multiple distinct alignment modes exist for certain types of interference network. By selecting the best alignment mode to support the signal-to-noise rate (SNR) of the worst user, a diversity gain improvement can be observed. This paper shows that in a 3-user double-antenna interference channel, a system switching between two alignment modes achieves a diversity gain of 2 in the fixed-rate regime and the maximum degree-of-freedom (DoF) gain of 3 in the variable-rate regime. Consequently, we disprove a previous feasibility condition for diversity in alignment systems, which requires a trade-off between the DoF gain and the diversity gain.

While the outer-bound of sum degrees of freedom (DoF) of 3-user interference channel is known, the entire DoF region is still unknown in terms of both outer-bound and achievable region. In this paper, we first give the outer-bound of DoF region. Then, we present a linear beamforming scheme based on interference alignment chain whose achievable DoF region is the same as the outer bound, with the consideration of integer DoF only.

Precoding based network alignment (PBNA) is a network coding paradigm inspired by wireless networks where all the intelligence resides at the sources and destination nodes whereas intermediate relay nodes only perform arbitrary linear network coding operations, creating an effective one-hop finite field linear network between sources and destinations. The main question explored in this work is how degrees of freedom (DoF) results from wireless networks can be translated into capacity results for their finite field counterparts. A finite field X channel, i.e., a multiple unicast network comprised of 2 source nodes, 2 destination nodes and 4 independent messages (one for each source-destination pair) is considered in this work, where the channel outputs are arbitrary linear combinations of channel inputs over a finite field Fpn. Like its wireless counterpart, which has 4/3 sum DoF, this channel is shown to have a sum capacity of 4/3 symbols per channel use for most channel realizations. The main insight is that, with a few exceptions that are pointed out, scalar (SISO) finite field channels over Fpnare analogous to n×n complex vector (MIMO) channels in the wireless setting, so the DoF optimal precoding solutions for wireless networks can be translated into capacity optimal solutions for their finite field counterparts.

The topological interference management problem refers to the study of the capacity of partially connected linear (wired and wireless) communication networks with no channel state information at the transmitters (no CSIT) beyond the network topology, i.e., a knowledge of which channel coefficients are zero (weaker than the noise floor in the wireless case). While the problem is originally studied with fixed topology, in this work we explore the implications of varying connectivity, through a series of simple and conceptually representative examples. Specifically, we highlight the synergistic benefits of coding across alternating topologies.

The degrees of freedom (DoF) of the two-user multiple-input single-output (MISO) broadcast channel (BC) are studied under the assumption that the form, Ii, i = 1, 2, of the channel state information at the transmitter (CSIT) for each user's channel can be either perfect (P), delayed (D) or not available (N), i.e., I1, I2ϵ {P, N, D}, and therefore the overall CSIT can alternate between the 9 resulting states I1I2. The fraction of time associated with CSIT state I1I2is denoted by the parameter λI1I2and it is assumed throughout that λI1I2= λI2I1, i.e., λPN= λNP, λPD= λDP, λDN= λND. Under this assumption of symmetry, the main contribution of this paper is a complete characterization of the DoF region of the two user MISO BC with alternating CSIT. The results highlight the synergistic benefits of alternating CSIT and the tradeoffs between various forms of CSIT for any given DoF value.

The robust principles of treating interference as noise (TIN) when it is sufficiently weak, and avoiding it when it is not, form the background for this work. Combining TIN with the topological interference management (TIM) framework that identifies optimal interference avoidance schemes, a baseline TIM-TIN approach is proposed which decomposes a network into TIN and TIM components, allocates the signal power levels to each user in the TIN component, allocates signal vector space dimensions to each user in the TIM component, and guarantees that the product of the two is an achievable number of signal dimensions available to each user in the original network.

The high repair bandwidth cost of (n,k) maximum distance separable (MDS) erasure codes has motivated a new class of codes that can reduce repair bandwidth over that of conventional MDS codes. In this paper, we address (n,k,d) exact repair MDS codes, which allow for any single failed node to be repaired exactly with access to any arbitrary set ofdsurvivor nodes. We show the existence of exact repair MDS codes that achieve minimum repair bandwidth (matching the cut-set lower bound) for arbitrary admissible (n,k,d), i.e.,k≤d≤n-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set ofr≤n-kfailed nodes needs to repaired. Our approach is based on asymptotic interference alignment proposed by Cadambe and Jafar. As a byproduct, we also characterize the capacity of a class of multisource nonmulticast networks.

We show that an M×N user MIMO X network with A antennas at each node has A(MN/(M+N-1)) degrees of freedom (DoF), thus resolving in this case a discrepancy between the spatial scale invariance conjecture (scaling the number of antennas at each node by a constant factor will scale the total DoF by the same factor) and a decomposability property of overconstrained wireless networks. While the best previously known general DoF outer bound is consistent with the spatial invariance conjecture, the best previously known general DoF inner bound, inspired by the K user MIMO interference channel, was based on the decomposition of every transmitter and receiver into multiple single antenna nodes, transforming the network into an AM×AN user SISO X network. While such a decomposition is DoF optimal for the K user MIMO interference channel, a gap remained between the best inner and outer bounds for the MIMO X channel. Here we close this gap with the new insight that the MIMO X network is only one-sided decomposable, i.e., either all the transmitters or all the receivers (but not both) can be decomposed by splitting multiple antenna nodes into multiple single antenna nodes without loss of DoF. The result is extended to SIMO and MISO X networks as well and in each case the DoF results satisfy the spatial scale invariance property.

The degrees of freedom (DoFs) of the two-user multiple-input single-output (MISO) broadcast channel (BC) are studied under the assumption that the form,$I_{i},\;i=1, 2$, of the channel state information at the transmitter (CSIT) for each user's channel can be either perfect$(P)$, delayed$(D)$, or not available$(N)$, i.e.,$I_{1},I_{2} \in \{P,N,D\}$, and therefore, the overall CSIT can alternate between the nine resulting states$I_{1}I_{2}$. The fraction of time associated with CSIT state$I_{1}I_{2}$is denoted by the parameter$\lambda_{I_{1}I_{2}}$and it is assumed throughout that$\lambda_{I_{1}I_{2}} = \lambda_{I_{2}I_{1}}$, i.e.,$\lambda_{PN} = \lambda_{NP}, \lambda_{PD}=\lambda_{DP}, \lambda_{DN}=\lambda_{ND}$. Under this assumption of symmetry, the main contribution of this paper is a complete characterization of the DoF region of the two-user MISO BC with alternating CSIT. Surprisingly, the DoF region is found to depend only on the marginal probabilities$(\lambda_{P}, \lambda_{D},\lambda_{N})=\left(\sum_{I_{2}}\lambda_{PI_{2}},\sum_{I_{2}}\lambda_{DI_{2}}, \sum_{I_{2}}\lambda_{NI_{2}}\right)$,$I_{2} \in \{P,D,N\}$, which represent the fraction of time that any given user (e.g., user 1) is associated with perfect, delayed, or no CSIT, respectively. As a consequence, the DoF region with all nine CSIT states,${\cal {D}}(\lambda_{I_{1}I_{2}}:I_{1},I_{2} \in \{P,D,N\})$, is the same as the DoF region with only three CSIT states${\cal {D}}(\lambda_{PP}, \lambda_{DD}, \lambda_{NN})$, under the same marginal distribution of CSIT states, i.e.,$(\lambda_{PP}, \lambda_{DD},\lambda_{NN})=(\lambda_{P},\lambda_{D},\lambda_{N})$. The sum-DoF value can be expressed as${\rm DoF}=\min \left({{4+2\lambda_{P}} \over {3}}, 1+\lambda_{P}+\lambda_{D}\right)$, from which one can uniquely identify the minimum required marginal CSIT fractions to achieve any target DoF value as$(\lambda_{P},\lambda_{D})_{\min}=\left({{3} \over {2}} {\rm DoF}-2,1- {{1} \over {2}} {\rm DoF}\right)$when${\rm DoF} \in \big [{{4} \over {3}},2\big]$and$(\lambda_{P},\lambda_{D})_{\min}=(0,({\rm DoF}-1)^{+})$when${\rm DoF} \in \big [0, {{4} \over {3}}\big)$. The results highlight the synergistic benefits of alternating CSIT and the tradeoffs between various forms of CSIT for any given DoF value. Partial results are also presented for the multiuser MISO BC with$M$transmit antennas and$K$single antenna users. For this problem, the minimum amount of perfect CSIT required per user to achieve the maximum DoFs of$\min (M,K)$is characterized. By the minimum amount of CSIT per user, we refer to the minimum fraction of time that the transmitter has access to perfect and instantaneous CSIT from a user. Through a novel converse proof and an achievable scheme, it is shown that the minimum fraction of time perfect CSIT is required per user in order to achieve the DoF of$\min (M,K)$is given by$\min (M,K)/K$.

The original ergodic interference alignment scheme proposed by Nazer et al. requires symmetric channel phase distribution. In this paper, we investigate a new ergodic interference alignment scheme which can achieve one half interference-free degree of freedom (DoF) for arbitrary phase distribution. Even for symmetric phase distributions, the new scheme achieves a better high SNR offset than the original ergodic interference alignment scheme, and depending upon the magnitude distributions it is shown that the SNR offset improvement with the new scheme over the original scheme can be arbitrarily large. The SNR offset optimal ergodic alignment scheme is based on results in majorization theory.

We explore degrees of freedom (DoF) characterizations of partially connected wireless networks, especially cellular networks, with no channel state information at the transmitters (no CSIT), and show that the problem is intimately connected to the index coding problem typically considered in network coding literature, albeit with significant additional constraints imposed by the wireless setting. In other words, the degrees of freedom of cellular networks with no CSIT, is a wireless index coding problem.

We study the degrees of freedom (DoF) of 2-user and 3-user multiple input multiple output (MIMO) interference channels with rank deficient channel matrices. Only achievable DoF results and trivial outer bounds were previously available for these problems, restricted to symmetric settings. For the 2-user rank deficient MIMO interference channel we prove the optimality of previously known achievable DoF in the symmetric case and generalize the result to fully asymmetric settings. For the 3-user rank deficient MIMO interference channel, we improve the achievable DoF and provide a tight outer bound to establish optimality. Linear precoding based achievable schemes are found to be DoF optimal in both cases.

We explore the feasibility of linear interference alignment using finite signaling dimensions and symbol extensions. In the non-zero total intersection regime, we show that the number of sources is upperbounded by a function of channel diversity. The available diversity places a fundamental constraint on the number of signal spaces that can overlap at one destination (where they are undesired) while maintaining the resolvability of a subset of those signals (desired signals) at another destination. Specifically, the number of such signal spaces cannot be larger than the channel diversity. This is the diversity constraint that we identify in this paper. Not only is the proposed method applicable for X channels, interference channels, and their rank-deficient counterparts, it can also be used for both circular symmetric signaling (CSS) and asymmetric complex signaling (ACS) over a combination of frequency and MIMO channels with arbitrary symbol extensions.

The index coding problem is a multiple unicast wireline communication network where the network is represented by a directed graph having exactly one link with finite capacity (also known as the bottleneck link). There are K independent sources which share the ingress of this bottleneck link. Correspondingly there are K destinations which are on the receiving end of the bottleneck link, with each destination intending to decode the message of one (unique) corresponding source. Each destination can have apriori side-information of a (different) subset of the original source messages. In this paper, we study the capacity of such a network from the perspective of interference alignment, and derive information theoretically optimal schemes for a class of networks. In our first main result, we identify the set of graphs where each user can achieve half rate in the index coding problem. In a second result, we derive the capacity for a class of symmetric index coding networks.

We consider the problem of network coding across three unicast sessions over a directed acyclic graph, when each session has min-cut one. Previous work by Das et al. adapted a precoding-based interference alignment technique, originally developed for the wireless interference channel, specifically to this problem. We refer to this approach as precoding-based network alignment (PBNA). Similar to the wireless setting, PBNA asymptotically achieves half the minimum cut; different from the wireless setting, its feasibility depends on the graph structure. Das et al. provided a set of feasibility conditions for PBNA with respect to a particular precoding matrix. However, the set consisted of an infinite number of conditions, which is impossible to check in practice. Furthermore, the conditions were purely algebraic, without interpretation with regards to the graph structure. In this paper, we first prove that the set of conditions provided by Das. et al are also necessary for the feasibility of PBNA with respect to any precoding matrix. Then, using two graph-related properties and a degree-counting technique, we reduce the set to just four conditions. This reduction enables an efficient algorithm for checking the feasibility of PBNA on a given graph.

We show that an M × N user MIMO X network with A antennas at each node has A (MN/M+N-1) degrees of freedom (DoF), thus settling the spatial scale invariance conjecture (scaling the number of antennas at each node by a constant factor will scale the total DoF by the same factor) for this class of networks. The previously known best general DoF inner bound, inspired by the K user interference channel, was based on the decomposition of every transmitter and receiver into multiple single antenna nodes, transforming the network into an AM × AN user SISO X network. While such a decomposition is DoF optimal for the K user interference channel, a gap remained between the best inner and outer bound for the MIMO X channel. Here we close this gap with the new insight that the MIMO X network is only one-sided decomposable, i.e., either all the transmitters or all the receivers (but not both) can be decomposed by splitting multiple antenna nodes into multiple single antenna nodes without loss of DoF. The result is extended to SIMO and MISO X networks as well and in each case the DoF results satisfy the spatial scale invariance property. In addition, the feasibility of linear interference alignment is investigated based only on spatial beamforming without symbol extensions. Similar to MIMO interference networks, we show that when the problem is improper, it is infeasible.

We show that the 3 user MT× MRMIMO interference channel where each transmitter is equipped with MTand each receiver is equipped with MRantennas has min (M/2-1/k, N/2+1/k) degrees of freedom (DoF) per user normalized by time, frequency, and space dimensions, where N = max(MT, MR), M = min(MT, MR), k = [M/N-M]. While the information theoretic DoF outer bound is established for every M, N value, the achievability, relying only on linear interference alignment, is established in general subject to a normalization with respect to spatial-extensions, i.e., the scaling of the number of antennas at all nodes. In the absence of spatial extensions, we can also show through examples how essentially the same alignment scheme may be applied over time or frequency extensions. The central new insight to emerge from this work is the notion of subspace alignment chains as DoF bottlenecks. The subspace alignment chains are instrumental both in identifying the extra dimensions provided by a genie to a receiver for the DoF outer bound, as well as constructing the optimal interference alignment schemes. In addition, our results also settle the question of feasibility of linear interference alignment for the 3 user MT× MRMIMO interference channel, for all values of MT, MR.

We explore the degrees of freedom (DoF) of the K >; 3 user MT× MRMIMO Gaussian interference channel where each transmitter is equipped with MTand each receiver is equipped with MRantennas. Expressing the DoF characterization as a function of the ratio γ = M/N, where M = min(MT, MR) and N = max(MT, MR), we find that when γ ≤ γo= K-1/K(K-2) = γo, the DoF value per user is piecewise linear depending on M and N alternately, similar to the DoF characterization for K = 3 which has been previously obtained. The regime γ >; γo, which is the dominant regime for K >; 3 users and is not encountered in the K = 3 user setting, is the main focus of this paper. Our DoF results in this regime are obtained through a novel “genie chains” approach, which is the main contribution of this work. It is a chain of mappings from genie signals provided to a receiver to the exposed signal spaces at that receiver, which then serve as the genie signals for the next receiver in the chain, until an acceptable genie with the required number of dimensions is obtained, essentially converting an information theoretic problem into a linear algebra problem.

We show that the 2 × 2 × 2 interference network, i.e., the multihop interference network formed by concatenation of two two-user interference channels achieves the min-cut outer bound value of 2 DoF, for almost all values of channel coefficients, for both time-varying or fixed-channel coefficients. The key to this result is a new idea, called aligned interference neutralization, that provides a way to align interference terms over each hop in a manner that allows them to be canceled over the air at the last hop.

We explore the capacity and generalized degrees of freedom (GDOF) of the two-user Gaussian X channel, i.e., a generalization of the two-user interference channel where there is an independent message from each transmitter to each receiver. There are three main results in this paper. First, we characterize the sum capacity of the deterministic X channel under a symmetric setting. Second, we characterize the GDOF of the Gaussian X channel under a similar symmetric model. Third. we extend the sum capacity characterization previously obtained for the Gaussian interference channel in the noisy interference regime to the Gaussian X channel. Specifically, we show that the Gaussian X channel has the same sum capacity as the underlying Gaussian interference channel in this regime.

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

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

Most multiuser precoding techniques require accurate channel state information at the transmitter (CSIT) to maintain orthogonality between the users. Such techniques have proven quite fragile in time-varying channels because the CSIT is inherently imperfect due to quantization error and feedback delay. An alternative approach recently proposed by Maddah-Ali and Tse (MAT) allows for significant multiplexing gain in the multi-input single-output (MISO) broadcast channel (BC) even with CSIT that is "completely stale", i.e., uncorrelated with the current channel state. With K users, their scheme claims to lose only a log(K) factor relative to the full K degrees of freedom (DoF) attainable in the MISO BC with perfect CSIT for large K. However, their result does not consider the cost of the feedback, which is potentially very large in high mobility (short channel coherence time). In this paper, we more closely examine the MAT scheme and compare its maximum net DoF gain to single user transmission (which always achieves 1 DoF) and partial CSIT linear precoding (which achieves up to K). In particular, assuming the channel coherence time is N symbol periods and the feedback delay is Nfd, we show that when N; (1+o(1)) (Nfd+ K/ log K)(1-log-1K)-1(long coherence time), zero-forcing precoding outperforms the other two. The MAT scheme is optimal for intermediate coherence times, which for practical parameter choices is indeed quite a large and significant range, even accounting for the feedback cost.

We study the sum capacity of multiple unicasts in wireless multihop networks. With 2 source nodes and 2 sink nodes, there are a total of 4 independent unicast sessions (messages), one from each source to each sink node (this setting is also known as an X network). We explore the degrees of freedom (DoF) of wireless multihop X networks with a layered structure, allowing arbitrary number of hops and arbitrary connectivity within each hop. For the case when there are no more than two relay nodes in each layer, the DoF can only take values 1, 4/3, 3/2 or 2, based on the connectivity of the network, for almost all values of channel coefficients. When there are arbitrary number of relays in each layer, the DoF can also take the value 5/3. Achievability schemes incorporate linear forwarding, interference alignment and aligned interference neutralization principles. Information theoretic converse arguments specialized for the connectivity of the network are constructed based on the intuition from linear dimension counting arguments.

We show that the 2 × 2 × 2 interference network, i.e., the multihop interference network formed by concatenation of two 2-user interference channels achieves the min-cut outer bound value of 2 DoF, for almost all values of channel coefficients, for both time-varying or fixed channel coefficients. The key to this result is a new idea, called aligned interference neutralization, that provides a way to align interference terms over each hop in a manner that allows them to be cancelled over the air at the last hop.

Interference alignment increases transmission rate in terms of multiplexing gain for X channel. In this paper, we propose a fixed-rate transmission scheme over a two-user X channel where each of the two double-antenna transmitters has independent messages for each of the two double-antenna receivers. Each transmitter encodes symbols using Alamouti codes followed by beamformers that align interference at unintended receivers. The receiver removes the aligned interference and decouples symbols using interference cancellation followed by symbol-by-symbol decoding. Our analysis shows that the proposed scheme achieves a diversity gain of 2 at the maximum node-to-node symbol-rate of 2 over 3.

In this paper, we explore the possibility of achieving interference alignment with delayed CSIT when the transmitters are distributed. Our main contribution is an interference alignment scheme, called retrospective interference alignment, that is specialized to settings with distributed transmitters. With this scheme we show that the interference channel with 3 users with only delayed channel state information at the transmitters can achieve 9/8 DoF, while the the 2 user X channel is able to achieve 8/7 DoF. We also consider another setting where delayed channel output feedback is available to transmitters. In this setting the 3 user interference channel and the 2 user X channel are shown to achieve 6/5 and 4/3 DoF, respectively.

We explore the interplay between interference, cooperation and connectivity in heterogeneous wireless interference networks. Specifically, we consider a 4-user locally-connected interference network with pairwise clustered decoding and show that its degrees of freedom (DoF) are bounded above by 12/5. Interestingly, when compared to the corresponding fully connected setting which is known to have 8/3 DoF, the locally connected network is only missing interference-carrying links, but still has lower DoF, i.e., eliminating these interference-carrying links reduces the DoF. The 12/5 DoF outer bound is obtained through a novel approach that translates insights from interference alignment over linear vector spaces into corresponding sub-modularity relationships between entropy functions.

Recent results establish the optimality of interference alignment to approach the Shannon capacity of interference networks at high SNR. However, the extent to which interference can be aligned over a finite number of signalling dimensions remains unknown. Another important concern for interference alignment schemes is the requirement of global channel knowledge. In this work, we provide examples of iterative algorithms that utilize the reciprocity of wireless networks to achieve interference alignment with only local channel knowledge at each node. These algorithms also provide numerical insights into the feasibility of interference alignment that are not yet available in theory.

TheN+1 user, 1 ×Nsingle-input multiple-output (SIMO) Gaussian interference channel where each transmitter has a single antenna and each receiver hasNantennas is studied. The sum capacity withinO(1) is characterized for the symmetric case where all direct links have the same signal-to-noise ratio (SNR) and all undesired links have the same interference-to-noise ratio (INR). The gap to the exact capacity is a constant which is independent of SNR and INR. To get this result, we first generalize the deterministic interference channel introduced by El Gamal and Costa to model interference channels with multiple antennas. We derive the capacity region of this deterministic interference channel. Based on the insights provided by the deterministic channel, we characterize the generalized degrees of freedom (GDOF) of Gaussian case, which directly leads to theO(1) capacity approximation. On the achievability side, an interesting conclusion is that the GDOF regime where treating interference as noise is found to be optimal in the two-user interference channel, does not appear in theN+ 1 user, 1 ×NSIMO case. On the converse side, new multiuser outer bounds emerge out of this work that do not follow directly from the two-user case. In addition to the GDOF region, the outer bounds identify a strong interference regime where the capacity region is established.

We explore the degrees of freedom (DoF) of three classes of finite state compound wireless networks in this paper. First, we study the multiple-input single-output (MISO) finite state compound broadcast channel (BC) with arbitrary number of users and antennas at the transmitter. In prior work, Weingartenhave found inner and outer bounds on the DoF with 2 users. The bounds have a different character. While the inner bound collapses to unity as the number of states increases, the outer bound does not diminish with the increasing number of states beyond a threshold value. It has been conjectured that the outer bound is loose and the inner bound represents the actual DoF. In the complex setting (all signals, noise, and channel coefficients are complex variables), we solve a few cases to find that the outer bound—and not the inner bound—of Weingartenis tight. For the real setting (all signals, noise, and channel coefficients are real variables), we completely characterize the DoF, once again proving that the outer bound of Weingartenis tight. We also extend the results to arbitrary number of users. Second, we characterize the DoF of finite state scalar (single antenna nodes) compound$X$networks with arbitrary number of users in the real setting. Third, we characterize the DoF of finite state scalar compound interference networks with arbitrary number of users in both the real and complex setting. The key finding is that scalar interference networks and (real)$X$networks do not lose any DoF due to channel uncertainty at the transmitter in the finite state compound setting. The finite state compound MISO BC does lose DoF relative to the perfect CSIT scenario. However, what is lost is only the DoF benefit of joint processing at transmit antennas, without which the MISO BC reduces to an$X$network.

We identify the role of equal strength interference links as bottlenecks on the ergodic sum capacity of aKuser phase-fading interference network, i.e., an interference network where the fading process is restricted primarily to independent and uniform phase variations while the channel magnitudes are held fixed across time. It is shown that even though there areK(K-1) cross-links, only aboutK/2 disjoint and equal strength interference links suffice to determine the capacity of the network regardless of the strengths of the rest of the cross channels. This scenario is called a minimal bottleneck state. It is shown that ergodic interference alignment is capacity optimal for a network in a minimal bottleneck state. The results are applied to large networks. It is shown that large networks are close to bottleneck states with a high probability, so that ergodic interference alignment is close to optimal for large networks. Limitations of the notion of bottleneck states are also highlighted for channels where both the phase and the magnitudes vary with time. It is shown through an example that for these channels, joint coding across different bottleneck states makes it possible to circumvent the capacity bottlenecks.

We study a layeredK-userM-hop Gaussian relay network consisting ofKmnodes in themthlayer, whereM≥ 2 andK=K1=KM+1. We observe that the time-varying nature of wireless channels or fading can be exploited to mitigate the interuser interference. The proposed amplify-and-forward relaying scheme exploits such channel variations and works for a wide class of channel distributions including Rayleigh fading. We show a general achievable degrees of freedom (DoF) region for this class of Gaussian relay networks. Specifically, the set of all (d1,...,dK) such thatdi≤ 1 for alliand Σi=1K di≤KΣis achievable, wherediis the DoF of theithsource-destination pair andKΣis the maximum integer such thatKΣ≤ minm{Km} andM/KΣis an integer. We show that surprisingly the achievable DoF region coincides with the cut-set outer bound ifM/ minm{Km} is an integer; thus, interference-free communication is possible in terms of DoF. We further characterize an achievable DoF region assuming multi-antenna nodes and general message set, which again coincides with the cut-set outer bound for a certain class of networks.

We propose a blind interference alignment scheme for the vector broadcast channel where the transmitter is equipped with M antennas and there are K receivers, each equipped with a reconfigurable antenna capable of switching among M preset modes. Without any knowledge of the channel coefficient values at the transmitters and with only mild assumptions on the channel coherence structure we show that MK/(M+K-1) degrees of freedom are achievable. The key to the blind interference alignment scheme is the ability of the receivers to switch between reconfigurable antenna modes to create short term channel fluctuation patterns that are exploited by the transmitter. The achievable scheme does not require cooperation between transmit antennas and is therefore applicable to the M×K X network as well. Only finite symbol extensions are used, and no channel knowledge at the receivers is required to null the interference.

We explore a few selected multiuser communication problems where the possibility of interference alignment, and consequently, the total number of degrees of freedom (DoF) with channel uncertainty at the transmitters are unknown. These problems share the common property that in each case the best known outer bounds are essentially robust to channel uncertainty and represent the outcome with interference alignment, but the best inner bounds - in some cases conjectured to be optimal - predict a total collapse of DoF, thus indicating the infeasibility of interference alignment under channel uncertainty at transmitters. Our main contribution is to show that even with no knowledge of channel coefficient values at the transmitters, the knowledge of the channels' correlation structure can be exploited to achieve interference alignment.

It is known that the capacity of parallel (e.g., multi-carrier) Gaussian point-to-point, multiple access and broadcast channels (without common messages) can be achieved by separate encoding for each subchannel (carrier) subject to a power allocation across carriers. Recent results have shown that parallel interference channels are not separable, i.e., joint coding is needed to achieve capacity in general. This work studies the separability, from a sum-capacity perspective, of single hop Gaussian interference networks with independent messages and arbitrary number of transmitters and receivers. The main result is that the only network that is always (for all values of channel coefficients) separable from a sum-capacity perspective is the MAC-Z-BC network, i.e., a network where a MAC component and a BC component are linked by a Z component. The sum capacity of this network is explicitly characterized.

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

We study K-user M-hop Gaussian relay networks with Kmnodes in the m-th layer, where M is even and K = K1= KM+1. We observe that the time-varying nature of wireless channels (fading) can be exploited to mitigate the inter-user interference. The proposed block Markov encoding and relaying scheme exploits such channel variations and works for any isotropically distributed channels including Rayleigh fading. We show a general achievable degrees of freedom (DoF) region of this class of Gaussian relay networks, which coincides with the cut-set outer bound if M/Kminis an integer, where Kmin= minm{Km}. Therefore, we completely characterize the DoF region for the case where M/Kminis an integer.

In this work, we consider a two-hop multiuser amplify-and-forward relay network with multi-antenna nodes. The results are three-fold. First, for any relay amplification matrix D in the multiple-access channel (MAC), we show that duality holds when ¿D¿is employed in the broadcast channel (BC), and vice versa, where re is obtained from switching the total source and relay power constraints. Second, under a total network power constraint, we show that MAC-BC duality holds when D and D¿are the relaying matrices in the MAC and BC respectively. Third, for any D in the MAC and cD¿in the BC where c is any positive real scalar, MAC-BC duality under total network power constraint holds only for the above two cases.

It has been conjectured by Hø-Madsen and Nosratinia that complex Gaussian interference channels with constant channel coefficients have only one degree-of-freedom regardless of the number of users. While several examples are known of constant channels that achieve more than 1 degree-of-freedom, these special cases only span a subset of measure zero. In other words, for almost all channel coefficient values, it is not known if more than 1 degree-of-freedom is achievable. In this paper, we settle the Høst-Madsen-Nosratinia conjecture in the negative. We show that at least 1.2 degrees-of-freedom are achievable for all values of complex channel coefficients except for a subset of measure zero. For the class of linear beamforming and interference alignment schemes considered in this paper, it is also shown that 1.2 is the maximum number of degrees-of-freedom achievable on the complex Gaussian 3 user interference channel with constant channel coefficients, for almost all values of channel coefficients. To establish the achievability of 1.2 degrees-of-freedom we use the novel idea of asymmetric complex signaling - i.e., the inputs are chosen to be complex but not circularly symmetric. It is shown that unlike Gaussian point-to-point, multiple-access and broadcast channels where circularly symmetric complex Gaussian inputs are optimal, for interference channels optimal inputs are in general asymmetric. With asymmetric complex signaling, we also show that the 2 user complex Gaussian X channel with constant channel coefficients achieves the outer bound of 4/3 degrees-of-freedom, i.e., the assumption of time-variations/frequency-selectivity used in prior work to establish the same result, is not needed.

We provide inner bound and outer bound for the total number of degrees of freedom of theKuser multiple-input multiple-output (MIMO) Gaussian interference channel withMantennas at each transmitter andNantennas at each receiver if the channel coefficients are time-varying and drawn from a continuous distribution. The bounds are tight when the ratio [(max(M,N))/(min(M,N))]=Ris equal to an integer. For this case, we show that the total number of degrees of freedom is equal to min(M,N)KifK≤Rand min(M,N)[(R)/(R+1)]KifK>R. Achievability is based on interference alignment. We also provide examples where using interference alignment combined with zero forcing can achieve more degrees of freedom than merely zero forcing for some MIMO interference channels with constant channel coefficients.

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

We consider a cognitive radio system where the secondary transmitter varies its transmit power based on the information available from the spectrum sensor. The operation of the secondary user is governed by its peak transmit power constraint and an average interference constraint at the primary receiver. Without restricting the sensing scheme (total received energy, or correlation etc), we characterize the power adaptation strategies that maximize the secondary user's SNR and capacity. We show that, in general, the capacity optimal power adaptation requires decreasing the secondary transmit power from the peak power to zero in a continuous fashion as the probability of the primary user being present increases. In contrast, we find that that power control that maximizes the SNR is binary, i.e., if there is any transmission, it takes place only at the peak power level. Numerical results for common spectrum sensing schemes show that the SNR and capacity maximizing schemes can be very different. With an average transmit power constraint at the secondary radio, both the SNR and capacity optimal power control schemes are observed to be non-binary. Further, we find that with secondary channel knowledge at the cognitive transmitter, the optimal SNR with an average transmit power constraint is unbounded.

The tradeoff between diversity, interference alignment and rate for a K user multiple-antenna interference network is analyzed. It is assumed that the sources employ a space-time code in combination with linear preceding, while the receiving nodes use linear detectors. We show that interference alignment is needed if the system is operating at or close to the maximum achievable rate. For low rates the preferred strategy is to utilize all antennas in order to achieve high diversity gains, rather than using some of the antennas to align the interference. For the case of K = 3 users, an exact characterization of the tradeoff is provided. We also investigate the impact of channel estimation errors on the diversity of the system. It turns out that small channel estimation errors can be tolerated, while larger errors reduce the diversity gain significantly.

The degrees of freedom (DoF) of K-user MIMO interference networks with constant channel coefficients are not known in general. Determining the feasibility of a linear interference alignment is a key step toward solving this open problem. Our approach in this paper is to view the alignment problem for interference networks as a multivariate polynomial system and determine its solvability by comparing the number of equations and the number of variables. Consequently, we divide the interference networks into two classes proper and improper, where interference alignment is and is not achievable, respectively. An interference network is called proper if the cardinality of every subset of equations in the corresponding polynomial system is less than or equal to the number of variables involved in that subset of equations. Otherwise, it is called improper. Our intuition in this paper is that for general channel matrices, proper systems are almost surely feasible and improper systems are almost surely infeasible. We prove the direct link between proper (improper) and feasible (infeasible) systems for some important cases, thus significantly strengthening our intuition. Numerical simulation results also support our intuition.

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

The N + 1 user, 1 × N single input multiple output (SIMO) Gaussian interference channel where each transmitter has a single antenna and each receiver has N antennas is studied. The symmetric capacity within O(1) is characterized for the symmetric case where all direct links have the same signal-to-noise ratio (SNR) and all undesired links have the same interference-to-noise ratio (INR). The gap to the exact capacity is a constant which is independent of SNR and INR. On the achievability side, an interesting conclusion is that the generalized degrees of freedom (GDOF) regime where treating interference as noise is found to be optimal in the 2 user interference channel, does not appear in the N + 1 user, 1 × N SIMO case. On the converse side, new multi-user outer bounds emerge out of this work that do not follow directly from the 2 user case. We also provide an outer bound on the capacity region of the 3 user SIMO Gaussian interference channel with 2 antennas at each receiver. This outer bound directly leads to the capacity region of this channel if the channel vectors satisfy certain conditions.

We study the sum capacity of the X channel generalization of the symmetric 2-user interference channel. In this X channel, there are 4 independent messages, one from each transmitter to each receiver. We characterize the sum capacity of a deterministic version of this channel, and obtain the generalized degrees of freedom characterization for the Gaussian version. The regime where the X channel outperforms the underlying interference channel is explicitly identified, and an interesting interference alignment scheme based on a cyclic decomposition of the signal space is shown to be optimal in this regime.

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

Cognitive radios hold tremendous promise for increasing spectral efficiency in wireless systems. This paper surveys the fundamental capacity limits and associated transmission techniques for different wireless network design paradigms based on this promising technology. These paradigms are unified by the definition of a cognitive radio as an intelligent wireless communication device that exploits side information about its environment to improve spectrum utilization. This side information typically comprises knowledge about the activity, channels, codebooks, and/or messages of other nodes with which the cognitive node shares the spectrum. Based on the nature of the available side information as well asa priorirules about spectrum usage, cognitive radio systems seek to underlay, overlay, or interweave the cognitive radios' signals with the transmissions of noncognitive nodes. We provide a comprehensive summary of the known capacity characterizations in terms of upper and lower bounds for each of these three approaches. The increase in system degrees of freedom obtained through cognitive radios is also illuminated. This information-theoretic survey provides guidelines for the spectral efficiency gains possible through cognitive radios, as well as practical design ideas to mitigate the coexistence challenges in today's crowded spectrum.

We find the degrees of freedom of a network with S source nodes,Rrelay nodes, and D destination nodes, with random time-varying/frequency-selective channel coefficients and global channel knowledge at all nodes. We allow full-duplex operation at all nodes, as well as causal noise-free feedback of all received signals to all source and relay nodes. An outer bound to the capacity region of this network is obtained. Combining the outer bound with previous interference alignment based achievability results, we conclude that the techniques of relays, feedback, full-duplex operation and noisy cooperation do not increase the degrees of freedom of interference andXnetworks. As a second contribution, we show that for a network withKfull-duplex nodes andK(K-1) independent messages with one message from every node to each of the otherK-1 nodes, the total degrees of freedom are bounded above and below by[(K(K-1))/( (2K-2))] and[(K(K-1))/( (2K-3))], respectively.

We explore the degrees of freedom of M times N user wireless X networks, i.e., networks of M transmitters and N receivers where every transmitter has an independent message for every receiver. We derive a general outer bound on the degrees of freedom region of these networks. When all nodes have a single antenna and all channel coefficients vary in time or frequency, we show that thetotalnumber of degrees of freedom of theXnetwork is equal to [(MN)/(M+N-1)] per orthogonal time and frequency dimension. Achievability is proved by constructing interference alignment schemes for X networks that can come arbitrarily close to the outer bound on degrees of freedom. For the case where either M=2 or N=2 we find that the degrees of freedom characterization also provides a capacity approximation that is accurate to within O(1) . For these cases the degrees of freedom outer bound is exactly achievable.

It is known that the capacity of parallel (multicarrier) Gaussian point-to-point, multiple access and broadcast channels can be achieved by separate encoding for each subchannel (carrier) subject to a power allocation across carriers. In this paper we show that such a separation does not apply to parallel Gaussian interference channels in general. A counterexample is provided in the form of a 3 user interference channel where separate encoding can only achieve a sum capacity of 2 log(1+3 SNR) while the actual capacity, achieved only by joint encoding across carriers, is 3 log(1+2 SNR). As a byproduct of our analysis, we propose a class of multiple-access-outer bounds on the capacity of the 3 user interference channel.

An interference alignment example is constructed for the deterministic channel model of theK-user interference channel. The deterministic channel example is then translated into the Gaussian setting, creating the first known example of a fully connected GaussianK-user interference network with single antenna nodes, real, nonzero and constant channel coefficients, and no propagation delays where the degrees of freedom outerbound is achieved. An analogy is drawn between the propagation delay based interference alignment examples and the deterministic channel model which also allows similar constructions for the two-userXchannel as well.

In wireless relay networks, noise at the relays can be correlated possibly due to common interference or noise propagation from preceding hops. A parallel relay network with noise correlation is considered in this network. For the relay strategy of amplify and forward (AF), the optimal rate maximizing relay gains when correlation knowledge is available at the relays are determined. Interestingly, it is shown that, on average, noise correlation is beneficial regardless of whether the relays know the noise covariance matrix. However, the knowledge of correlation can greatly improve the performance. Typically, the performance improvement from correlation knowledge increases with the relay power and the number of relays. With perfect correlation knowledge the system is capable of canceling interference if the number of interferers is less than the number of relays. For a two-hop multiple-access parallel network, closed-form expressions for the maximum sum rate and the optimal relay strategy are determined. Relay optimization for networks with three hops is also considered. Based on the result of two-hop network with noise correlation, an iterative algorithm is proposed for solving the relay optimization problem for three-hop networks.

In this paper, we explore the benefits, from the perspective of degrees of freedom (DOF), of user cooperation and cognitive message sharing for a two-user multiple-input multiple-output (MIMO) Gaussian interference channel withM1,M2antennas at transmitters andN1,N2antennas at receivers. For the case of user cooperation (including cooperation at transmitters only, at receivers only, and at transmitters as well as receivers), the sum DOF ismin{M1+M2,N1+N2, max(M1,N2), max(M2,N1)} , which is the same as the sum DOF of the channel without cooperation. For the case of cognitive message sharing, the sum DOF ismin{M1+M2,N1+N2, (1-1T2)((1-1R2)max(M1,N2) + 1R2(M1+N2)) + 1T2(M1+M2),(1-1T1)((1-1R1) middotmax(M2,N1) + 1R1(M2+N1)) + 1T1(M1+M2)} where 1Ti= 1 (0) when transmitteriis (is not) a cognitive transmitter and 1Riis defined in the same fashion. Our results show that while both techniques may increase the sum capacity of the MIMO interference channel, only cognitive message sharing can increase the sum DOF. We also find that it may be more beneficial for a user to have a cognitive transmitter than to have a cognitive receiver.

It is known that the capacity of parallel (multi-carrier) Gaussian point-to-point, multiple access and broadcast channels can be achieved by separate encoding for each subchannel (carrier) subject to a power allocation across carriers. In this paper we show that such a separation does not apply to parallel Gaussian interference channels in general. A counter-example is provided in the form of a 3 user interference channel where separate encoding can only achieve a sum capacity of log(SNR) +o(log(SNR)) per carrier while the actual capacity, achieved only by joint-encoding across carriers, is 3/2(log(SNR))+o(log(SNR)) per carrier. As a byproduct of our analysis, we propose a class of multiple-access-outerbounds on the capacity of the 3 user interference channel.

Recent results establish the optimality of interference alignment to approach the Shannon capacity of interference networks at high SNR. However, the extent to which interference can be aligned over a finite number of signalling dimensions remains unknown. Another important concern for interference alignment schemes is the requirement of global channel knowledge. In this work we provide examples of iterative algorithms that utilize the reciprocity of wireless networks to achieve interference alignment with only local channel knowledge at each node. These algorithms also provide numerical insights into the feasibility of interference alignment that are not yet available in theory.

The 4 user single input multiple output (SIMO) Gaussian interference channel where each transmitter has a single antenna and each receiver has two antennas is studied. We show that if the channel coefficients are time-varying and drawn from a continuous distribution, the maximum number of spatial degrees of freedom per orthogonal time dimension for this channel is 8/3 almost surely. Achievability is based on the idea of interference alignment, i.e., signal spaces are aligned at receiver where they constitute interference while they are separable at receivers where they are desired.

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

We show that the sum capacity of the K user frequency selective (or time-varying) interference channel is C(SNR) = (K/2) log(SNR) +o(log(SNR)) meaning that the channel has a total of K/2 degrees of freedom per orthogonal time and frequency dimension. Linear schemes of interference alignment and zero forcing suffice to achieve all the degrees of freedom and multi-user detection is not required.

We study stability regions of multi-rate Gaussian multiple access (MAC) and broadcast (BC) networks with centralized scheduling algorithms. Techniques are presented to characterize stability regions of BC and MAC networks with peak power constraints and average power constraints. The duality property that relates the MAC and BC information theoretic capacity regions is found to extend to their stability regions as well, in the average power constraint case.

We consider a fully connected network with S full duplex source nodes, D full duplex destination nodes and R relay nodes, perfect feedback to source and relay nodes, and noisy cooperation between all source, relay and destination nodes. We show that this network has SD/S+D-1 degrees of freedom if the channel gains are time-varying/frequency selective. The implication of the result is that, the techniques mentioned in the title (i.e relays etc.) can affect the capacity of a network only up to a o(log(SNR)) term and therefore cannot improve the degrees of freedom of a network. Certain communication scenarios excluded by our system model where these techniques improve the degrees of freedom are also identified. Bounds on the degrees of freedom of a fully connected K node network emerge as a by-product of our study.

We study the degrees of freedom characterization of wireless X networks, i.e. networks of M distributed single antenna transmitters and N distributed single antenna receivers where every transmitter has an independent message to every receiver. We provide an outerbound on the capacity region of X networks within o(log(SNR)). If the channel co-efficients are time-varying/frequency selective, we show that the total number of degrees of freedom is equal to MN/M+N-1 using a coding scheme based on the idea of interference alignment.

In this paper, we explore the benefits, in the sense of total (sum rate) degrees of freedom (DOF), of cooperation and cognitive message sharing for a two-user multiple-input-multiple-output (MIMO) Gaussian interference channel with M1, M2antennas at transmitters and N1, N2antennas at receivers. For the case of cooperation (including cooperation at transmitters only, at receivers only, and at transmitters as well as receivers), the DOF is min{M1+ M2,N1+ N2, max(M1,N2), max(M2,N1)}, which is the same as the DOF of the channel without cooperation. For the case of cognitive message sharing, the DOF is min{M1+ M2,N1+N2, (1−1T2)((1–1R2)max(M1,N2)+1R2(M1+N2))+ 1T2(M1+ M2), (1 − 1T1)((1 − 1R1)max(M2,N1) + 1R1(M2+ N1)) + 1T1(M1+ M2)} where 1Ti= 1 (0) when transmitter i is (is not) a cognitive transmitter and 1Riis defined in the same fashion. Our results show that while both techniques may increase the sum rate capacity of the MIMO interference channel, only cognitive message sharing can increase the DOF. We also find that it may be more beneficial for a user to have a cognitive transmitter than to have a cognitive receiver.

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

An interference alignment example is constructed for the deterministic channel model of the K user interference channel. The deterministic channel example is then translated into the Gaussian setting, creating the first known example of a fully connected Gaussian K user interference network with single antenna nodes, real, non-zero and contant channel coefficients, and no propagation delays where the degrees of freedom outerbound is achieved. An analogy is drawn between the propagation delay based interference alignment examples and the deterministic channel model which also allows similar constructions for the 2 user X channel as well.

For the fully connected K user wireless interference channel where the channel coefficients are time-varying and are drawn from a continuous distribution, the sum capacity is characterized as C(SNR)=K/2log(SNR)+o(log(SNR)) . Thus, the K user time-varying interference channel almost surely has K/2 degrees of freedom. Achievability is based on the idea of interference alignment. Examples are also provided of fully connected K user interference channels with constant (not time-varying) coefficients where the capacity is exactly achieved by interference alignment at all SNR values.

We provide achievability as well as converse results for the degrees of freedom region of a multiple-input multiple-output (MIMO)$X$channel, i.e., a system with two transmitters, two receivers, each equipped with multiple antennas, where independent messages need to be conveyed over fixed channels from each transmitter to each receiver. The inner and outer bounds on the degrees of freedom region are tight whenever integer degrees of freedom are optimal for each message. With$M=1$antennas at each node, we find that the total (sum rate) degrees of freedom are bounded above and below as$1 \leq \eta _{X}^{\star} \leq {{ 4}\over { 3}}$. If$M>1$and channel matrices are nondegenerate then the precise degrees of freedom$\eta _{X}^{\star} = {{ 4}\over { 3}}M$. Thus, the MIMO$X$channel has noninteger degrees of freedom when$M$is not a multiple of$3$. Simple zero forcing without dirty paper encoding or successive decoding, suffices to achieve the${{ 4}\over { 3}}M$degrees of freedom. If the channels vary with time/frequency then the$X$channel with single antennas$(M=1)$at all nodes has exactly${4\over 3}$degrees of freedom. The key idea for the achievability of the degrees of freedom isinterference alignment—i.e., signal spaces are aligned at receivers where they constitute interference while they are separable at receivers where they are desired. We also explore the increase in degrees of freedom when some of the messages are made available to a transmitter or receiver in the manner of cognitive radio.

We explore the performance tradeoff between opportunistic and regulated access inherent in the design of multiuser cognitive radio networks. We consider a multichannel cognitive radio system with sensing limits at the secondary users and interference tolerance limits at the primary and secondary users. Our objective is to determine the optimal amount of spectrum sharing, i.e., the number of secondary users that maximizes the total deliverable throughput in the network.We begin with the case of perfect primary user detection and zero interference tolerance at each of the primary and secondary nodes. With identical primary and secondary traffic statistics, we find that the optimal fraction of licensed users lies between the two extremes of fully opportunistic and fully licensed operation and is equal to the traffic duty cycle. When the secondary users can vary their transmission probabilities based on the number of active primary users, we find that the optimal number of opportunistic users is equal to the average number of unoccupied channels. We then consider the more involved case of imperfect sensing and non-zero interference tolerance constraints. We provide numerical simulation results to study the tradeoff between licensing and autonomy and the impact of primary user sensing and interference tolerance on the deliverable throughput for two different subchannel selection strategies at the secondary users.

In wireless relay networks, noise at the relays can be correlated possibly due to common interference or noise propagation from preceding hops. In this work we consider a parallel relay network with noise correlation. For the relay strategy of amplify-and-forward (AF), we determine the optimal rate maximizing relay gains when correlation knowledge is available at the relays. The effect of correlation on the performance of the relay networks is analyzed for the cases where full knowledge of correlation is available at the relays and when there is no knowledge about the correlation structure. Interestingly we find that, on the average, noise correlation is beneficial regardless of whether the relays know the noise covariance matrix or not. However, the knowledge of correlation can greatly improve the performance. Typically, the performance improvement from correlation knowledge increases with the relay power and the number of relays. With perfect correlation knowledge the system is capable of canceling interference if the number of interferers is less than the number of relays.

We provide achievability as well as converse results for the degrees of freedom region of a MIMO X channel, i.e., a system with two transmitters, two receivers, each equipped with multiple antennas, where independent messages need to be conveyed over fixed channels from each transmitter to each receiver. The inner and outerbounds on the degrees of freedom region are tight whenever integer degrees of freedom are optimal for each message. If all nodes have equal number of antennas M > 1 and channel matrices are non-degenerate then the degrees of freedom etaX* = 4/3 M. If the channels vary with time/frequency then the X channel with single antennas (M = 1) at all nodes has 4/3 degrees of freedom. Thus, the MIMO X channel has non-integer degrees of freedom when M is not a multiple of 3. Simple zero forcing without dirty paper encoding or successive decoding, suffices to achieve the 4/3 M degrees of freedom in all cases. The key idea for the achievability of the degrees of freedom is interference alignment - i.e., signal spaces are aligned at receivers where they constitute interference while they are separable at receivers where they are desired. With equal number of antennas at all nodes, we also explore the increase in degrees of freedom when some of the messages are made available to a transmitter or receiver in the manner of cognitive radio.

We consider a cognitive radio system where the secondary transmitter varies its transmit power based on all the information available from the spectrum sensor. The operation of the secondary user is governed by its peak transmit power constraint and an average interference constraint at the primary receiver. Without restricting the sensing scheme (total received energy, or correlation etc), we characterize the power adaptation strategies that maximize the secondary user's SNR and capacity. We show that, in general, the capacity optimal power adaptation requires decreasing the secondary transmit power from the peak power to zero in a continuous fashion as the probability of the primary user being present increases. We find that power control that maximizes the SNR is binary, i.e., if there is any transmission, it takes place only at the peak power level. Numerical results for common spectrum sensing schemes show that the SNR and capacity maximizing schemes can be significantly different.

We explore the performance tradeoff between opportunistic and regulated access inherent in the design of multiuser cognitive radio networks. We consider a cognitive radio system with sensing limits at the secondary users and interference tolerance limits at the primary and secondary users. Our objective is to determine the optimal amount of spectrum sharing, i.e., the number of secondary users that maximizes the total deliverable throughput in the system. We begin with the case of perfect primary user detection and zero interference tolerance at each of the primary and secondary nodes. We find that the optimal fraction of licensed users lies between the two extremes of fully opportunistic and fully licensed operation and is equal to the traffic duty cycle. For the more involved case of imperfect sensing and non-zero interference tolerance constraints, we provide numerical simulation results to study the tradeoff between licensing and autonomy and the impact of primary user sensing and interference tolerance on the deliverable throughput.

We consider multi-hop multiple access (MAC) and broadcast channels (BC) where communication takes place with the assistance of relays that amplify and forward (AF) their received signals. For a two hop parallel AF relay MAC, assuming a sum power constraint across all relays we characterize optimal relay amplification factors and the resulting capacity regions. We find that the parallel AF relay MAC with total transmit power of the two users P1+P2=P and total relay power PRis the dual of the parallel AF relay BC where the MAC source nodes become the BC destination nodes, the MAC destination node becomes the BC source node, the dual BC source transmit power is PRand the total transmit power of the AF relays is P.

We explore the SNR-optimal relay functionality in a mernoryless relay network, i.e. a network where, during each channel use, the signal transmitted by a relay depends only on the last received symbol at that relay. We develop a generalized notion of SNR for the class of memoryless relay functions. The solution to the generalized SNR optimization problem leads to the novel concept of minimum mean squared uncorrelated error (MMSUE) estimation. For the elemental case of a single relay, we show that MMSUE estimate is a scaled version of the MMSE estimate. This scheme, that we call estimate and forward (EF), performs better than the best of amplify and forward (AF) and demodulate and forward (DF) in both parallel and serial relay networks. We determine that AF is near-optimal at low transmit power in a parallel network, while DF is near-optimal at high transmit power in a serial network. For hybrid networks that contain both serial and parallel elements, the advantage of EF over the best of AF and DF is found to be significant. Error probabilities are provided to substantiate the performance gain obtained through SNR optimality. We also show that, for Gaussian inputs, AF, DF and EF are identical

We investigate the capacity of opportunistic communication in the presence of dynamic and distributed spectral activity, i.e., when the time varying spectral holes sensed by the cognitive transmitter are correlated but not identical to those sensed by the cognitive receiver. We develop a two switch model that captures the localized spectral activity estimates at the transmitter and receiver. The information theoretic framework of communication with side information is employed to characterize the capacity of the cognitive link with both causal and non-causal side information at the transmitter and/or the receiver. These capacity results are used to determine the benefits of any feedforward and feedback information. We find that cognitive radio capacity is robust to the uncertainties arising out of distributed and dynamic spectral environments, even when the communication occurs in bursts of only 3-5 symbols. The capacity depends strongly on the correlation of the local spectral environment at the cognitive transmitter and receiver.

We investigate the performance degradation of basic modulation schemes in a rapidly time-varying channel using a first-order autoregressive channel model. Various performance metrics are used to indicate the relative advantages of each modulation scheme. We find that noncoherent frequency-shift keying (FSK) is suitable for operating at very high mobility and high signal-to-noise ratio, ideal for some military applications. We then propose a partially coherent detector for FSK and differential phase-shift keying that exploits partial channel knowledge to enable the receiver to operate effectively in both fast and slow fading. The maximum-likelihood rule obtained for the partially coherent FSK turns out to be a linear combination of coherent and noncoherent detection rules. Results demonstrate that significant performance improvement can be achieved over the best of coherent and noncoherent FSK detection. The detector is robust to estimation errors present in the channel statistics. We also propose a few adaptive schemes that employ various combinations of modulation schemes to increase the robustness of the system in fast fading

The ergodic capacity of a fading vector channel with multiple transmit antennas and a single receive antenna is explored. Perfect channel information is assumed to be available at the receiver while the transmitter has only partial knowledge of the direction of the user's channel vector based on quantized feedback. We present necessary and sufficient conditions for the optimality of beamforming in such systems. The conditions are applicable to all quantized feedback scenarios regardless of the channel distribution, number of transmit antennas, number of quantization vectors or transmit power. The optimality conditions are closely related to the iteration conditions of the Lloyd algorithm, revealing an interesting link between the optimality of beamforming and the optimality of the vector quantizers. Using the conditions, we prove the capacity optimality of beamforming for several quantized feedback scenarios such as the antenna-selection scheme. We also point out examples of quantized feedback scenarios where beamforming is not optimal. We find that for the independent identically distributed Rayleigh fading channel with more than a single bit of quantized feedback, there is no capacity benefit from increasing the number of antennas beyond the number of quantization vectors. Extensions of the necessary and sufficient optimality condition to the multiple-input multiple-output case are also provided.

In this correspondence, we show that the exact number of spatial degrees of freedom (DOF) for a two user nondegenerate (full rank channel matrices) multiple-input-multiple-output (MIMO) Gaussian interference channel with M1, M2 antennas at transmitters 1, 2 and N1, N2 antennas at the corresponding receivers, and perfect channel knowledge at all transmitters and receivers, is min{M1 + M2, N1 + M2, max(M1, N2), max(M2, N1)}. A constructive achievability proof shows that zero forcing is sufficient to achieve all the available DOF on the two user MIMO interference channel. We also show through an example of a share-and-transmit scheme how the gains of transmitter cooperation may be entirely offset by the cost of enabling that cooperation so that the available DOF are not increased.

In this paper, we consider multihop multiple access (MAC) and broadcast channels (BC) where communication takes place with the assistance of relays that amplify and forward (AF) their received signals. For a two-hop parallel AF relay MAC, assuming a sum power constraint across all relays we characterize optimal relay amplification factors and the resulting optimal rate regions. We find the maximum sum rate and the maximum rate for each user in closed form and express the optimal rate pair (R1, R2) that maximizes mu1R1+mu2R2as the solution of a pair of simultaneous equations. We find that the parallel AF relay MAC with total transmit power of the two users P1+P2=P and total relay power PRis the dual of the parallel AF relay BC where the MAC source nodes become the BC destination nodes, the MAC destination node becomes the BC source node, the dual BC source transmit power is PRand the total transmit power of the AF relays is P. The duality means that the rate region of the AF relay MAC with a sum power constraint P on the transmitters is the same as that of the dual BC. The duality relationship is found to be useful in characterizing the rate region of the AF relay BC as the union of MAC rate regions. The duality is established for distributed multiple antenna AF relay nodes and multiple (more than 2) hops as well.

The optimality of transmit beamforming for a multiple antenna system with partial/limited feedback is investigated and a single general necessary and sufficient condition for beamforming to achieve ergodic capacity is derived. The condition obtained is universal - applicable to all partial/limited feedback scenarios in all ergodic fading channel distributions regardless of the number of transmit/receive antennas or transmit power. Using the universal condition we explore the optimality of beamforming for the quantized mean feedback scheme, which unifies previous results for the separate cases of mean feedback and quantized feedback. Numerical results are provided to complement the analysis

In a relay network, the signal processing at the relay significantly affects the capacity benefits of cooperation. In this work, we explore the optimal relay functionality for capacity maximization in a memoryless relay network, i.e. a network where, during each channel use, the signal transmitted by a relay depends only on the last received symbol at that relay. By relating some of the existing memoryless forwarding strategies to the fundamental signal processing operations of estimation and detection, we develop a new scheme that forwards the unconstrained minimum mean square error (MMSE) estimate obtained at the relay to the destination. For a single relay system, we derive the characterization of the optimal relay function and show that the relay function of EF (estimate and forward) satisfies the optimality condition. For the multiple relay case, we consider both parallel and serial relay networks and show that EF performs better than both AF (amplify and forward) and DF (demodulate and forward). For hybrid networks that contain both serial and parallel elements, and when robust performance is desired at all SNR, the advantage of EF over the best of AF and DF is found to be significant.

We investigate the capacity of opportunistic communication in the presence of dynamic and distributed spectral activity, i.e. when the time varying spectral holes sensed by the cognitive transmitter are correlated but not identical to those sensed by the cognitive receiver. Using the information theoretic framework of communication with causal and non-causal side information at the transmitter and/or the receiver, we obtain analytical capacity expressions and the corresponding numerical results. We find that cognitive radio communication is robust to dynamic spectral environments even when the communication occurs in bursts of only 3 - 5 symbols. The value of handshake overhead is investigated for both lightly loaded and heavily loaded systems. We find that the capacity benefits of overhead information flow from the transmitter to the receiver is negligible while feedback information overhead in the opposite direction significantly improves capacity.

We explore the tradeoff between hopping and spreading in a wideband spread spectrum transmitter-receiver link in an ad-hoc network with multi-user interference. The receiver is assumed to track the user's channel, spreading signature and the overall SINR. Using expressions for the ergodic capacity of the link, we determine the amount of spreading required that maximizes the link capacity. As a comparison we also discuss optimal spreads in centralized architectures where the receiver has interference knowledge. While we find that in general a combination of spreading and hopping may achieve higher throughputs than either pure spreading or pure hopping, we prove that pure hopping and pure spreading are optimal strategies for ad-hoc networks at low SINR and for centralized networks at all SINR, respectively. Numerical results suggest that in an ad-hoc network, spreading is beneficial at high SNR.

We explore the available degrees of freedom (DoF) for the two user MIMO interference channel, and find a general inner bound and a genie aided outer bound that give us the exact # of DoF in many cases. We also study a share-and-transmit scheme and show how the gains of transmitter cooperation are entirely offset by the cost of enabling that cooperation so that the available DoF are not increased

We explore the capacity of opportunistic secondary (cognitive) communication over a spectral pool of two independent channels. Due to the distributed nature of the primary user's spectral activity, the cognitive receiver does not have full knowledge of the channel used at the transmitter for secondary communication. Tracking the transmitter state at the receiver is therefore a primary issue in such channels. The problem is further complicated as the channel availability changes with time. The tracking uncertainty also makes decoding at the receiver non-trivial. Using genie based outer bounds and training based lower bounds, we estimate the capacity of the secondary link. The capacity analysis shows that the benefits of spectral pooling are lost in dynamic spectral environments

We investigate the performance degradation due to rapidly time varying channels in a repetition based coherent cooperative system. We demonstrate that mobility of source affects the performance much more than the mobility of destination, for both amplify and forward (AF) and demodulate and forward (DF) relays, despite the symmetry of the network. Exploiting the property of FSK modulation that allow us to detect either coherently or noncoherently or even semi-coherently, we develop ML detection rules for a variety of mobile scenarios. The detection rules that take into account the mobility of the nodes, are mostly hybrids of partially coherent detectors and noncoherent detectors. The performance of these detectors is better than the best of coherent and noncoherent detectors in fast fading and a gain of about 2 dB is obtained over a wide range of SNR and a gain of almost 3 dB is achieved at the crossing of coherent and noncoherent curves. As energy efficiency is one of the main objectives for pursuing cooperation and relaying, these hybrid detectors assume significance in fast fading scenarios

We investigate the performance degradation of basic modulation schemes in a rapidly time varying channel using a first order auto regressive channel model. We propose a partially coherent detector for both noncoherent frequency shift keying (FSK) and differential phase shift keying (PSK) that exploits partial channel knowledge to enable the receiver to operate effectively in both fast and slow fading. The maximum likelihood rule (ML) obtained for the partially coherent FSK turns out to be a linear combination of coherent and noncoherent detection rule. Results demonstrate that significant performance improvement can be achieved over the best of coherent and noncoherent FSK detection in fast fading. We also propose a few adaptive schemes that vary the modulation scheme in response to degrading quality of the channel estimate between successive training symbols

In this correspondence, we determine the feedback capacity region of a two user Gaussian multiple-access channel (MAC) with multiple antennas at the base station and a single antenna at each user. The vector MAC with a single antenna at the base station and multiple antennas at each user is shown to be equivalent to a scalar MAC. We also determine the capacity enhancement due to feedback at high signal-to-noise ratio (SNR) for the scalar and vector MAC for any number of users. Extensions of the high SNR results to the vector broadcast channel are also provided.

We explore the optimality of transmit beamforming for a vector channel with multiple transmit antennas and a single receive antenna. Perfect channel information is assumed to be available at the receiver while the transmitter only has partial/limited knowledge of the user's channel vector based on feedback. Without limiting the kind of partial/limited feedback or the type of channel distribution, we derive a general necessary and sufficient condition for the optimality of beamforming in such channels. The condition we obtain is universal - applicable to all partial/limited feedback scenarios in all ergodic fading channel distributions regardless of the number of transmit antennas or transmit power. Considering different types of partial/limited feedback, we show how our conditions can be employed to obtain previous results on the optimality of beamforming. With Monte Carlo simulations, we provide numerical results comparing different partial/limited feedback schemes.

We explore the capacity of an isotropic fading vector channel with multiple transmit antennas at the base station and a single antenna at the mobile receiver. Perfect channel knowledge is assumed to he available at the receiver while the transmitter has only partial knowledge of the direction of the user's channel vector based on quantized feedback. We determine a necessary and sufficient condition for optimality of beamforming, which turns out to be a precise relationship between the optimality of beamforming and the symmetry of the quantizer. For the cases where beamforming is not optimal, we develop upper and lower bounds. Numerical results are provided to help estimate the capacity.

Opportunistic beamforming with proportional fair scheduling is a very promising technique that exploits multiuser diversity to achieve high data rates on the downlink while ensuring a certain level of fairness. However, it greatly improves system performance only for a sufficiently large mobile user population. This paper proposes a technique enhancing opportunistic beamforming at the transmitter with antenna selection at each mobile receiver to overcome this limitation. Significant performance improvement is achieved, especially for small number of users. The simplicity and inexpensive deployment of this technique make it a highly desirable enhancement to opportunistic beamforming.

We show that for highly mobile ad hoc networks, the benefits of mobility are overshadowed by the cost of mobility in terms of the increased channel uncertainty and network homogeneity. We assume a block-fading channel model with jointly isotropic fading. We allow relays which can transmit and receive simultaneously. Under fairly general assumptions for the users' channel fades and additive noise distributions we show that increasing the number of transmit antennas M at any node beyond the channel coherence time Tc(measured in units of channel uses) does not affect the capacity region of the ad hoc network. For a fast-fading (coherence time TclesM) homogeneous network, we determine the exact capacity region of the ad hoc network for any partition of the nodes into source, destination, and relay nodes. The optimal strategy is such that only one pair of source-destination nodes is active at a time while all the other nodes are inactive. There is no benefit from relaying and at high signal-to-noise ratio (SNR) the total throughput grows at most double-logarithmically with the number of nodes. Even for the case of slow fading, where the channel variations are slow enough that the receiver can track the channel perfectly, the inability of the transmitter to track the network topology limits the total throughput growth rate to no more than logarithmic in the number of nodes. Spatial correlation is shown to enhance the capacity region of the Rayleigh-fading ad hoc network

We propose a scalar upper bound on the capacity region of the isotropic fading vector broadcast channel in terms of the capacity region of a scalar fading broadcast channel. The scalar upper bound is applicable to the broad class of isotropic fading broadcast channels regardless of the distribution of the users' channel magnitudes, the distribution of the additive noise experienced by each user, or the amount of channel knowledge available at the receiver. Using this upper bound, we prove the optimality of the Alamouti scheme in a broadcast setting, extend the recent results on the capacity of nondegraded, fading scalar broadcast channels to nondegraded fading vector broadcast channels, and determine the capacity region of a fading vector Gaussian broadcast channel with channel magnitude feedback. We also provide an example of a Rayleigh-fading broadcast channel with no channel state information available to the receiver (CSIR), where the bound on the capacity region obtained by a naive application of the scalar upper bound is provably loose, because it fails to account for the additional loss in degrees of freedom due to lack of channel knowledge at the receiver. A tighter upper bound is obtained by separately accounting for the loss in degrees of freedom due to lack of CSIR before applying the scalar upper bound.

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

We analyze a mobile multiple input multiple output wireless link with M transmit and N receive antennas operating in a spatially correlated Rayleigh flat fading environment. Only the correlations between the channel coefficients are assumed to be known at the transmitter and the receiver. The channel coefficients are correlated in space and uncorrelated in time from one coherence interval to another. These coefficients remain constant for a coherence interval of T symbol periods after which they change to another independent realization according to the spatial correlation model. For this system we characterize the structure of the input signal that achieves capacity. The capacity achieving transmit signal is expressed as the product of an isotropically distributed unitary matrix, an independent nonnegative diagonal matrix and a unitary matrix whose columns are the eigenvectors of the transmit fade covariance matrix. For the case where the number of transmit antennas M is larger than the channel coherence interval T, we show that the channel capacity is independent of the smallest M-T eigenvalues of the transmit fade covariance matrix. In contrast to the previously reported results for the spatially white fading model where adding more transmit antennas beyond the coherence interval length (M>T) does not increase capacity, we find that additional transmit antennas always increase capacity as long as their channel fading coefficients are spatially correlated with the other antennas. We show that for fast hopping or fast fading systems (T=1) with only channel covariance information available to the transmitter and receiver, transmit fade correlations are beneficial. Mathematically, we prove this by showing that capacity is a Schur-convex function of the vector of eigenvalues of the transmit fade correlation matrix. We also show that the maximum possible capacity gain due to transmitter fade correlations is 10logM dB.

We consider a K user isotropic fast fading ad-hoc network with no channel state information at any transmitter or receiver. Assuming that the users' channels are identically distributed, we determine the capacity region of this ad-hoc network for any partition of the users into transmitters and receivers. The optimal strategy is such that only one pair of transmit-receive nodes is active at a time while all the other nodes are inactive. There is no benefit from cooperation and the total throughput grows at most double-logarithmically with the number of nodes. Even if the channel variations are slow enough that the receiver can track the channel perfectly, the inability of the transmitter to track the network topology limits the total throughput growth rate to no more than logarithmic in the number of nodes. Our analysis extends Hochwald and Marzetta's single user Rayleigh fading AWGN channel result to show that under the more general model of an isotropic fading ad-hoc network with arbitrary distribution of additive noise there is no capacity benefit from increasing the number of transmit antennas beyond the channel coherence time T/sub c/.

We develop an upperbound on the capacity region of an isotropic fading vector broadcast channel in terms of the capacity region of a scalar fading broadcast channel. Using this upperbound we prove the optimality of the Alamouti scheme [1] in a broadcast setting and extend the recent results [2] on the capacity region of the fading scalar non-degraded broadcast channel to fading vector non-degraded broadcast channels. The upperbound is fundamental in that it makes no assumption regarding the distribution of the users' channel magnitudes, the distribution of the additive noise, or the amount of channel information available at the receiver. The scalar upperbound explicitly characterizes the loss of degrees of freedom in a vector broadcast channel when the transmitter has no information about the "direction" of the users' channel vectors.

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

We solve the transmitter optimization problem and determine a necessary and sufficient condition under which beamforming achieves Shannon capacity in a linear narrowband point-to-point communication system employing multiple transmit and receive antennas with additive Gaussian noise. We assume that the receiver has perfect channel knowledge while the transmitter has only knowledge of either the mean or the covariance of the channel coefficients. The channel is modeled at the transmitter as a matrix of complex jointly Gaussian random variables with either a zero mean and a known covariance matrix (covariance information), or a nonzero mean and a white covariance matrix (mean information). For both cases, we develop a necessary and sufficient condition for when the Shannon capacity is achieved through beamforming; i.e., the channel can be treated like a scalar channel and one-dimensional codes can be used to achieve capacity. We also provide a waterpouring interpretation of our results and find that less channel uncertainty not only increases the system capacity but may also allow this higher capacity to be achieved with scalar codes which involves significantly less complexity in practice than vector coding.

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

We determine the optimal adaptive rate and power control strategies to maximize the total throughput in a multirate code-division multiple-access system. The total throughput of the system provides a meaningful baseline in the form of an upper bound to the throughput achievable with additional restrictions imposed on the system to guarantee fairness. Peak power and instantaneous bit energy-to-noise spectral density constraints are assumed at the transmitter with matched filter detection at the receiver. Our results apply to frequency selective fading in so far as the bit energy-to-equivalent noise power spectral density ratio definition can be used as the quality-of-service metric. The bit energy-to-equivalent noise power spectral density ratio metric coincides with the bit-error rate metric under the assumption that the processing gains and the number of users are high enough so that self-interference can be neglected. We first obtain results for the case where the rates available to each user are unrestricted, and we then consider the more practical scenario where each user has a finite discrete set of rates. An upper bound to the maximum average throughput is obtained and evaluated for Rayleigh fading. Suboptimal low-complexity schemes are considered to illustrate the performance tradeoffs between optimality and complexity. We also show that the optimum rate and power adaptation scheme with unconstrained rates is in fact just a rate adaptation scheme with fixed transmit powers, and it performs significantly better than a scheme that uses power adaptation alone.

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

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

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