Center for Pervasive Communications and Computing

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.