Skip to main content
eScholarship
Open Access Publications from the University of California

Recent Work

This is the website for papers published by the Center for Pervasive Communications and Computing at the University of California, Irvine.

Cover page of GDoF of Interference Channel with Limited Cooperation under Finite Precision CSIT

GDoF of Interference Channel with Limited Cooperation under Finite Precision CSIT

(2019)

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.

Cover page of Towards an Extremal Network Theory – Robust GDoF Gain of Transmitter Cooperation over TIN

Towards an Extremal Network Theory – Robust GDoF Gain of Transmitter Cooperation over TIN

(2019)

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.

Cover page of On the Capacity of Locally Decodable Codes

On the Capacity of Locally Decodable Codes

(2018)

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

Cover page of On the Necessity of Non-Shannon Information Inequalities for Storage Overhead Constrained PIR and Network Coding

On the Necessity of Non-Shannon Information Inequalities for Storage Overhead Constrained PIR and Network Coding

(2018)

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.

Cover page of Optimality of Simple Layered Superposition Coding in the 3 User MISO BC with Finite Precision CSIT

Optimality of Simple Layered Superposition Coding in the 3 User MISO BC with Finite Precision CSIT

(2018)

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.

Cover page of Interference Mitigation Using Asynchronous Transmission and Sampling Diversity

Interference Mitigation Using Asynchronous Transmission and Sampling Diversity

(2016)

In this paper, we show that by investigating inherent time delays between different users in a multiuser scenario, we are able to cancel interference more efficiently. Time asynchrony provides another tool to cancel interference which results in preserving other resources like frequency, time and code. Therefore, we can save the invaluable resource of frequency band and also increase spectral efficiency. A sampling method is presented which results in independent noise samples and obviates the need for the complex process of noise whitening. By taking advantage of this sampling method and its unique structure, we implement maximum-likelihood sequence detection which outperforms synchronous maximum-likelihood detection. We also present successive interference cancellation with hard decision passing which gives rise to a novel forward-backward belief propagation method. Next, the performance of zero forcing detection is analyzed. Simulation results are also presented to verify our analysis.

Cover page of Transmitter Cooperation under Finite Precision CSIT: A GDoF Perspective

Transmitter Cooperation under Finite Precision CSIT: A GDoF Perspective

(2016)

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

Cover page of Degrees of Freedom of Rank-Deficient MIMO Interference Networks

Degrees of Freedom of Rank-Deficient MIMO Interference Networks

(2015)

We characterize the degrees of freedom (DoF) of MIMO interference networks with rank-

deficient channel matrices. For the 2-user rank deficient MIMO interference channel, we prove

the optimality of previously known achievable DoF in the symmetric case and generalize the re-

sult to fully asymmetric settings. For the K-user rank deficient interference channel, we improve

the previously known achievable DoF and provide a tight outer bound to establish optimality

in symmetric settings. In particular, we show that for the K-user rank deficient interference

channel, when all nodes have M antennas, all direct channels have rank D0, all cross chan-

nels are of rank D, and the channels are otherwise generic, the optimal DoF value per user is

min(D0, M −min(M,(K−1)D)). For 2-user and 3-user rank deficient channels, achievable schemes2

are for both constant and time-varying channels, while for K-user rank deficient channels, we present schemes for time-varying channels and note that the insights would act as stepping stones for constant channels. Notably for interference channels, the rank-deficiency of direct channels does not help and the rank-deficiency of cross-channels does not hurt. The main technical challenge is to account for the spatial dependencies introduced by rank deficiencies in the interference alignment schemes that typically rely on the independence of channel coefficients.