Search

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.

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

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 transmit- ters 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 (?1 × ?1)(?2 × ?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 ?1 < ?1 < min(?2,?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.

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.

Double blind $T$-private information retrieval (DB-TPIR) enables two users,each of whom specifies an index ($\theta_1, \theta_2$, resp.), to efficientlyretrieve a message $W(\theta_1,\theta_2)$ labeled by the two indices, from aset of $N$ servers that store all messages $W(k_1,k_2),k_1\in\{1,2,\cdots,K_1\}, k_2\in\{1,2,\cdots,K_2\}$, such that the two users'indices are kept private from any set of up to $T_1,T_2$ colluding servers,respectively, as well as from each other. A DB-TPIR scheme based oncross-subspace alignment is proposed in this paper, and shown to becapacity-achieving in the asymptotic setting of large number of messages andbounded latency. The scheme is then extended to $M$-way blind $X$-secure$T$-private information retrieval (MB-XS-TPIR) with multiple ($M$) indices,each belonging to a different user, arbitrary privacy levels for each index($T_1, T_2,\cdots, T_M$), and arbitrary level of security ($X$) of datastorage, so that the message $W(\theta_1,\theta_2,\cdots, \theta_M)$ can beefficiently retrieved while the stored data is held secure against collusionamong up to $X$ colluding servers, the $m^{th}$ user's index is private againstcollusion among up to $T_m$ servers, and each user's index $\theta_m$ isprivate from all other users. The general scheme relies on a tensor-productbased extension of cross-subspace alignment and retrieves$1-(X+T_1+\cdots+T_M)/N$ bits of desired message per bit of download.

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., as- sumptions 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 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 (ρ -X-T)/N, where N is the total number of servers, and each message is replicated at leastρ 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/ν 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\in E between vertices u,v only if a subset of messages is replicated at both servers u and v.

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.

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.

The goal of coded distributed batch matrix multiplication  is to efficiently multiply  L instances of \lambda x \kappa matrices, A=(A_1, ..., A_L)$,  with L instances of \kappa x \mu matrices  B=(B_1,..., B_L), 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=(A_1B_1, A_2B_2, ..., A_LB_L).  Existing solutions either compute each $A_lB_l$ 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 download-constrained 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.

A parameter regime is identified where the simple scheme of treating interference as Gaussian noise (TIN), with power control and jamming, is optimal for the secure generalized degrees of freedom (GDoF) region of Gaussian broadcast networks under the robust assumption of finite-precision channel state information at the transmitter (CSIT). The network consists of one transmitter equipped with K antennas, and K single-antenna receivers. The results are generalized to groupcast (equivalently, compound broadcast) settings where each message is desired by a disjoint group of receivers. Noting that messages are independently encoded in the GDoF-optimal scheme, the result for the broadcast channel is extended to its counterpart Gaussian interference channel under finite precision CSIT. Evidently, both secrecy constraints and finite precision CSIT limit the benefits of more sophisticated schemes, leading to optimality of simpler schemes for larger parameter regimes. Aligned Image bounds are the key to the proof of optimality for these larger parameter regimes under finite precision CSIT.

$X$-secure and $T$-private information retrieval (XSTPIR) is a form ofprivate information retrieval where data security is guaranteed againstcollusion among up to $X$ servers and the user's privacy is guaranteed againstcollusion among up to $T$ servers. The capacity of XSTPIR is characterized forarbitrary number of servers $N$, and arbitrary security and privacy thresholds$X$ and $T$, in the limit as the number of messages $K\rightarrow\infty$.Capacity is also characterized for any number of messages if either $N=3,X=T=1$ or if $N\leq X+T$. Insights are drawn from these results, about aligningversus decoding noise, dependence of PIR rate on field size, and robustness tosymmetric security constraints. In particular, the idea of cross subspacealignment, i.e., introducing a subspace dependence between Reed-Solomon codeparameters, emerges as the optimal way to align undesired terms while keepingdesired terms resolvable.

$X$-secure and $T$-private information retrieval (XSTPIR) is a form ofprivate information retrieval where data security is guaranteed againstcollusion among up to $X$ servers and the user's privacy is guaranteed againstcollusion among up to $T$ servers. The capacity of XSTPIR is characterized forarbitrary number of servers $N$, and arbitrary security and privacy thresholds$X$ and $T$, in the limit as the number of messages $K\rightarrow\infty$.Capacity is also characterized for any number of messages if either $N=3,X=T=1$ or if $N\leq X+T$. Insights are drawn from these results, about aligningversus decoding noise, dependence of PIR rate on field size, and robustness tosymmetric security constraints. In particular, the idea of cross subspacealignment, i.e., introducing a subspace dependence between Reed-Solomon codeparameters, emerges as the optimal way to align undesired terms while keepingdesired terms resolvable.

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 \emph{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.

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 N1 and N2 antennas, 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 two-user computation broadcast problem is introduced as the setting where user 1 wants message W1 and has side information W0 1 , user 2 wants message W2 and has side information W0 2, and (W1;W0 1 ;W2;W0 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(W1jW0 1) + H(W2jW0 2) min I(W1;W2;W0 2jW0 1 ); I(W2;W1;W0 1jW0 2 ) . Furthermore, for the linear computation broadcast problem, where W1;W0 1;W2;W0 2 are comprised of arbitrary linear combinations of a basis set of independent symbols, the bound is shown to be tight.

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.

With the emergence of aligned images bounds, significant progress has been made in the understanding of robust fundamental limits of wireless networks through Generalized Degrees of Freedom (GDoF) characterizations 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 insights 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 over the simple scheme of power control and treating interference as Gaussian noise (TIN) for three  regimes of interest where the interference is weak. The question is intriguing because while in general transmitter cooperation can be quite powerful, finite precision CSIT and weak interference favor TIN.  The three regimes that we explore include a TIN regime previously identified by Geng et al. where TIN was  shown to be GDoF optimal for the $K$ user interference channel, a CTIN regime previously identified by Yi and Caire where the GDoF region achievable by TIN turns out to be convex without the need for time-sharing, and an SLS regime previously identified by Davoodi and Jafar where a simple layered superposition (SLS) scheme is shown to be optimal in the $K$ user MISO BC, although only for $K\leq 3$. It remains an intriguing possibility that TIN may not be far from optimal in the CTIN regime, and that SLS schemes may be close to optimal even for larger networks in the SLS regime, but the curse of dimensionality is one of the obstacles that stands in the way of such generalizations. 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 $\Theta(1)$, i.e., it is bounded above by a constant regardless of the number of users $K$. In fact, the gain is at most a factor of $2$ in the CTIN regime, which automatically implies that TIN is GDoF optimal within a factor of $2$ in the CTIN regime. In the TIN regime, the extremal GDoF gain of transmitter cooperation over TIN is shown to be exactly $50\%$, regardless of the number of users $K$, provided $K>1$. However, in the SLS regime, the extremal GDoF gain of transmitter cooperation  over TIN is $\Theta(\log_2(K))$, i.e., it scales logarithmically with the number of users. Remarkably, an SLS scheme suffices to demonstrate this extremal GDoF gain. Last but not the least, as a byproduct of our analysis we  prove a useful cyclic decomposition property of the sum GDoF achievable by TIN in the SLS regime.

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.

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.

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 PIR$_{\max}$, 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 PIR$_{\max}$ schemes is $(K-1)\log N$. The results also generalize to a variation of the PIR problem, known as Repudiative Information Retrieval (RIR).

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.

We show that to characterize the capacity of storage overhead constrained private information retrieval (PIR) with only 2 messages, and 2 databases, non-Shannon information inequalities are necessary. As a by-product of this result, we construct the smallest instance, to our knowledge, of a network coding capacity problem that requires non-Shannon inequalities.

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.

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

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

We study the 3 user multiple input single output (MISO) broadcast channel (BC) with 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 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 αij representing the channel strength parameter for the link from the jth antenna of the transmitter to the ith receiver, we prove that SLS is GDoF optimal without the need for time-sharing if max(αji,αij) ≤ αii and αki + αij ≤ αii + αkj for all i,j,k ∈ [3]. The GDoF region under this condition is a convex polyhedron.

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.

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 in 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+ cdots +1/N^K-1-1. In this paper, for arbitrary K and N , we explore the minimum download cost DL across 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=LC. 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 in (L'C), (L/C-1, (L'/C) -2, where L'= L M' M, i.e., the optimal download cost is characterized to within two symbols.

In order to gain new insights into multiple-input-multiple-output (MIMO) interference networks, the optimality ofσk=1 K Mk/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 k th transmitter and receiver are equipped with Mk antennas 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 k th user pair has Mk antennas. 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.

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. The bounds are useful instruments to obtain GDoF characterizations for wireless interference networks, especially with multiple antenna nodes, subject to arbitrary channel strength and channel uncertainty levels.

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, and zero otherwise.

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.

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.

This paper identifies the CEO characteristics that have an impact on the performance of family businesses listed in the Euronext in the post-COVID 19 period. CEO characteristics are evaluated on two dimensions, i.e., personal characteristics and corporate governance mechanisms. A sample of 137 firm-year observations from Portugal, Luxembourg, the Netherlands, Ireland, France, and Belgium was chosen. CEO attributes of age, gender, education, and family membership were combined with corporate governance mechanisms of ownership concentration, CEO duality, CEO directorships, and CEO tenure, to predict return on assets and return on equity, using OLS regression. GMM estimation and Two-Stage Least Squares were employed to establish the robustness of the results. Among CEO personal characteristics, CEO family membership has a positive impact on return on assets, and a positive impact on return on equity. Among corporate governance mechanisms, CEO duality had a negative impact on return on assets, and a negative impact on return on equity. CEO ownership, and CEO tenure had a positive impact on return on assets, and a positive impact on return on equity. This paper's value lies in its evaluation of the under-researched area of family businesses of Euronext-listed firms. It can be used by family businesses in the region, for the selection and training of CEOs to fulfill the goal of achieving superior financial performance. [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.

The 2 user MIMO interference channel with arbitrary antenna configurations is studied under arbitrary levels of partial CSIT for each of the channels, to find the degrees of freedom (DoF) achievable by User 2 while User 1 achieves his full interference-free DoF. The goal is to gain new insights due to the inclusion of MIMO (multiple antennas at both transmitters and receivers) into the signal space partitioning schemes associated with partial CSIT. An interesting idea that emerges from this study is 'elevated multiplexing' where the signals are split into streams and transmitted from separate antennas at elevated power levels, which allows these signals to be jointly decoded at one receiver which has fewer spatial dimensions with lower interference floors, while another receiver is simultaneously able to separately decode these signals with a higher interference floor but across a greater number of spatial dimensions. Through elevated multiplexing we find that there is a DoF benefit from increasing the number of antennas at a transmitter even if that transmitter already has more antennas than its desired receiver and has no CSIT.

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.

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 βij parameters, 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.

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.

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.

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.