Cooperative Data Exchange and Private Information Retrieval

Coding techniques have been well studied and used for improving communication quality by combating noise and mitigating interference. Recently, it has been shown that the same coding techniques can also be exploited to further improve communication performance and provide specific communication features even when the communication channel is ideal. In this thesis, we study two problems where coding techniques are used for improving communications in distributed systems and protecting the privacy of the client from untrusted servers, respectively.\

The first part of this thesis studies the cooperative data exchange problem for fully connected networks. While many previous studies have shown that the problem can be solved by algorithms based on submodular function minimization, we tackle this problem via a concept we refer to as "conditioning basis", which is closely linked to linear coding schemes with particular additional properties. We show that such special linear coding schemes are optimal for the cooperative data exchange problem. Hence, by searching the existence of such a conditioning basis and special linear coding schemes, we can solve this problem with lower complexity. We propose a deterministic algorithm for this problem and briefly show how to construct the optimal linear coding schemes starting from a Vandermonde matrix. Moreover, we show that our new method can be used to solve two generalized problems, which are cooperative data exchange with weighted cost and successive local omniscience problems.\

The second part of this thesis investigates the problem of private information retrieval with side information. Specifically, three different extensions are studied: multi-message, multi-server, and multi-user, respectively. For each problem, we provide a proof of the converse for the download rate as well as propose efficient approaches to construct optimal coding schemes. For multi-message and multi-server cases, we give closed-form expressions for the download rates and introduce two useful tools, {\it conditioning answer string} and {\it virtual private information}, to analyze the problem. For multi-user cases, we show that the optimal download rate can be obtained by solving an optimization problem over all partitions of the total number of messages and propose a novel algorithm based on dynamic programming to solve the optimization problem.\