In latent-variable private information retrieval (LV-PIR), a user wishes to retrieve one out of$K$messages (indexed by θ) without revealing any information about a sensitive latent attribute (modeled by a latent variable$S$correlated with θ). While conventional PIR protocols, which keep θ2private, also suffice for hiding S, they can be too costly in terms of the download overhead. In this paper, we characterize the capacity (equivalently, the optimal download cost) of LV-PIR as a function of the distribution PS|θ. We present a converse proof that yields a lower bound on the optimal download cost, and a matching achievable scheme. The optimal scheme, however, involves an exhaustive search over subset queries and over all messages, which can be computationally prohibitive. We further present two low-complexity, albeit sub-optimal, schemes that also outperform the conventional PIR solution.

Information-theoretic formulations of the private information retrieval (PIR) problem have been investigated under a variety of scenarios. Symmetric private information retrieval (SPIR) is a variant where a user is able to privately retrieve one out of K messages from N non-colluding replicated databases without learning anything about the remaining K-1 messages. However, the goal of perfect privacy can be too taxing for certain applications. In this paper, we investigate if the information-theoretic capacity of SPIR (equivalently, the inverse of the minimum download cost) can be increased by relaxing both user and DB privacy definitions. Such relaxation is relevant in applications where privacy can be traded for communication efficiency. We introduce and investigate the Asymmetric Leaky PIR (AL-PIR) model with different privacy leakage budgets in each direction. For user privacy leakage, we bound the probability ratios between all possible realizations of DB queries by a function of a non-negative constant ϵ. For DB privacy, we bound the mutual information between the undesired messages, the queries, and the answers, by a function of a non-negative constant δ. We propose a general AL-PIR scheme that achieves an upper bound on the optimal download cost for arbitrary ϵ and δ. We show that the optimal download cost of AL-PIR is upper-bounded as D*(ϵ,δ) ≤ 1+\frac 1N-1-\frac δeϵNK-1-1. Second, we obtain an information-theoretic lower bound on the download cost as D*(ϵ,δ) ≥ 1+\frac 1Neϵ-1-\frac δ(Neϵ)K-1-1. The gap analysis between the two bounds shows that our AL-PIR scheme is optimal when ϵ = 0, i.e., under perfect user privacy and it is optimal within a maximum multiplicative gap of \frac N-e-ϵN-1 for any ϵ > 0 and δ > 0.

In many applications, content accessed by users (movies, videos, news articles, etc.) can leak sensitive latent attributes, such as religious and political views, sexual orientation, ethnicity, gender, and others. To prevent such information leakage, the goal of classical PIR is to hide the identity of the content/message being accessed, which subsequently also hides the latent attributes. This solution, while private, can be too costly, particularly, when perfect (information-theoretic) privacy constraints are imposed. For instance, for a single database holding K messages, privately retrieving one message is possible if and only if the user downloads the entire database of K messages. Retrieving content privately, however, may not be necessary to perfectly hide the latent attributes.Motivated by the above, we formulate and study the problem of latent-variable private information retrieval (LV-PIR), which aims at allowing the user efficiently retrieve one out of K messages (indexed by θ) without revealing any information about the latent variable (modeled by S). We focus on the practically relevant setting of a single database and show that one can significantly reduce the download cost of LV-PIR (compared to the classical PIR) based on the correlation between θ and S. We present a general scheme for LV-PIR as a function of the statistical relationship between θ and S, and also provide new results on the capacity/download cost of LV-PIR. Several open problems and new directions are also discussed.

Private information retrieval (PIR) allows a user to retrieve a desired message from a set of databases without revealing the identity of the desired message. The replicated database scenario, where N databases store each of the K messages was considered by Sun and Jafar, and the optimal download cost was characterized as (1+ 1/N+1/N2+ ⋯ + 1/NK-1). In this work, we consider the problem of PIR from uncoded storage constrained databases. Each database has a storage capacity of μKL bits, where L is the size of each message in bits, and μ ∈ [1/N, 1] is the normalized storage. The novel aspect of this work is to characterize the optimum download cost of PIR from uncoded storage constrained databases for any “normalized storage” value in the range μ ∈ [1/N, 1]. In particular, for any (N, K), we show that the optimal trade-off between normalized storage, μ, and the download cost, D(μ), is a piece-wise linear function given by the lower convex hull of the N pairs (t/N,(1 + 1/t + 1/t2+ ⋯ + 1/tK-1))for t=1,2,...,N. To prove this result, we first present a storage constrained PIR scheme for any (N, K). Next, we obtain a general lower bound on the download cost for PIR, which is valid for any arbitrary storage architecture. The uncoded storage assumption is then applied which allows us to express the lower bound as a linear program (LP). Finally, we solve the LP to obtain tight lower bounds on the download cost for different regimes of storage, which match the proposed storage constrained PIR scheme.

