Cross Subspace Alignment and Its Applications to Private Information Retrieval and Coded Distributed Computation

Originating from the construction of the asymptotic-capacity achieving scheme for X-secure T-private information retrieval (XSTPIR), the technique of cross-subspace alignment (CSA) emerges as the natural solution to secure and private information retrieval, secure distributed matrix multiplication, and coded distributed batch computation. Characterized by a Cauchy-Vandermonde structure that facilitates interference alignment along Vandermonde terms, while the desired signals remain resolvable along the Cauchy terms, the idea of CSA is shown to be the essential ingredient in the optimal/asymptotically optimal/state-of-art approaches that minimize the download and/or communication cost of these independently introduced but closely related problems.In this dissertation we will first introduce the idea of CSA to the applications of XSTPIR, XSTPIR with graph-based replicated storage (GXSTPIR) and XSTPIR with MDS coded storage (MDS-XSTPIR). The CSA solution to XSTPIR exploits the Cauchy-Vandermonde structured answer strings that align interference symbols guaranteeing T-privacy and X-security to achieve the asymptotic capacity. The achievability scheme for GXSTPIR reveals a non-trivial generalization of CSA that takes the advantage of a special structure inspired by dual Generalized Reed Solomon (GRS) codes to allow interference alignment for arbitrary storage patterns. For MDS-XSTPIR, we propose a novel scheme based on confluent Cauchy-Vandermonde storage structure and a strategy of successive decoding with interference cancellation. Next, by characterizing a connection between a form of XSTPIR problem known as multi-message XSTPIR and the problem of secure distributed matrix multiplication (SDMM), we characterize a series of capacity regions of SDMM, as well as several of its variants. The idea of CSA serves as an essential component of the construction of several achievability schemes. Given the insights from all these results, next, we construct CSA/GCSA codes based on (confluent) Cauchy-Vandermonde structures for coded distributed batch computation (CDBC) that unify, generalize and improve upon the state-of-art codes for distributed computing such as LCC codes for multivariate polynomial evaluations and EP codes for matrix multiplication. Finally, we study the problem of X-secure T-private federated submodel learning (XSTPFSL), which is a non-trivial generalization of the XSTPIR problem where private writes are needed. The proposed ACSA-RW scheme achieves the desired private read and write functionality with elastic dropout resilience, takes the advantage of the synergistic gain from the joint design of private read and write for low communication costs, and sheds light on a striking symmetry between upload and download costs. Intuitively, private read and write functionalities, as well as their synergistic gain, rely on secure distributed matrix multiplication so that the idea of CSA emerges as the core of the solution