Search

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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\rightarrow \infty)$ 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. [ABSTRACT FROM AUTHOR]

A locally decodable code (LDC) maps $K$ source symbols, each of size $L_{w}$ bits, to $M$ coded symbols, each of size $L_{x}$ bits, such that each source symbol can be decoded from $N \leq 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 $L_{w}/L_{x}$ is 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\left ({1+1/N+1/N^{2}+\cdots +1/N^{K-1}}\right)^{-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 = N^{K}$. 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). [ABSTRACT FROM AUTHOR]

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 $(\rho _{\min }-X-T)/N$ , where $N$ is the total number of servers, and each message is replicated at least $\rho _{\min }$ times. 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/\nu _{2}(G)$ where $\nu _{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\in E$ between vertices $u,v$ only if a subset of messages is replicated at both servers $u$ and $v$. [ABSTRACT FROM AUTHOR]

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 $N_{1}$ and $N_{2}$ antennas, and the levels of channel state information at the transmitter (CSIT) for the two users are parameterized by $\beta _{1}, \beta _{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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The two-user computation broadcast problem is introduced as the setting where User 1 wants message $W_{1}$ and has side-information $W_{1}'$ , User 2 wants message $W_{2}$ and has side-information $W_{2}'$ , and $(W_{1}, W_{1}', W_{2}, W_{2}')$ may have arbitrary dependencies. The rate of a computation broadcast scheme is defined as the ratio $H(W_{1},W_{2})/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 $C_ {{{{CB}}}}$. It is shown that $C_ {{{{CB}}}}\leq H(W_{1},W_{2})/\bigg [H(W_{1}|W_{1}')+H(W_{2}|W_{2}')-\min \Big (I(W_{1}; W_{2}, W_{2}'|W_{1}'), I(W_{2}; W_{1}, W_{1}'|W_{2}')\Big)\bigg]$. For the linear computation broadcast problem, where $W_{1}, W_{1}', W_{2}, W_{2}'$ 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 $\{W_{1},W_{1}',W_{2},W_{2}'\}$ , 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. [ABSTRACT FROM AUTHOR]

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 $\alpha _{ij}$ representing the channel strength parameter for the link from the $j^{th}$ antenna of the transmitter to the $i^{th}$ receiver, we prove that the SLS is GDoF optimal without the need for time-sharing if $\max (\alpha _{ki},\alpha _{im})\leq \alpha _{ii}$ and $\alpha _{ki}+\alpha _{im}\le \alpha _{ii}+\alpha _{km}$ for all $i,k\in [{3}],m\in [M]$. The GDoF region under this condition is a convex polyhedron. The result generalizes to arbitrary $M\geq 3$. [ABSTRACT FROM AUTHOR]

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}=\left ({1+1/ {N}+\cdots +1/ {N}^{ {K}-1}}\right)^{-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}\rightarrow \infty $. [ABSTRACT FROM AUTHOR]

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 $\sim P$ , while each undesired channel has strength $\sim P^\alpha $ , 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 $\alpha $ 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. [ABSTRACT FROM AUTHOR]

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 $\alpha $ and the same channel uncertainty parameter $\beta $. The main challenge resides in the proof of the outer bound which is accomplished by a generalization of the aligned image sets approach. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper obtains the first degrees of freedom (DoFs) bound that is provably sensitive tonetworkcoherence 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 Gouet 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 $T_{c}=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. [ABSTRACT FROM AUTHOR]

Private information retrieval (PIR) is the problem of retrieving one message out of $K$ messages from $N$ non-communicating 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 $\epsilon $ -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, $\epsilon $ -error PIR scheme that requires a strictly smaller storage overhead than the best possible with single-round, linear, zero-error PIR schemes. [ABSTRACT FROM AUTHOR]

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 \geq N$ databases, out of which any M - N$ may fail to respond. For K$ messages and . The result includes as special cases the capacity of PIR without robustness ( $M=N$ ) or $T$ -privacy constraints ( $T=1$ ). [ABSTRACT FROM AUTHOR]

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 K_{c} belongs 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. [ABSTRACT FROM AUTHOR]

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 $\alpha $ 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. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

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 . 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. [ABSTRACT FROM PUBLISHER]

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((\sqrt {P})^\alpha ) , representing the concentration of probability density (improving CSIT) due to, e.g., quantized feedback at rate ({\alpha }/{2})\log (P)$ , then the DoF is bounded above by $1+\alpha $ , 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\times N$ user $X$ networks as well. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 \(\mathbb {F}_{\!p^n}\) are analogous to \(n\times n\) vector (MIMO) channels in the wireless setting, but with an important distinction—there is additional structure due to finite field 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 field 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 field networks over \(\mathbb {F}_{\!p^n}\) 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

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 of d survivor 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 \leq d \leq n-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set of r \leq n-k failed 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. [ABSTRACT FROM PUBLISHER]

We show that the 2\,\times \,2\,\times \,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. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

We identify the role of equal strength interference links as bottlenecks on the ergodic sum capacity of a K user 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 are K(K-1) cross-links, only about K/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. [ABSTRACT FROM AUTHOR]

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, Weingarten have 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 Weingarten is 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 Weingarten is 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. [ABSTRACT FROM AUTHOR]

The N+1 user, 1 \times 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 sum capacity within \cal 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. 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 the \cal O(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 the N+1 user, 1 \times N SIMO 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. [ABSTRACT FROM AUTHOR]

We provide inner bound and outer bound for the total number of degrees of freedom of the K user multiple-input multiple-output (MIMO) Gaussian interference channel with M antennas at each transmitter and N antennas 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) \over \min(M,N)=R is equal to an integer. For this case, we show that the total number of degrees of freedom is equal to \min(M,N)K if K \leq R and \min(M,N)R \over R+1K if K > 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. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM PUBLISHER]

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-tonoise 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. [ABSTRACT FROM AUTHOR]

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 ,cD† is employed in the broadcast channel (BC), and vice versa, where ic 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. [ABSTRACT FROM AUTHOR]

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 with M1, M2 antennas at transmitters and N1, N2 antennas 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 is min {M1 M1,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 is min{M1, M2 + N2, (1 - 1T2) ((1 - 1R2 max(M1, N2) + 1R2, (M1, N2)) + 1T2M1 + M2, (1 - 1T1)((1 - 1R1) ⋅ max(M2, N1) + 1R1M2 + N1) + 1T1M1 + M2)} where 1Ti = 1(0) when transmitter i is (is not) a cognitive transmitter and 1Ri is 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. [ABSTRACT FROM AUTHOR]

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 counter example 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. [ABSTRACT FROM AUTHOR]

We explore the degrees of freedom of M x 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 the total number of degrees of freedom of the X network 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. [ABSTRACT FROM AUTHOR]

We find the degrees of freedom of a network with S source nodes, B relay 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 achiev-ability results, we conclude that the techniques of relays, feedback, full-duplex operation and noisy cooperation do not increase the degrees of freedom of interference and X networks. As a second contribution, we show that for a network with K full-duplex nodes and K ( K - 1) independent messages with one message from every node to each of the other K - 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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, 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-user X channel as well. [ABSTRACT FROM AUTHOR]

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/2 log(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. [ABSTRACT FROM AUTHOR]

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 Light 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 ≤ η*X ≤ 4/3. If M > 1 and channel matrices are nondegenerate then the precise degrees of freedom η*X = 4/3 M. Thus, the MIMO X channel has noninteger degrees of freedom when M is nota multiple of 3. Simple zero forcing without dirty paper encoding or successive decoding, suffices to achieve the 4/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/3 degrees of freedom. 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 white 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. [ABSTRACT FROM AUTHOR]

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 beam- forming 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. [ABSTRACT FROM AUTHOR]

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 μ R1 + μ2 R2 as 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 PR is 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 PR and 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. [ABSTRACT FROM AUTHOR]

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 + N2, 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. [ABSTRACT FROM AUTHOR]

Cognitive radios are promising solutions to the problem of overcrowded spectrum. In this article we explore the throughput potential of cognitive communication. Different interpretations of cognitive radio that underlay, overlay, and interweave the transmissions of the cognitive user with those of licensed users are described. Considering opportunistic communication as a baseline, we investigate the through- put improvements offered by the overlay methods. Channel selection techniques for opportunistic access such as frequency hopping, frequency tracking, and frequency coding are presented. The trade-off between regulation and autonomy inherent in the design and performance of cognitive networks is examined through a simple example, which shows that the optimal amount of licensing is equal to the duty cycle of the traffic arrivals. [ABSTRACT FROM AUTHOR]