## Type of Work

Article (19) Book (0) Theses (6) Multimedia (0)

## Peer Review

Peer-reviewed only (7)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (0) UC Davis (0) UC Irvine (25) UCLA (0) UC Merced (0) UC Riverside (0) UC San Diego (0) UCSF (0) UC Santa Barbara (0) UC Santa Cruz (0) UC Office of the President (0) Lawrence Berkeley National Laboratory (0) UC Agriculture & Natural Resources (0)

## Department

Center for Pervasive Communications and Computing (19)

## Journal

## Discipline

Engineering (19)

## Reuse License

BY-NC-ND - Attribution; NonCommercial use; No derivatives (5)

## Scholarly Works (25 results)

We identify the role of equal strength interference links as bottlenecks on the ergodic sum capacity of a K user interference network with the fading process restricted primarily to inde- pendent and uniform phase variations while the channel magnitudes are held ﬁxed 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 suﬃce 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 high- lighted for channels where both the phase and the magnitudes are allowed to vary with time. It is shown through an example that for these channels, joint coding across diﬀerent bottleneck states makes it possible to circumvent the capacity bottlenecks.

The modern information age is heralded by exciting paradigms ranging from big data, cloud computing to internet of things. As information becomes increasingly available, privacy concerns are starting to take center-stage, especially in the communication networks that are used for information storage, repair, retrieval or transfer. The focus of this dissertation is on the private information retrieval (PIR) problem. PIR originated in theoretical computer science and cryptography, and has only recently started receiving attention in information and coding theory. PIR seeks the most efficient way for a user to retrieve a desired message from a set of N distributed servers, each of which stores all K messages, without revealing any information about which message is being retrieved to any individual server. It is a canonical problem with deep connections to a number of other prominent problems such as oblivious transfer, multiparty computation, locally decodable codes, batch codes and blind interference alignment.

We will first identify the capacity of PIR, i.e., the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. This result is inspired by the discovery of an intriguing connection between PIR and blind interference alignment in wireless networks. Then we will discuss four extensions of PIR. The first extension is the TPIR problem, where we increase the privacy level, i.e., instead of requiring privacy to each individual server, we require privacy to any colluding set of up to T servers. We will characterize the capacity of TPIR and generalize the result to include robustness constraints, where we have M databases, out of which any M − N may fail to respond. The second extension is the MDS-TPIR problem, where we further generalize the storage constraint, i.e., instead of data replication, an MDS storage code is used to store the messages. In particular, we will disprove a recent conjecture on the capacity of MDS-TPIR. The third extension is the SPIR problem, a form of oblivious transfer where the privacy constraint is extended symmetrically to protect both the user and the servers. We will identify the capacity of SPIR. The final extension is MPIR, where the user and the servers communicate in multiple rounds. We will show that multiple rounds do not increase the capacity of PIR, but reduce the storage overhead. The results will shed light into the necessity for non-linear schemes and non-Shannon information inequalities.

### Optimal Use of Multiple Antennas in Interference Networks -- MIMO, Interference Alignment and Beyond

Degrees of freedom (DoF) studies of wireless networks have contributed many fundamental insights into their capacity limits. One of the most critical determinants of these capacity limits is the amount of channel state information at the transmitters (CSIT). In this dissertation, we consider the MIMO interference networks with both perfect CSIT and CSIT uncertainty. In particular, a novel class of replication-based outer bounds will first be presented for arbitrary rank-constrained MIMO interference networks with perfect CSIT. It creates a new perspective of the capacity 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. Then, we prove that when CSIT is not perfect, signal space partitioning schemes can be DoF optimal. 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. Finally, we explore the compatibility of various approaches under CSIT uncertainty which only been studied in isolation before, such as Blind Interference Alignment (BIA) and partial zero-forcing. Coding schemes are proposed that jointly exploit partial channel knowledge and reconfigurable antennas, demonstrating synergistic DoF gains over what is achievable with either BIA or beamforming by itself.

As the first steps in the path towards progressively refined capacity approximations, degrees of freedom (DoF) and generalized degrees of freedom (GDoF) studies of wireless networks have turned out to be surprisingly useful. By exposing large gaps where they exist in our understanding of the capacity limits, these studies have been the catalysts for numerous discoveries over the past decade \cite{Jafar_FnT}. Some of the most interesting unresolved questions brought to light by recent DoF and GDoF studies have to do with channel uncertainty and the diversity of channel strengths. Consider the wireless network with $K$ transmitters and $K$ receivers, which could represent the $K$ user interference channel, the $K\times K$ $X$ channel, or the $K$ user MISO BC, i.e., the broadcast channel formed by allowing full cooperation among the transmitters in a $K$ user interference channel. Consider, first the issue of channel uncertainty. If the channel state information at the transmitter(s) (CSIT) is perfect then the $K$ user interference channel has $K/2$ DoF, the $K\times K$ $X$ channel has $K^2/(2K-1)$ DoF, and the MISO BC has $K$ DoF almost surely.\footnote{Channel state information at the receivers (CSIR) is assumed perfect throughout this work.} The optimal DoF are achieved by interference alignment for the interference and $X$ channel settings, and by transmit zero-forcing in the MISO BC. However, what happens if the CSIT is available only to finite precision?

Lapidoth et al. nearly a decade ago conjectured that the MISO BC has only $1$ DoF, i.e., the DoF collapse.

Since the MISO BC contains within it the $K$ user interference and $X$ channels, the collapse of DoF under finite precision CSIT implies that neither zero-forcing nor interference alignment is robust enough to provide a DoF advantage under finite precision CSIT, i.e., the DoF collapse for the interference and $X$ channels as well. Now consider the diversity of channel strengths which is explored through the studies of generalized degrees of freedom (GDoF). If all cross channels are much weaker relative to the direct channels then the DoF do not collapse even with finite precision CSIT. The collapse of DoF is avoided in the interference channel, simply by treating the weak interference as noise. Since the $X$ and BC settings include the interference channel, the collapse of DoF is avoided there as well. If some cross-channels are strong while others are so weak that they can be ignored entirely, as in the topological interference management problem, then even under finite precision CSIT, interference alignment plays a key role, albeit in a more robust form that does not depend on actual channel realizations.

In this thesis, we first prove the conjecture of Lapidoth, Shamai and Wigger as well as the ”PN” conjecture of Tandon et al., for all non-degenerate forms of finite precision CSIT. In the next step, we derive the GDoF of two user MISO BC problem, the sum GDoF of the K user symmetric MISO BC and the symmetric GDoF region of the K-user interference channel under finite precision CSIT. In the symmetric setting, we allow each cross channel to carry α DoF while each direct channel is capable of carrying 1 DoF. Finally, we derive sum-set inequalities specialized to the GDoF framework and derive DoF of MIMO BC under partial CSIT aiding from sum-set inequalities.

In this paper we investigate the sum degrees of freedom (DoF) of multiple unicasts in a wireless network. With 2 source nodes, 2 destination nodes, there are a total of 4 independent unicast sessions (messages), one from each source to each sink node (this setting is also known as an X network), and also there is a delay-free relay working in full-duplex mode helping the transmissions from the source to destination nodes. For such a channel setting, we prove that 5/3 DoF is achievable almost surely for time-varying/frequency-selective channels, based on the ideas of aligned interference neutralization, linear forwarding and interference alignment. Also, the achievable scheme can be easily translated to the rational alignment scheme for the network with constant-values channel coefficients. In addition, we provide an intuition for the 5/3 DoF result from the perspective of counting the number of linear equations and variables.