Data shuffling between distributed cluster of nodes is one of the critical steps in implementing large-scale learning algorithms. Randomly shuffling the data-set among a cluster of workers allows different nodes to obtain fresh data assignments at each learning epoch. This process has been shown to provide improvements in the learning process (via testing and training error). However, the statistical benefits of distributed data shuffling come at the cost of extra communication overhead from the master node to worker nodes, and can act as one of the major bottlenecks in the overall time for computation. There has been significant recent interest in devising approaches to minimize this communication overhead. One approach is to provision for extra storage at the computing nodes. The other emerging approach is to leverage coded communication to minimize the overall communication overhead. The focus of this work is to understand the fundamental tradeoff between the amount of storage and the communication overhead for distributed data shuffling. In this paper, we first present an information theoretic formulation for the data shuffling problem, accounting for the underlying problem parameters (number of workers, K, number of data points, N, and available storage, and S per node). We then present an information theoretic lower bound on the communication overhead for data shuffling as a function of these parameters. We next present a novel coded communication scheme and show that the resulting communication overhead of the proposed scheme is within a multiplicative factor of at most K-1 from the lower bound (which is upper bounded by 2 for K/K ≥ 2). Furthermore, we present new results towards closing this gap through a novel coded communication scheme, which we call the aligned coded shuffling. This scheme is inspired by the ideas of coded shuffling and interference alignment. In particular, we show that the aligned scheme achieves the optimal storage vs communication trade-off for K <; 5, and further reduces the K-1 maximum multiplicative gap down to K-1/3/k-1, for K ≥ 5.

Private information retrieval (PIR) allows a user to retrieve a desired message out of$K$possible messages from$N$databases (DBs) without revealing the identity of the desired message. In this work, we consider the problem of PIR from uncoded storage constrained DBs. Each DB has a storage capacity of$\mu KL$bits, where$L$is the size of each message in bits, and$\mu\in[1/N,\ 1]$is the normalized storage. In the storage constrained PIR problem, there are two key challenges: a) construction of communication efficient schemes through storage content design at each DB that allow download efficient PIR; and b characterizing the optimal download cost via information-theoretic lower bounds. The novel aspect of this work is to characterize the optimum download cost of PIR with storage constrained DBs for any value of storage. In particular, for any$(N,\ K)$, we show that the optimal tradeoff between storage$(\mu)$and the download cost$(D(\mu))$is given by the lower convex hull of the pairs$(\frac{t}{N}(1+\frac{1}{t}+\frac{1}{t^{2}}+\cdots+\frac{1}{t^{K-1}}))$for$t$= 1,2, …, N. The main contribution of this paper is the converse proof, i.e., obtaining lower bounds on the download cost for PIR as a function of the available storage.

Data shuffling between distributed workers is one of the critical steps in implementing large-scale learning algorithms. The focus of this work is to understand the fundamental trade-off between the amount of storage and the communication overhead for distributed data shuffling. We first present an information theoretic formulation for the data shuffling problem, accounting for the underlying problem parameters (i.e., number of workers, K, number of data points, N, and the available storage, S per node). Then, we derive an information theoretic lower bound on the communication overhead for data shuffling as a function of these parameters. Next, we present a novel coded communication scheme and show that the resulting communication overhead of the proposed scheme is within a multiplicative factor of at most 2 from the lower bound. Furthermore, we introduce an improved aligned coded shuffling scheme, which achieves the optimal storage vs communication trade-off for K <; 5, and further reduces the maximum multiplicative gap down to 7/6, for K ≥ 5.

In this work, we focus on the partially connected interference network with confidential messages, and study the secure degrees of freedom with no channel state information at the transmitters (CSIT). Prior works on fully connected interference networks with full CSIT have shown that the secure degrees of freedom scales linearly with the number of users. With no CSIT, however, the secure degrees of freedom of fully connected networks collapses to zero. In this work, we show that partial connectivity, a widely prevalent property of wireless networks, can be leveraged to provide secrecy even with no CSIT. We present a systematic approach to first understand the feasibility of secure communication in a partially connected network and develop achievable schemes for a class of regular partially connected networks. Finally, we also provide novel information theoretic outer bounds on the secure degrees of freedom for this class of regular partially connected networks, and approximately characterize the secure degrees of freedom.

Data shuffling is one of the fundamental building blocks for distributed learning algorithms, that increases the statistical gain for each step of the learning process. In each iteration, different shuffled data points are assigned by a central node to a distributed set of workers to perform local computation, which leads to communication bottlenecks. The focus of this paper is on formalizing and understanding the fundamental information-theoretic tradeoff between storage (per worker) and the worst-case communication overhead for the data shuffling problem. We completely characterize the information theoretic tradeoff for K = 2, and K = 3 workers, for any value of storage capacity, and show that increasing the storage across workers can reduce the communication overhead by leveraging coding. We propose a novel and systematic data delivery and storage update strategy for each data shuffle iteration, which preserves the structural properties of the storage across the workers, and aids in minimizing the communication overhead in subsequent data shuffling iterations.

In this paper, we consider a fading relay channel where the source uses two layers source coding with successive refinement. The two source layers are transmitted using superposition coding at the source and relay with optimal power allocation, and successive interference cancellation at the receivers (i.e. relay and destination). The power allocation for the two layers at the source and relay is subject to optimization in order to maximize the expected user satisfaction that is defined by a utility function of the total decoded rates at the destination. We assume that only the channel statistics are known. The relay is half-duplex and applies decode and forward. We characterize the expected utility function in terms of the channel statistics of the fading channels, and we solve the optimization problem using the numerical random search method. We provide many numerical examples to show the prospected gains of using the relay on the expected utility for different channel conditions. Furthermore, we obtain that for some conditions, it is optimal to send only one layer.