We propose a new capacity-achieving code for the private information retrieval (PIR) problem, and show that it has the minimum message size (being one less than the number of servers) and the minimum upload cost (being roughly linear in the number of messages) among a general class of capacityachieving codes, and in particular, among all capacity-achieving linear codes. Different from existing code constructions, the proposed code is asymmetric, and this asymmetry appears to be the key factor leading to the optimal message size and the optimal upload cost. The converse results on the message size and the upload cost are obtained by an analysis of the information theoretic proof of the PIR capacity, from which a set of critical properties of any capacity-achieving code in the code class of interest is extracted. The symmetry structure of the PIR problem is then analyzed, which allows us to construct symmetric codes from asymmetric ones, yielding a meaningful bridge between the proposed code and existing ones in the literature.

Most of our lives are conducted in the cyberspace. The human notion of privacy translates into a cyber notion of privacy on many functions that take place in the cyberspace. This article focuses on three such functions: how to privately retrieve information from cyberspace (privacy in information retrieval), how to privately leverage large-scale distributed/parallel processing (privacy in distributed computing), and how to learn/train machine learning models from private data spread across multiple users (privacy in distributed (federated) learning). The article motivates each privacy setting, describes the problem formulation, summarizes breakthrough results in the history of each problem, and gives recent results and discusses some of the major ideas that emerged in each field. In addition, the cross-cutting techniques and interconnections between the three topics are discussed along with a set of open problems and challenges.

We propose a generic transformation that can convert any nonbinary (n = k + r, k) maximum distance separable (MDS) code into another (n, k) MDS code over the same field such that 1) some arbitrarily chosen r nodes have the optimal repair bandwidth and the optimal rebuilding access, 2) for the remaining k nodes, the normalized repair bandwidth and the normalized rebuilding access (over the file size) are preserved, 3) the sub-packetization level is increased only by a factor of r. Two immediate applications of this generic transformation are then presented. The first application is that we can transform any nonbinary MDS code with the optimal repair bandwidth or the optimal rebuilding access for the systematic nodes only, into a new MDS code which possesses the corresponding repair optimality for all nodes. The second application is that by applying the transformation multiple times, any nonbinary (n, k) scalar MDS code can be converted into an (n, k) MDS code with the optimal repair bandwidth and the optimal rebuilding access for all nodes, or only a subset of nodes, whose sub-packetization level is also optimal.

We illustrate how computer-aided methods can be used to investigate the fundamental limits of the caching systems, which are significantly different from the conventional analytical approach usually seen in the information theory literature. The linear programming (LP) outer bound of the entropy space serves as the starting point of this approach; however, our effort goes significantly beyond using it to prove information inequalities. We first identify and formalize the symmetry structure in the problem, which enables us to show the existence of optimal symmetric solutions. A symmetry-reduced linear program is then used to identify the boundary of the memory-transmission-rate tradeoff for several small cases, for which we obtain a set of tight outer bounds. General hypotheses on the optimal tradeoff region are formed from these computed data, which are then analytically proven. This leads to a complete characterization of the optimal tradeoff for systems with only two users, and certain partial characterization for systems with only two files. Next, we show that by carefully analyzing the joint entropy structure of the outer bounds for certain cases, a novel code construction can be reverse-engineered, which eventually leads to a general class of codes. Finally, we show that outer bounds can be computed through strategically relaxing the LP in different ways, which can be used to explore the problem computationally. This allows us firstly to deduce generic characteristic of the converse proof, and secondly to compute outer bounds for larger problem cases, despite the seemingly impossible computation scale.

We propose a new coded caching scheme where linear combinations of the file segments are cached at the users, for the cases where the number of files is no greater than the number of users. When a user requests a certain file in the delivery phase, the other file segments in the cached linear combinations can be viewed as interference. The proposed scheme combines rank-metric codes and maximum distance-separable codes to facilitate the decoding and elimination of the interference and also to simultaneously deliver useful contents to the intended users. The performance of the proposed scheme can be explicitly evaluated, and we show that it can achieve improvement over known memory-rate tradeoff achievable results in the literature in some regime; for certain special cases, the new memory-rate tradeoff points can be shown to be optimal.

We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from N non-colluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from accessing the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization factor) is significantly, in fact exponentially, lower than previously believed. More precisely, when K > T/1(N,T) where K is the total number of messages in the system and 1(∙,∙) means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as (N-T,T), where (∙,∙) means the least common multiple. On the other hand, when K is small, we show that it is in fact possible to design codes with a message size even smaller than (N-T,T).