## Type of Work

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

## Peer Review

Peer-reviewed only (9)

## Supplemental Material

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

## Publication Year

## Campus

UC Berkeley (0) UC Davis (0) UC Irvine (31) 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 (23)

## Journal

## Discipline

Engineering (23)

## Reuse License

BY-NC-ND - Attribution; NonCommercial use; No derivatives (6) BY - Attribution required (2) BY-NC-SA - Attribution; NonCommercial use; Derivatives use same license (1)

## Scholarly Works (31 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.

We consider a two-tier cellular system where there is a macrocell base station equipped with multiple antennas transmitting to multiple microcells, each equipped with a microcell base station (relay) equipped with one antenna. Each microcell has one user. We explore the degrees of freedom (DoF) of several conﬁgurations of this network with the assumption that no channel state information (CSI) of the users is available at the macrocell base station and different assumptions on the CSI between other transmitter-receiver pairs. With very limited CSI and the relays, the achievable DoF can be greatly increased compared to the case when there is no relays.

Treating interference as noise (TIN) when it is sufficiently weak is one of the key principles of interference management for wireless networks. This dissertation revisits the optimality of TIN from an information theoretic perspective. It is shown that for K-user Gaussian interference channels, TIN achieves all points in the capacity region to within a constant gap, if for each user, the desired signal strength is no weaker than the sum of the strengths of the strongest interference caused by the user and the strongest interference suffered by the user (with all signal strengths measured in dB scale). We also extend the optimality of TIN to more general settings, including interference networks with general message sets, compound networks and MIMO interference channels, and characterize the secure capacity region within a constant gap for the identified TIN-optimal interference channels with secrecy constraints. Moreover, combining TIN with interference avoidance, we formulate a joint signal space and signal level optimization problem and propose a baseline decomposition approach.

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.