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

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

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.

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

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

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

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