Large-scale decentralized learning frameworks such as federated learning (FL), require both communication efficiency and strong data security, motivating the study of secure aggregation (SA). While information-theoretic SA is well understood in centralized and fully connected networks, its extension to decentralized networks with limited local connectivity remains largely unexplored. This paper introduces \emph{topological secure aggregation} (TSA), which studies one-shot, information-theoretically secure aggregation of neighboring users' inputs over arbitrary network topologies. We develop a unified linear design framework that characterizes TSA achievability through the spectral properties of the communication graph, specifically the kernel of a diagonally modulated adjacency matrix. For several representative classes of $d$-regular graphs including ring, prism and complete topologies, we establish the optimal communication and secret key rate region. In particular, to securely compute one symbol of the neighborhood sum, each user must (i) store at least one key symbol, (ii) broadcast at least one message symbol, and (iii) collectively, all users must hold at least $d$ i.i.d. key symbols. Notably, this total key requirement depends only on the \emph{neighborhood size} $d$, independent of the network size, revealing a fundamental limit of SA in decentralized networks with limited local connectivity.

This paper studies the master-worker distributed linearly separable computation problem, where the considered computation task, referred to as linearly separable function, is a generic linear map. This model includes cooperative distributed gradient coding, real-time rendering, linear transforms, etc. as special cases. The computation task on K datasets can be expressed as Kclinear combinations of K messages, where each message is the output of an individual function on one dataset. In this distributed computing model, the K datasets are assigned to N workers for computation. Due to the possible presence of stragglers, it is required that the master can obtain the desired computation task from the answers of any Nrout of N workers. The computation cost is defined as the number of datasets assigned to each worker, while the communication cost is defined as the number of codewords that should be received. The objective is to characterize the optimal tradeoff between the computation and communication costs. A common way to assign the datasets to the workers is “cyclic assignment”. This has been considered in several theoretical works, as well as gradient coding, etc. Motivated by its theoretical and practical relevance, in this paper we focus on the cyclic assignment and solve the problem by determining the optimal computation/communication cost tradeoff when N = K and order optimal within a factor of 2 otherwise. In particular, this paper proposes a new computing scheme with the cyclic assignment based on the concept of interference alignment, by treating each message which cannot be computed by a worker as an interference from this worker. The decodability of our scheme is proved for the cases Kc[K/N (Nr− m + 1) : K] and N = Nrwith m+u−1 dividing N (where u = [ KcN K ]), and is further numerically verified for N ≤ 60. Beyond the appealing order-optimality result, we also show that the proposed scheme achieves significant gains over the current state of the art in practice. Experimental results over Tencent Cloud show the reduction of whole distributed computing process time of our scheme is up to 72.8% compared to the benchmark scheme which treats the computation on Kclinear combinations as Kcindividual computations.

Secure aggregation usually aims at securely computing the sum of the inputs fromKusers at a server. Noticing that the sum might inevitably reveal information about the inputs (when the inputs are non-uniform) and typically the users (not the server) desire the sum (in applications such as federated learning), we consider a variant of secure aggregation where the server is oblivious, i.e., the server only serves as a communication facilitator/helper to enable the users to securely compute the sum and learns nothing in the process. Our communication protocol involves one round of messages from the users to the server and one round of messages from the server to each user such that in the end each user only learns the sum of allKinputs and the server learns no information about the inputs. For this secure aggregation with an oblivious server problem, we show that to compute 1 bit of the sum securely, each user needs to send at least 1 bit to the server, the server needs to send at least 1 bit to each user, each user needs to hold a key of at least 2 bits, and all users need to collectively hold at leastKkey bits. In addition, when arbitrary user dropouts are allowed, the optimal performance remains the same, except that the minimum size of the key held by each user increases toKbits, per sum bit.

Secure aggregation is concerned with the task of securely computing the sum of the inputs from multiple users by an aggregation server without letting the server know the inputs beyond their summation. It finds broad applications in distributed machine learning paradigms such as federated learning (FL) where numerous clients, each holding a proprietary dataset, periodically upload their locally trained models (abstracted as inputs) to a parameter server. The server then generates an aggregate model, typically through averaging, which is shared back with clients as the starting point for a new round of local training. To protect data security, secure aggregation protocols leverage cryptographic techniques to ensure the server gains no additional information beyond the input sum, even if it colludes with a subset of users. While the simple star client-server architecture provides insights into the fundamental utility-security trade-off in secure aggregation, it falls short of capturing the impact of network topology in practical systems. Motivated by hierarchical federated learning, we investigate the secure aggregation problem in a three-layer hierarchical network, where clustered users communicate with an aggregation server via an intermediate layer of relays. In addition to conventional server security which ensures the server learns only the input sum, we also impose relay security, requiring that the relays remain oblivious to users’ inputs. For such a hierarchical secure aggregation (HSA) problem, we characterize the optimal multifaceted trade-off between communication efficiency (measured by user-to-relay and relay-to-server communication rates) and key generation efficiency (including individual and source key rates). A core contribution of this work is the derivation of the optimal source key rate as a function of the number of relays, cluster size, and collusion level. We propose an optimal communication scheme alongside a key generation scheme utilizing a novel matrix structure called extended Vandermonde matrix that guarantees both input sum recovery and security. Moreover, we derive a tight information-theoretic converse proof to establish the optimal rate region for the HSA problem.

In a typical formulation of the private information retrieval (PIR) problem, a single user wishes to retrieve one out of$ K$files from N servers without revealing the demanded file index to any server. This paper formulates an extended model of PIR, referred to as multi-message private computation (MM-PC), where instead of retrieving a single file, the user wishes to retrieve$P\gt 1$linear combinations of files while preserving the privacy of the demand information. The MM-PC problem is a generalization of the private computation (PC) problem (where the user requests one linear combination of the files), and the multi-message private information retrieval (MM-PIR) problem (where the user requests$P\gt 1$files). A baseline achievable scheme repeats the optimal PC scheme by Sun and Jafar P times, or treats each possible demanded linear combination as an independent file and then uses the near optimal MM-PIR scheme by Banawan and Ulukus. In this paper, we propose a new MM-PC scheme that significantly improves upon the baseline schemes. In doing so, we design the queries inspired by the structure in the cache-aided scalar linear function retrieval scheme by Wan et al., which leverages the dependency between linear functions to reduce the amount of communications. To ensure the decodability of our scheme, we propose a new method to benefit from the existing dependency, referred to as the sign assignment step. In the end, we use Maximum Distance Separable matrices to code the queries, which allows the reduction of download from the servers, while preserving privacy. By the proposed schemes, we characterize the capacity within a multiplicative factor of 2.

In secure summation,Kusers, each holds an input, wish to compute the sum of the inputs at a server without revealing any information aboutall the inputseven if the server may collude withan arbitrary subset of users. In this work, we relax the security and colluding constraints, where the set of inputs whose information is prohibited from leakage is from a predetermined collection of sets (e.g., any set of up toSinputs) and the set of colluding users is from another predetermined collection of sets (e.g., any set of up toTusers). For arbitrary collection of security input sets and colluding user sets, we characterize the optimal randomness assumption, i.e., the minimum number of key bits that need to be held by the users, per input bit, for weakly secure summation to be feasible, which generally involves solving a linear program.

In the secure groupcast problem, a transmitter wants to securely groupcast a message with the maximum rate to the first N of K receivers by broadcasting with the minimum bandwidth, where the K receivers are each equipped with a key variable from a known joint distribution. Examples are provided to prove that different instances of secure groupcast that have the same entropic structure, i.e., the same entropy for all subsets of the key variables, can have different maximum groupcast rates and different minimum broadcast bandwidth. Thus, extra-entropic structure matters for secure groupcast. Next, the maximum groupcast rate is explored when the key variables are generic linear combinations of a basis set of independent key symbols, i.e., the keys lie in generic subspaces. The maximum groupcast rate is characterized when the dimension of each key subspace is either small or large, i.e., the extreme regimes. For the intermediate regime, various interference alignment schemes originated from wireless interference networks, such as eigenvector based and asymptotic schemes, are shown to be useful.

A collection ofKrandom variables are called$(K,n)$-MDS if anynof theKvariables are independent and determine all remaining variables. In the MDS variable generation problem,Kusers wish to generate variables that are$(K,n)$-MDS using a randomness variable owned by each user. We show that to generate 1 bit of$(K,n)$-MDS variables for each$n \in \{1,2,\cdots , K\}$, the minimum size of the randomness variable at each user is$1 + 1/2 + \cdots + 1/K$bits. An intimately related problem is secure summation with user selection, where a server may select an arbitrary subset ofKusers and securely compute the sum of the inputs of the selected users. We show that to compute 1 bit of an arbitrarily chosen sum securely, the minimum size of the key held by each user is$1 + 1/2 + \cdots + 1/(K-1)$bits, whose achievability uses the generation of$(K,n)$-MDS variables for$n \in \{1,2,\cdots ,K-1\}$.

In a typical formulation of the private information retrieval (PIR) problem, a single user wishes to retrieve one out of$K$files from$N$servers without revealing the demanded file index to any server. This paper formulates an extended model of PIR, referred to as multi-message private computation (MMPC), where instead of retrieving a single file, the user wishes to retrieve$P > 1$linear combinations of files while preserving the privacy of the demand information. The MM-PC problem is a generalization of the private computation (PC) problem (where the user requests one linear combination of the files), and the multi-message private information retrieval (MM-PIR) problem (where the user requests$P > 1$files). A baseline achievable scheme repeats the optimal PC scheme by Sun and Jafar$P$times, or treats each possible demanded linear combination as an independent file and then uses the near optimal MM-PIR scheme by Banawan and Ulukus. In this paper, we propose an achievable MM-PC scheme that significantly improves upon the baseline scheme. Doing so, we design the queries inspired from the structure in the cache-aided scalar linear function retrieval scheme, where they leverage the dependency between messages to reduce the amount of communication. To ensure the decodability of our scheme, we propose a new method to benefit from the existing dependency, referred to as the sign assignment step. In the end, we use Maximum Distance Separable matrices to code the queries, which allows the reduction of download from the servers, while preserving privacy.

This paper considers the secure aggregation problem for federated learning under an information theoretic cryptographic formulation, where distributed training nodes (referred to as users) train models based on their own local data and a server aggregates the trained models without retrieving other information about users' local data. Secure aggregation generally contains two phases, namely key sharing phase and model aggregation phase. Due to the common effect of user dropouts in federated learning, the model aggregation phase should contain two rounds, where in the first round the users transmit masked models and according to the identity of surviving users, the surviving users then transmit some further messages to help the server decrypt the sum of users' trained models. The objective of the considered information theoretic formulation is to characterize the capacity region of the communication rates from the users to the server in the two rounds of the model aggregation phase, by assuming that the key sharing have already been done offline in prior. If the keys shared by the users could be any random variables, the capacity was fully characterized in the literature. Recently, an additional constraint on the keys (referred to as uncoded groupwise keys) was added into the problem, where there are several independent keys in the system and each key is shared by exactly S users, where S is a system parameter. In this paper, we fully characterize the capacity region for this problem by matching new converse and achievable bounds.

This paper studies information theoretic secure aggregation in federated learning, involving K distributed users and a central server. “Secure” means that the server can only get aggregated locally trained model updates, with no other information about the local users' data being leaked to the server. In addition, the effect of user dropouts is considered, where at most$\mathsf{K}-\mathsf{U}$users can drop and the identity of these users cannot be predicted in advance. Users share keys in an offline way independently of the models, and send the encrypted models to the server in the model aggregation phase. The objective of this problem is to minimize the number of transmissions in the model aggregation phase. A secure aggregation scheme with uncoded groupwise keys, where any$\mathsf{S}$users share an independent key, was recently proposed to achieve the same optimal communication cost as the best scheme with coded keys when$\mathsf{S} > \mathsf{K}-\mathsf{U}$. In this paper, we additionally consider the potential impact of user collusion, where up to$\mathsf{T}$users may collude with the server. For this setting, we propose a secure aggregation scheme with uncoded groupwise keys that guarantees secure aggregation with$\mathsf{U}$non-dropped users and$\mathsf{T}$colluding users provided that$\mathsf{K}-\mathsf{U}+1\leq \mathsf{S}\leq$K - T, and is proven to achieve the optimality without any constraint on the keys.

Secure aggregation is concerned with the task of securely uploading the inputs associated with multiple users to an aggregation server without revealing the user inputs to the server besides the summation of all inputs. It finds broad applications in distributed machine learning paradigms such as federated learning (FL). Motivated by practical hierarchical FL systems which utilize the client-edge-cloud network architecture to improve delay performance, we study the hierarchical secure aggregation (HSA) problem in a 3-layer hierarchical network where a total of$UV$users are connected to an aggregation server through$U$relay nodes each being associated with a disjoint subset of$V$users. Security requires that the server learn nothing beyond the desired sum of the inputs (server security), and each relay learn nothing about the user inputs (relay security) even if they collude with up to$T$users. We characterize the optimal communication and key rate region by proposing a novel secure aggregation scheme and deriving an information-theoretic converse that matches the achievable scheme. In particular, we show that when$T\geq(U-1)V$, the proposed HSA problem is infeasible. Otherwise when$T < (U-1)V$, to securely compute 1 bit of the desired sum, each user needs to upload at least 1 bit to its associating relay, each relay needs to upload at least 1 bit to the server, each user needs to hold at least 1 key bit, and all users need to collectively hold at least$\max\{V+T, \min\{U+T-1,UV- 1\}\}$(source) key bits. The characterization of the source key rate is a major contribution of this work.

The secure summation problem is studied with user selection and collusion, where a server may select any$U$out of$K$users and compute the sum of the inputs from the selected users without learning any additional information even if the server colludes with any$T$out of$K$users. The optimal communication and randomness rate is characterized when either$U=2$or$T=1$, i.e., to securely compute 1 bit of the selected sum, each user needs to send 1 bit to the server, each user needs to hold a key of$T+1$bits when$U=2$and$U/(U-1)$-bits when$T=1$, and all users need to hold key variables of ($\binom{T+2}{2}$) bits when$U=2$and$U/(U-1)+U-1$bits when$T=1$.

This paper investigates the privacy problem in coded caching. Recently, it was shown that the seminal MAN coded caching scheme leaks the demand information of each user to the other users in the system. Many works have considered coded caching with demand privacy, while every non-trivial existing coded caching scheme with private demands was built on the fact that the cache information of each user is private to the others. However, most of these schemes leak the users’ cache information. As a consequence, in most realistic settings (e.g., video streaming) where the system is used over time with multiple sequential transmission rounds, these schemes leak demand privacy beyond the first round. This observation motivates our new formulation of coded caching with simultaneously private demands and caches in this paper. For this new model, we first show that an existing coded caching scheme with private demands, referred to as the virtual users scheme, can also preserve the privacy of the users’ caches. However, this scheme suffers from its extremely high subpacketization. The main contribution of this paper is a new construction that generates private coded caching schemes by leveraging two-server private information retrieval (PIR) schemes. We show that if in the PIR scheme the demand is uniform over all files and the queries are independent, the resulting caching scheme is private on both the demands and the caches; otherwise, the resulting scheme is private only on the demands. This first result constructs coded caching schemes from a particular class of PIR schemes, which is a new “structural” result in its own merit. We then construct new two-server PIR schemes with uniform demand and independent queries, such that the resulting caching scheme has a subpacketization level that is significantly reduced compared to the virtual users scheme. Interestingly we propose a new construction of two-server PIR schemes with uniform demand and independent queries by exploiting coded caching schemes. By applying the seminal Maddah-Ali and Niesen coded caching scheme in our construction, the resulting two-server PIR scheme is proved to be order-optimal under the constraint of uniform demand and independent queries. This is a second new “structural” result that somehow closes the loop in the relationship between coded caching and PIR. As a by-product of our new construction, we obtain a new demand private that improves the load of the state-of-the-art demand private caching schemes known so far. Finally, to explore a broader tradeoff between cache privacy and transmission load, we relax the cache privacy constraint and introduce the definition of cache information leakage. Then, again as a by-product of our new construction, we propose new schemes with perfect demand privacy and imperfect cache privacy that achieve an order-gain in load with respect to the scheme with perfect privacy on both demands and caches. This also establishes a first non-trivial achievability result in the tradeoff between load and cache privacy, for demand-private caching schemes.

A storage code over a graph maps$K$independent source symbols, each of$L_{w}$bits, to$N$coded symbols, each of$L_{v}$bits, such that each coded symbol is stored in a node of the graph and each edge of the graph is associated with one source symbol. From a pair of nodes connected by an edge, the source symbol that is associated with the edge can be decoded. The ratio$L_{w}/L_{v}$is called the symbol rate of a storage code and the highest symbol rate is called the capacity. We show that the three highest capacity values of storage codes over graphs are$2, 3/2, 4/3$. We characterize all graphs over which the storage code capacity is 2 and$3/2$, and for capacity value of$4/3$, necessary condition and sufficient condition (that do not match) on the graphs are given.

This paper considers the secure aggregation problem for federated learning under an information theoretic cryptographic formulation, where distributed training nodes (referred to as users) train models based on their own local data and a curious-but-honest server aggregates the trained models without retrieving other information about users’ local data. Secure aggregation generally contains two phases, namely key sharing phase and model aggregation phase. Due to the common effect of user dropouts in federated learning, the model aggregation phase should contain two rounds, where in the first round the users transmit masked models and, in the second round, according to the identity of surviving users after the first round, these surviving users transmit some further messages to help the server decrypt the sum of users’ trained models. The objective of the considered information theoretic formulation is to characterize the capacity region of the communication rates from the users to the server in the two rounds of the model aggregation phase, assuming that key sharing has already been performed offline in prior. In this context, Zhao and Sun completely characterized the capacity region under the assumption that the keys can be arbitrary random variables. More recently, an additional constraint, known as “uncoded groupwise keys,” has been introduced. This constraint entails the presence of multiple independent keys within the system, with each key being shared by precisely S users, where S is a defined system parameter. The capacity region for the information theoretic secure aggregation problem with uncoded groupwise keys was established in our recent work subject to the condition S > K - U, where K is the number of total users and U is the designed minimum number of surviving users (which is another system parameter). In this paper we fully characterize the capacity region for this problem by matching a new converse bound and an achievable scheme. Experimental results over the Tencent Cloud show the improvement on the model aggregation time compared to the original secure aggregation scheme.

Secure aggregation, which is a core component of federated learning, aggregates locally trained models from distributed users at a central server. The “secure” nature of such aggregation consists of the fact that no information about the local users’ data must be leaked to the server except the aggregated local models. In order to guarantee security, some keys may be shared among the users (this is referred to as the key sharing phase). After the key sharing phase, each user masks its trained model which is then sent to the server (this is referred to as the model aggregation phase). This paper follows the information theoretic secure aggregation problem originally formulated by Zhao and Sun, with the objective to characterize the minimum communication cost from the$\mathsf K$users in the model aggregation phase. Due to user dropouts, which are common in real systems, the server may not receive all messages from the users. A secure aggregation scheme should tolerate the dropouts of at most${\mathsf K}-{\mathsf U}$users, where$\mathsf U$is a system parameter. The optimal communication cost is characterized by Zhao and Sun, but with the assumption that the keys stored by the users could be any random variables with arbitrary dependency. On the motivation that uncoded groupwise keys are more convenient to be shared and could be used in large range of applications besides federated learning, in this paper we add one constraint into the above problem, namely, that the key variables are mutually independent and each key is shared by a group of$\mathsf S$users, where$\mathsf S$is another system parameter. To the best of our knowledge, all existing secure aggregation schemes (with information theoretic security or computational security) assign coded keys to the users. We show that if${\mathsf S}\gt {\mathsf K}-{\mathsf U}$, a new secure aggregation scheme with uncoded groupwise keys can achieve the same optimal communication cost as the best scheme with coded keys; if${\mathsf S}\leq {\mathsf K}-{\mathsf U}$, uncoded groupwise key sharing is strictly sub-optimal. Finally, we also implement our proposed secure aggregation scheme into Amazon EC2, which are then compared with the existing secure aggregation schemes with offline key sharing.

The secure summation problem is considered, where$K$users, each holds an input, wish to compute the sum of their inputs at a server securely, i.e., without revealing any information beyond the sum even if the server may collude with any set of up to$T$users. First, we prove a folklore result for secure summation - to compute 1 bit of the sum securely, each user needs to send at least 1 bit to the server, each user needs to hold a key of at least 1 bit, and all users need to hold collectively some key variables of at least$K-1$bits. Next, we allow any arbitrary group of users to share an independent key and any arbitrary group of users to collude with the server. For such a general groupwise key and colluding user setting, we show that secure summation is feasible if and only if the hypergraph, where each node is a user and each edge is a group of users sharing the same key, is connected after removing the nodes corresponding to any colluding set of users and their incident edges. Finally, we focus on the symmetric groupwise key setting, where every group of$G$users share an independent key. We show that for symmetric groupwise keys with group size$G$, if$G =1$or$G > K-T$, the secure summation problem is not feasible; else$1 < G \leq K-T$, to compute 1 bit of the sum securely, each user needs to send at least 1 bit to the server and the size of each groupwise key is at least$(K-T-1)/\binom {K-T}{G}$bits.

Secure aggregation, which is a core component of federated learning, aggregates locally trained models from distributed users at a central server, without revealing any other information about the local users' data. This paper follows a recent information theoretic secure aggregation problem with user dropouts, where the objective is to characterize the minimum communication cost from the$\mathrm{K}$users to the server during the model aggregation. All existing secure aggregation protocols let the users share and store coded keys to guarantee security. On the motivation that uncoded groupwise keys are more convenient to be shared and could be used in large range of practical applications, this paper is the first to consider uncoded groupwise keys, where the keys are mutually independent and each key is shared by a group of$\mathrm{S}$users. We show that if$\mathrm{S}$is beyond a threshold, a new secure aggregation protocol with uncoded groupwise keys, referred to as GroupSecAgg, can achieve the same optimal communication cost as the best protocol with coded keys. The experiments on Amazon EC2 show the considerable improvements on the key sharing and model aggregation times compared to the state-of-the art.

Distributed Linearly Separable Computation problem under the cyclic assignment is studied in this paper. It is a problem widely existing in cooperated distributed gradient coding, real-time rendering, linear transformers, etc. In a distributed computing system, a master asks N distributed workers to compute a linearly separable function from K datasets. The task function can be expressed as Kclinear combinations of K messages, where each message is the output of one individual function of one dataset. Straggler effect is also considered, such that from the answers of each Nrworker, the master should recover the task. The computation cost is defined as the number of datasets assigned to each worker, while the communication cost is defined as the number of (coded) messages which should be received. The objective is to characterize the optimal tradeoff between the computation and communication costs. Various distributed computing scheme were proposed in the literature with a well-known cyclic data assignment, but the (order) optimality of this problem remains open, even under the cyclic assignment. This paper proposes a new computing scheme with the cyclic assignment based on interference alignment, which is near optimal under the cyclic assignment.

A storage code over a graph maps K independent source symbols, each of Lwbits, to N coded symbols, each of Lvbits, such that each coded symbol is stored in a node of the graph and each edge of the graph is associated with one source symbol. From a pair of nodes connected by an edge, the source symbol that is associated with the edge can be decoded. The ratio Lw/Lvis called the symbol rate of a storage code and the highest symbol rate is called the capacity. We show that the three highest capacity values of storage codes over graphs are 2, 3/2, 4/3. We characterize all graphs over which the storage code capacity is 2 and 3/2, and for capacity value of 4/3, necessary condition and sufficient condition (that do not match) on the graphs are given.

In secure summation, K users, each holds an input, wish to compute the sum of the inputs at a server without revealing any information about all the inputs even if the server may collude with an arbitrary subset of users. In this work, we relax the security and colluding constraints, where the set of inputs whose information is prohibited from leakage is from a predetermined collection of sets (e.g., any set of up to S inputs) and the set of colluding users is from another predetermined collection of sets (e.g., any set of up to T users). For arbitrary collection of security input sets and colluding user sets, we characterize the optimal randomness assumption, i.e., the minimum number of key bits that need to be held by the users, per input bit, for weakly secure summation to be feasible, which generally involves solving a linear program.

A collection of K random variables are called (K,n)-MDS if any n of the K variables are independent and determine all remaining variables. In the MDS variable generation problem, K users wish to generate variables that are (K,n)-MDS using a randomness variable owned by each user. We show that to generate 1 bit of (K,n)-MDS variables for each n ∈ {1,2, ⋯ ,K}, the minimum size of the randomness variable at each user is 1+1/2+ ⋯ +1/K bits.

Conditional disclosure of secrets (CDS) is the problem of disclosing as efficiently as possible, one secret from Alice and Bob to Carol if and only if the inputs at Alice and Bob satisfy some function. The information theoretic capacity of CDS is the maximum number of bits of the secret that can be securely disclosed per bit of total communication from Alice and Bob to Carol. All CDS instances, where the capacity is the highest and is equal to 1/2, are recently characterized through a noise and signal alignment approach and are described using a graph representation of the function. In this work, we go beyond the best case scenarios and further develop the alignment approach to characterize the linear capacity of a class of CDS instances to be$(\rho -1)/(2\rho)$, where$\rho $is a newly introduced and highly specific covering parameter of the graph representation of the function.

A secure storage code maps$K$source symbols, each of$L_{w}$bits, to$N$coded symbols, each of$L_{v}$bits, such that each coded symbol is stored in a node of a graph (one may view a node as a server). Each edge of the graph is either associated with$D$of the$K$source symbols such that from the pair of nodes connected by the edge, we can decode the$D$source symbols and learn no information about the remaining$K-D$source symbols; or the edge is associated with no source symbols such that from the pair of nodes connected by the edge, nothing about the$K$source symbols is revealed. The ratio$L_{w}/L_{v}$is called the symbol rate of a secure storage code and the highest possible symbol rate is called the capacity. We characterize all graphs over which the capacity of a secure storage code is equal to 1, when$D = 1$. This result is generalized to$D> 1$, i.e., we characterize all graphs over which the capacity of a secure storage code is equal to$1/D$under a mild condition that for any node, the source symbols associated with each of its connected edges do not include a common element. Further, we characterize all graphs over which the capacity of a secure storage code is equal to$2/D$.

In the coded caching literature, the notion of privacy is considered only against demands. On the motivation that multi-round transmissions almost appear everywhere in real communication systems, this paper formulates the coded caching problem with private demands and caches. Only one existing private caching scheme, which is based on introducing virtual users, can preserve the privacy of demands and caches simultaneously, but at the cost of an extremely large subpacketization exponential in the product of the number of users (K) and files (N) in the system. In order to reduce the subpacketization while satisfying the privacy constraints, we propose a novel approach which constructs private coded caching schemes through private information retrieval (PIR). Based on this approach, we propose novel schemes with private demands and caches which have a subpacketization level in the order exponential with K instead of NK in the virtual user scheme. As a by-product, for the coded caching problem with private demands, a private coded caching scheme could be obtained from the proposed approach, which generally improves the memory-load tradeoff of the private coded caching scheme by Yan and Tuninetti.

We consider the cache-aided multiuser private information retrieval (MuPIR) problem with a focus on the special case of two messages, two users and arbitrary number of databases where the users have distinct demands of the messages. We characterize the optimal memory-load trade-off for the considered MuPIR problem by proposing a novel achievable scheme and a tight converse. The proposed achievable scheme uses the idea of cache-aided interference alignment (CIA) developed in the literature by the same authors. The proposed converse uses a tree-like decoding structure to incorporate both the decodability and privacy requirements of the users. While the optimal characterization of the cache-aided MuPIR problem is challenging in general, this work provides insight into understanding the general structure of the cache-aided MuPIR problem.

In the conditional disclosure of secrets (CDS) problem, Alice and Bob (each holds an input and a common secret) wish to disclose, as efficiently as possible, the secret to Carol if and only if their inputs satisfy some function. The capacity of CDS is the maximum number of bits of the secret that can be securely disclosed per bit of total communication. We characterize the necessary and sufficient condition for the extreme case where the capacity of CDS is the highest and is equal to$1/2$. For the simplest instance where the capacity is smaller than$1/2$, we show that the linear capacity is$2/5$.

We consider a transmitter and$K$receivers, each of which shares a key variable with the transmitter. Through a noiseless broadcast channel, the transmitter wishes to send a common message$W$securely to$N$out of the$K$receivers while the remaining$K-N$receivers learn no information about$W$. We are interested in the maximum message rate, i.e., the maximum number of bits of$W$that can be securely groupcast to the legitimate receivers per key block and the minimum broadcast bandwidth, i.e., the minimum number of bits of the broadcast information required to securely groupcast the message bits. We focus on the setting of combinatorial keys, where every subset of the$K$receivers share an independent key of arbitrary size. Under this combinatorial key setting, the maximum message rate is characterized for the following scenarios - 1)$N=1$or$N=K-1$, i.e., secure unicast to 1 receiver with$K-1$eavesdroppers or secure groupcast to$K-1$receivers with 1 eavesdropper, 2)$N=2, K=4$, i.e., secure groupcast to 2 out of 4 receivers, and 3) the symmetric setting where the key size for any subset of the same cardinality is equal for any$N,K$. Further, for the latter two cases, the minimum broadcast bandwidth for the maximum message rate is characterized.

This paper formulates a distributed computation problem, where a master asks${\mathsf N}$distributed workers to compute a linearly separable function. The task function can be expressed as${\mathsf K}_{\mathrm{ c}}$linear combinations of${\mathsf K}$messages, where each message is a function of one dataset. Our objective is to find the optimal tradeoff between the computation cost (number of uncoded datasets assigned to each worker) and the communication cost (number of symbols the master must download), such that from the answers of any${\mathsf N}_{\mathrm{ r}}$out of${\mathsf N}$workers the master can recover the task function with high probability, where the coefficients of the${\mathsf K}_{\mathrm{ c}}$linear combinations are uniformly i.i.d. over some large enough finite field. The formulated problem can be seen as a generalized version of some existing problems, such as distributed gradient coding and distributed linear transform. In this paper, we consider the specific case where the computation cost is minimum, and propose novel achievability schemes and converse bounds for the optimal communication cost. Achievability and converse bounds coincide for some system parameters; when they do not match, we prove that the achievable distributed computing scheme is optimal under the constraint of a widely used ‘cyclic assignment’ scheme on the datasets. Our results also show that when${\mathsf K}= {\mathsf N}$, with the same communication cost as the optimal distributed gradient coding scheme proposed by Tandonet al. from which the master recovers one linear combination of${\mathsf K}$messages, our proposed scheme can let the master recover any additional${\mathsf N}_{\mathrm{ r}}-1$independent linear combinations of messages with high probability.

Coded caching is a promising technique to smooth out network traffic by storing part of the library content at the users’ local caches. The seminal work on coded caching for single file retrieval by Maddah-Ali and Niesen (MAN) showed the existence of a global caching gain that scales with the total memory in the system, in addition to the known local caching gain in uncoded systems. This paper formulates a novel cache-aided matrix multiplication retrieval problem, relevant for data analytics and machine learning applications. In the considered problem, each cache-aided user requests the product of two matrices from the library. A structure-agnostic solution is to treat each possible matrix product as an independent file and use the MAN coded caching scheme for single file retrieval. This paper proposes two structure-aware schemes, which partition each matrix in the library by either rows or columns and let a subset of users cache some sub-matrices, that improve on the structure-agnostic scheme. For the case where the library matrices are “fat” matrices, the structure-aware row-partition scheme is shown to be order optimal under some constraint.

In the coded caching problem, as originally formulated by Maddah-Ali and Niesen, a server communicates via a noiseless shared broadcast link to multiple users that have local storage capability. In order for a user to decode its demanded file from the coded multicast transmission, the demands of all the users must be globally known, which may violate the privacy of the users. To overcome this privacy problem, Wan and Caire recently proposed several schemes that attain coded multicasting gain while simultaneously guarantee information theoretic privacy of the users’ demands. In Device-to-Device (D2D) networks, the demand privacy problem is further exacerbated by the fact that each user is also a transmitter, which appears to be needing the knowledge of the files demanded by the remaining users in order to form its coded multicast transmission. This paper shows how to solve this seemingly infeasible problem. The main contribution of this paper is the development of new achievable and converse bounds for D2D coded caching that are to within a constant factor of one another when privacy of the users’ demands must be guaranteed even in the presence of colluding users (i.e., when some users share cached contents and demanded file indices). First, a D2D private caching scheme is proposed, whose key feature is the addition of virtual users in the system in order to “hide” the demands of the real users. By comparing the achievable D2D private load with an existing converse bound for the shared-link model without demand privacy constraint, the proposed scheme is shown to be order optimal, except for the very low memory size regime with more files than users. Second, in order to shed light into the open parameter regime, a new achievable scheme and a new converse bound under the constraint of uncoded cache placement (i.e., when each user stores directly a subset of the bits of the library) are developed for the case of two users, and shown to be to within a constant factor of one another for all system parameters. Finally, the two-user converse bound is extended to any number of users by a cut-set type argument. With this new converse bound, the virtual users scheme is shown to be order optimal in all parameter regimes under the constraint of uncoded cache placement and user collusion.

In the robust secure aggregation problem, a server wishes to learn and only learn the sum of the inputs of a number of users while some users may drop out (i.e., may not respond). The identity of the dropped users is not known a priori and the server needs to securely recover the sum of the remaining surviving users. We consider the following minimal two-round model of secure aggregation. Over the first round, any set of no fewer than$U$users out of$K$users respond to the server and the server wants to learn the sum of the inputs of all responding users. The remaining users are viewed as dropped. Over the second round, any set of no fewer than$U$users of the surviving users respond (i.e., dropouts are still possible over the second round) and from the information obtained from the surviving users over the two rounds, the server can decode the desired sum. The security constraint is that even if the server colludes with any$T$users and the messages from the dropped users are received by the server (e.g., delayed packets), the server is not able to infer any additional information beyond the sum in the information theoretic sense. For this information theoretic secure aggregation problem, we characterize the optimal communication cost. When$U \leq T$, secure aggregation is not feasible, and when$U > T$, to securely compute one symbol of the sum, the minimum number of symbols sent from each user to the server is 1 over the first round, and$1/(U-T)$over the second round.

Conditional disclosure of secrets (CDS) is the problem of disclosing as efficiently as possible, one secret from Alice and Bob to Carol if and only if the inputs at Alice and Bob satisfy some function f. The information theoretic capacity of CDS is the maximum number of bits of the secret that can be securely disclosed per bit of total communication. All CDS instances, where the capacity is the highest and is equal to 1/2, are recently characterized through a noise and signal alignment approach and are described using a graph representation of the function f, Gf. In this work, we go beyond the best case scenarios and further develop the alignment approach to characterize the linear capacity of a class of CDS instances to be (p- 1)/(2p), where$p$is a covering parameter of Gf.

The compound secure groupcast problem is considered, where the key variables at$K$receivers are designed so that a transmitter can securely groupcast a message to any$N$out of the$K$receivers through a noiseless broadcast channel. The metric is the information theoretic tradeoff between key storage$\alpha$, i.e., the number of bits of the key variable per message bit, and broadcast bandwidth$\beta$, i.e., the number of bits of the broadcast information per message bit. We present two results. First, when broadcast bandwidth is minimized, i.e., when$\beta=1$, we show that the minimum key storage is$\alpha=N$. Second, when key storage is minimized, i.e., when$\alpha=1$, we show that broadcast bandwidth$\beta=\min(N, K-N+1)$is achievable.

Distributed linearly separable computation, where a user asks some distributed servers to compute a linearly separable function, was recently formulated by the same authors and aims to alleviate the bottlenecks of stragglers and communication cost in distributed computation. For this purpose, the data center assigns a subset of input datasets to each server, and each server computes some coded packets on the assigned datasets, which are then sent to the user. The user should recover the task function from the answers of a subset of servers, such that the effect of stragglers could be tolerated. In this paper, we formulate a novel secure framework for this distributed linearly separable computation, where we aim to let the user only retrieve the desired function without obtaining any other information about the input datasets, even if it receives the answers of all servers. In order to preserve the security of the input datasets, some common randomness variable independent of the datasets should be introduced into the transmission. We show that any non-secure linear-coding based computing scheme for the original distributed linearly separable computation problem, can be made secure without increasing the communication cost (number of symbols the user should receive). Then we focus on the case where the computation cost of each server (number of datasets assigned to each server) is minimum and aim to minimize the size of the randomness variable (i.e., randomness size) introduced in the system while achieving the optimal communication cost. Novel information theoretic converse bound on the randomness size and some achievable schemes are proposed, where they coincide in some cases.

This paper formulates the shared-link cache-aided matrix multiplication retrieval problem. Matrix multiplication is an essential building block for distributed computing applications. Different from the original coded caching single file retrieval model, in the considered problem each cache-aided user requests the product of two matrices from a library that contains N matrices. A trivial solution, agnostic to the structure of matrix multiplication, is to treat each of the N2possible matrix products as a file in the original single file retrieval coded caching problem. Such a solution can be improved by leveraging the correlation among the entries in the matrix product. In this paper, two structure-aware schemes are proposed, which partition each library matrix either by rows or by columns, and let a subset of users cache some sub-matrices; in the delivery, coded multicast messages are created to leverage the cached content and the correlation among the entries in the requested matrix products. These schemes outperform two baseline schemes, where one sends packets without coding and the other lets each user directly recover the two input matrices. Order optimality results are derived in some parameter regimes.

In the problem of cache-aided multiuser private information retrieval (MuPIR), a set of$K_{\mathrm{u}}$cache-equipped users wish to privately download a set of messages from$N$distributed databases each holding a library of$K$messages. The system works in two phases: the cache placement (prefetching) phase in which the users fill up their cache memory, and the private delivery phase in which the users' demands are revealed and they download an answer from each database so that the their desired messages can be recovered while each individual database learns nothing about the identities of the requested messages. The goal is to design the placement and the private delivery phases such that the load, which is defined as the total number of downloaded bits normalized by the message size, is minimized given any user memory size. This paper considers the MuPIR problem with two messages, arbitrary number of users and databases where uncoded prefetching is assumed, i.e., the users directly copy some bits from the library as their cached contents. We propose a novel MuPIR scheme inspired by the Maddah-Ali and Niesen (MAN) coded caching scheme. The proposed scheme achieves lower load than any existing schemes, especially the product design (PD), and is shown to be optimal within a factor of 8 in general and exactly optimal at very high or very low memory regimes.

In the robust secure aggregation problem, a server wishes to learn and only learn the sum of the inputs of a number of users while some users may drop out (i.e., may not respond). The identity of the dropped users is not known a priori and the server needs to securely recover the sum of the remaining surviving users. We consider the following minimal two-round model of secure aggregation. Over the first round, any set of no fewer than$U$users out of$K$users respond to the server and the server wants to learn the sum of the inputs of all responding users. The remaining users are viewed as dropped. Over the second round, any set of no fewer than$U$users of the surviving users respond (i.e., dropouts are still possible over the second round) and from the information obtained from the surviving users over the two rounds, the server can decode the desired sum. The security constraint is that even if the server colludes with any$T$users and the messages from the dropped users are received by the server (e.g., delayed packets), the server is not able to infer any additional information beyond the sum in the information theoretic sense. For this information theoretic secure aggregation problem, we characterize the optimal communication cost. When$U\leq T$, secure aggregation is not feasible, and when$U > T$, to securely compute one symbol of the sum, the minimum number of symbols sent from each user to the server is 1 over the first round, and$1/(U-T)$over the second round.

In the conventional robust$T$-colluding private information retrieval (PIR) system, the user needs to retrieve one of the possible messages while keeping the identity of the requested message private from any$T$colluding servers. Motivated by the possible heterogeneous privacy requirements for different messages, we consider the ($N, T_{1}: K_{1}, T_{2}: K_{2}$) two-level PIR system, where$K_{1}$messages need to be retrieved privately against$T_{1}$colluding servers, and all the messages need to be retrieved privately against$T_{2}$colluding servers where$T_{2}\leq T_{1}$. We obtain a lower bound to the capacity by proposing a novel coding scheme, namely the non-uniform successive cancellation scheme. A capacity upper bound is also derived. The gap between the upper bound and the lower bound is analyzed, and shown to vanish when$T_{1}=T_{2}$.

The robust principles of treating interference as noise (TIN) when it is sufficiently weak, and avoiding it when it is not, form the background of this work. Combining TIN with the topological interference management (TIM) framework that identifies optimal interference avoidance schemes, we formulate a TIM-TIN problem for multilevel topological interference management, wherein only a coarse knowledge of channel strengths and no knowledge of channel phases is available to transmitters. To address the TIM-TIN problem, we first propose an analytical baseline approach, which decomposes a network into TIN and TIM components, allocates the signal power levels to each user in the TIN component, allocates signal vector space dimensions to each user in the TIM component, and guarantees that the product of the two is an achievable number of signal dimensions available to each user in the original network. Next, a distributed numerical algorithm called ZEST is developed. The convergence of the algorithm is demonstrated, leading to the duality of the TIM-TIN problem in terms of generalized degrees-of-freedom (GDoF). Numerical results are also provided to demonstrate the superior sum-rate performance and fast convergence of ZEST.

This paper studies the distributed linearly separable computation problem, which is a generalization of many existing distributed computing problems such as distributed gradient coding and distributed linear transform. A master asks${\mathsf {N}}$distributed workers to compute a linearly separable function of${\mathsf {K}}$datasets, which is a set of${\mathsf {K}}_{\mathrm{ c}}$linear combinations of${\mathsf {K}}$equal-length messages (each message is a function of one dataset). We assign some datasets to each worker in an uncoded manner, who then computes the corresponding messages and returns some function of these messages, such that from the answers of any${\mathsf {N}}_{\mathrm{ r}}$out of${\mathsf {N}}$workers the master can recover the task function with high probability. In the literature, the specific case where${\mathsf {K}}_{\mathrm{ c}}=1$or where the computation cost is minimum has been considered. In this paper, we focus on the general case (i.e., general${\mathsf {K}}_{\mathrm{ c}} $and general computation cost) and aim to find the minimum communication cost. We first propose a novel converse bound on the communication cost under the constraint of the popularcyclic assignment(widely considered in the literature), which assigns the datasets to the workers in a cyclic way. Motivated by the observation that existing strategies for distributed computing fall short of achieving the converse bound, we propose a novel distributed computing scheme for some system parameters. The proposed computing scheme is optimal for any assignment when${\mathsf {K}}_{\mathrm{ c}}$is large and is optimal under the cyclic assignment when the numbers of workers and datasets are equal or${\mathsf {K}}_{\mathrm{ c}}$is small. In addition, it is order optimal within a factor of 2 under the cyclic assignment for the remaining cases.

We consider the problem of cache-aided Multiuser Private Information Retrieval (MuPIR) which is an extension of the single-user cache-aided PIR problem to the case of multiple users. In cache-aided MuPIR, each of the$K_{\mathrm{ u}}$cache-equipped users wishes to privately retrieve a message out of$K$messages from$N$databases each having access to the entire message library. Demand privacy requires that any individual database learns nothing about the demands of all users. The users are connected to each database via an error-free shared-link. In this paper, we aim to characterize the optimal trade-off between user cache memory and communication load for such systems. First, we propose a novel approach ofcache-aided interference alignment (CIA), for the MuPIR problem with$K=2$messages,$K_{\mathrm{ u}}=2$users and$N\ge 2$databases. The CIA approach is optimal when the cache placement is uncoded. For general cache placement, the CIA approach is optimal when$N=2$and 3 verified by the computer-aided converse approach. Second, for the general case, we propose aproduct design(PD) which incorporates the PIR code into the linear caching code. The product design is shown to be order optimal within a multiplicative factor of 8 and is exactly optimal in the high memory regime.

Coded caching has the potential to greatly reduce network traffic by leveraging the cheap and abundant storage available in end-user devices so as to create multicast opportunities in the delivery phase. In the seminal work by Maddah-Ali and Niesen (MAN), the shared-link coded caching problem was formulated, where each user demands one file (i.e., single file retrieval). This article generalizes the MAN caching problem formulation from single file retrieval on the binary filed to general scalar linear function retrieval on an arbitrary finite field. The proposed novel scheme is linear, based on MAN uncoded cache placement, and leverages ideas from interference alignment. Quite surprisingly, the worst-case load of the proposed scheme among all possible demands is the same as the one of the scheme by Yu, Maddah-Ali, and Avestimehr (YMA) for single file retrieval. The proposed scheme has thus the same optimality guarantees as YMA, namely, it is optimal under the constraint of uncoded cache placement, and is optimal to within a factor 2 otherwise. Some extensions of the proposed scheme are then discussed. It is shown that the proposed scheme works not only on arbitrary finite field, but also on any commutative ring. The key idea of this article can be also extended to all scenarios to which the original MAN scheme has been extended, including but not limited to demand-private retrieval and Device-to-Device networks.

In order to preserve the privacy of the users demands from other users, in this paper we formulate a novel information theoretic Device-to-Device (D2D) private caching model by adding a trusted server. In the delivery phase, the trusted server collects the users demands and sends a query to each user, who then broadcasts packets according to this query. Two D2D private caching schemes (uncoded and coded) are proposed in this paper, which are shown to be order optimal.

In the conditional disclosure of secrets (CDS) problem, Alice and Bob (each holds an input and a common secret) wish to disclose, as efficiently as possible, the secret to Carol if and only if their inputs satisfy some function. The capacity of CDS is the maximum number of bits of the secret that can be securely disclosed per bit of total communication. We characterize the necessary and sufficient condition for the extreme case where the capacity of CDS is the highest and is equal to 1/2.

This paper considers cache-aided device-to-device (D2D) networks where a trusted server helps to preserve the privacy of the users' demands. Specifically, the trusted server collects the users' demands before the delivery phase and sends a query to each user, who then broadcasts multicast packets according to this query. Recently the Authors proposed a D2D private caching scheme that was shown to be order optimal except for the very low memory size regime, where the optimality was proved by comparing to a converse bound without privacy constraint. The main contribution of this paper is a novel converse bound for the studied model where users may collude (i.e., some users share cache contents and demanded files, and yet cannot infer what files the remaining users have demanded) and under the placement phase is uncoded. To the best of the Author's knowledge, such a general bound is the first that genuinely accounts for the demand privacy constraint. The novel converse bound not only allows to show that the known achievable scheme is order optimal in all cache size regimes (while the existing converse bounds cannot show it), but also has the potential to be used in other variants of demand private caching.

In the shared-link coded caching problem, formulated by Maddah-Ali and Niesen (MAN), each cache-aided user demands one file (i.e., single file retrieval). This paper generalizes the MAN problem so as to allow users to request scalar linear functions (aka, linear combinations with scalar coefficients) of the files. We propose a novel coded delivery scheme, based on MAN uncoded cache placement, that allows for the decoding of arbitrary scalar linear functions of the files on arbitrary finite fields. Surprisingly, it is shown that the load for cache-aided scalar linear function retrieval depends on the number of linearly independent functions that are demanded, akin to the cache-aided single-file retrieval problem where the load depends on the number of distinct file requests. The proposed scheme is proved to be optimal under the constraint of uncoded cache placement, in terms of worst-case load, and within a factor 2 otherwise.

This paper formulates the cache-aided multi-user Private Information Retrieval (MuPIR) problem, including Kucache-equipped users, each of which wishes to retrieve a desired message efficiently from N distributed databases with access to K independent messages. Privacy of the users’ demands requires that any individual database can not learn anything about the demands of the users. The load of this problem is defined as the average number of downloaded bits per desired message bit. The goal is to find the optimal memory-load trade-off while preserving the demand privacy. Besides the formulation of the MuPIR problem, the contribution of this paper is two-fold. First, we characterize the optimal memory-load trade-off for a system with N = 2 databases, K = 2 messages and Ku= 2 users demanding distinct messages; Second, a product design with order optimality guarantee is proposed. In addition, the product design can achieve the optimal load when the cache memory is large enough. The product design embeds the well-known Sun-Jafar PIR scheme into coded caching, in order to benefit from the coded caching gain while preserving the privacy of the users’ demands.

For the symmetric private information retrieval problem with K messages and N servers, we show that the minimum (symmetric) upload cost is log2(⌈K1/N-1⌉) bits per server, i.e., the user must upload a q-ary symbol to each server where q is at least ⌈K1/N-1⌉.

The topological interference management (TIM) problem studies the degrees of freedom (DoF) of partially-connected interference networks with no channel state information (CSI) at the transmitters except the network topology (i.e., partial connectivity). In this paper, we consider a variant of the TIM problem with uncertainty in network topology, where the channel state with partial connectivity is only known to belong to one of M states at the transmitters. In particular, the transmitter has access to all network topological information over M states, but is unaware of which state it falls in exactly for communication. The receiver at any state is aware of the exact state it falls in besides the network topologies of all states, and wish to recover as much highly-prioritized information at current state as possible. We formulate it as the opportunistic TIM problem with network uncertainty modeled by M state-varying network topologies. To adapt to network topology uncertainty and different message decoding priority, joint encoding and opportunistic decoding are enabled at the transmitters and receivers respectively. Specifically, being aware of all possible network topologies, each transmitter sends a signal jointly encoded from all messages desired over M states, say M distinct messages, and at a certain State m, Receiver k wishes to opportunistically decode the first πk(m) ∈ {1, 2, · · · , M} higher-priority messages. Under this opportunistic TIM setting, we construct a multi-state conflict graph to capture the mutual conflict of messages over M states, and characterize the optimal DoF region of two classes of network topologies via polyhedral combinatorics. A remarkable fact is that, under an additional mild monotonous condition, the optimality conditions of orthogonal access and one-to-one interference alignment still apply to TIM with uncertainty in network topology.

We introduce the problem of private information delivery (PID), comprised of K messages, a user, and N servers (each holds M ≤ K messages) that wish to deliver one out of K messages to the user privately, i.e., without revealing the delivered message index to the user. The information theoretic capacity of PID, C, is defined as the maximum number of bits of the desired message that can be privately delivered per bit of total communication to the user. For the PID problem with K messages, N servers, M messages stored per server, and N ≥ ΓMK⌉, we provide an achievable scheme of rate 1/ΓMK⌉ and an information theoretic converse of rate M/K, i.e., the PID capacity satisfies 1/ΓKM⌉ ≤ C ≤ M/K. This settles the capacity of PID whenMKis an integer. When K/M is not an integer, we show that the converse rate of M/K is achievable if N ≥ K/gcd(K,M ) - ( M/gcd(K,M) - 1)(⌊K/M⌋- 1), and the achievable rate of 1/ΓMK⌉ is optimal if N =ΓK/M⌉. Otherwise if ΓK/M⌉ <; N<; K/gcd(K,M) -( M/gcd(K,M) -1)(⌊K/M⌋-1), we give an improved achievable scheme and prove its optimality for several small settings.

The two-user computation broadcast problem is introduced as the setting where User 1 wants message W1and has side-information W1', User 2 wants message W2and has side-information (W2', and W1, W1', W2, W2') may have arbitrary dependencies. The rate of a computation broadcast scheme is defined as the ratio H(W1, W2)/H(S), where S is the information broadcast to both users to simultaneously satisfy their demands. The supremum of achievable rates is called the capacity of computation broadcast CCB. It is shown that CCB≤ H(W1, W2)/[H(W1|W1')+H(W2|W2')- min (I(W1; W2, W2'|W1'), I(W2; W1, W1'|W2'))] . For the linear computation broadcast problem, where W1, W1', W2, W2' are comprised of arbitrary linear combinations of a basis set of independent symbols, the bound is shown to be tight. For non-linear computation broadcast, it is shown that this bound is not tight in general. Examples are provided to prove that different instances of computation broadcast that have the same entropic structure, i.e., the same entropy for all subsets of {W1, W1', W2, W2'}, can have different capacities. Thus, extra-entropic structure matters even for two-user computation broadcast. The significance of extra-entropic structure is further explored through a class of non-linear computation broadcast problems where the extremal values of capacity are shown to correspond to minimally and maximally structured problems within that class.

A locally decodable code (LDC) maps K source symbols, each of size Lwbits, to M coded symbols, each of size Lxbits, such that each source symbol can be decoded from N ≤ M coded symbols. A perfectly smooth LDC further requires that each coded symbol is uniformly accessed when we decode any one of the messages. The ratio Lw/Lxis called the symbol rate of an LDC. The highest possible symbol rate for a class of LDCs is called the capacity of that class. It is shown that given K, N, the maximum value of capacity of perfectly smooth LDCs, maximized over all code lengths M, is C* = N(1 + 1/N 1/N2+ · · · 1/NK-1)-1. Furthermore, given K, N, the minimum code length M for which the capacity of a perfectly smooth LDC is C* is shown to be M = NK. Both of these results generalize to a broader class of LDCs, called universal LDCs. The results are then translated into the context of PIRmax, i.e., Private Information Retrieval subject to maximum (rather than average) download cost metric. It is shown that the minimum upload cost of capacity achieving PIRmax schemes is (K - 1) log N. The results also generalize to a variation of the PIR problem, known as Repudiative Information Retrieval (RIR).

We consider a K-user interference network with M states, where each transmitter has up to M messages and over State m, Receiver k wishes to decode the first πk(m) ∈ {1,2, ⋯, M} messages from its desired transmitter. This problem of channel with states models opportunistic communications, where more messages are decoded for better channel states. The first message from each transmitter has the highest priority as it is required to be decoded regardless of the state of the receiver; the second message is opportunistically decoded if the state allows a receiver to decode 2 messages; and the M-th message has the lowest priority as it is decoded if and only if the receiver wishes to decode all M messages. For this interference network with states, we show that if any possible combination of the channel states satisfies a condition under which power control and treating interference as noise (TIN) are sufficient to achieve the entire generalized degrees of freedom (GDoF) region of this channel state by itself, then a simple layered superposition encoding scheme with power control and a successive decoding scheme with TIN achieves the entire GDoF region of the network with M states for all K M messages.

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/ gcd(N, T) where K is the total number of messages in the system and gcd(·, ·) means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as lcm(N - T, T), where lcm(·, ·) 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 lcm(N - T, T).

The two-user computation broadcast problem is introduced as the setting where user 1 wants message W1and has side information W'1, user 2 wants message W2and has side information W2', and (W1, W'1, W2, W'2) may have arbitrary dependencies. The goal is to minimize the entropy H(S) of the broadcast information S that simultaneously satisfies both users' demands. It is shown that H(S) > H(W1|W'1) + H(W2|W'2)-min (I(W1; W2, W'2|W'1), I (W2; W1, W'1|W'2)). Furthermore, for the linear computation broadcast problem, where W1, W'1, W2, W'2are comprised of arbitrary linear combinations of a basis set of independent symbols, the bound is shown to be tight.

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 capacity-achieving 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 a strategic 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 capacity of symmetric private information retrieval (PIR) with N servers and K messages, each coded by an (N, M)-MDS code has been characterized as CMDS-SPIR= 1- M/N . A critical assumption for this result is that the randomness is similarly coded by an (N, M)-MDS code, i.e., the code parameters of the messages and randomness are matched. In this work, we are interested in the mismatched case, and as a preliminary result, we establish the capacity of the mismatched MDS coded symmetric PIR (SPIR) problem under an extreme setting, where the messages are coded by an (N, M)-MDS code and the randomness is replicated (i.e., coded by an (N,1)MDS code). The capacity is shown to be Cmis-MDS-SPIR= (1 - 1/N) · (1+M-1/N (1 + M/N + ⋯ + (M/N)K-2))-1. Interestingly, Cmis-MDS-SPIR> CMDS-SPIR, so mismatched coded randomness (with more redundancy) is strictly beneficial. Further, mismatched SPIR exhibits properties that are similar to PIR.

The topological interference management (TIM) problem studies the degrees of freedom (DoF) of partially- connected interference networks with no channel state information (CSI) at the transmitters except the network topology (i.e., partial connectivity). In this paper, we consider a variant of the TIM problem with uncertainty in network topology, where the channel state with partial connectivity is only known to belong to one of M states at the transmitters. In particular, the transmitter has access to all network topological information over M states, but is unaware of which state it falls in exactly for communication. The receiver at any state is aware of the exact state it falls in besides the network topologies of all states, and wish to recover as much highly-prioritized information at current state as possible. We formulate it as the opportunistic TIM problem with network uncertainty modeled by M state-varying network topologies. To adapt to network topology uncertainty and different message decoding priority, joint encoding and opportunistic decoding are enabled at the transmitters and receivers respectively. Specifically, being aware of all possible network topologies, each transmitter sends a signal jointly encoded from all messages desired over M states, say M distinct messages, and at a certain State m, Receiver k wishes to opportunistically decode the first πk(m)∈ {1,2,...,M} higher-priority messages. Under this opportunistic TIM setting, we construct a multi-state conflict graph to capture the mutual conflict of messages over M states, and characterize the optimal DoF region of two classes of network topologies via polyhedral combinatorics. A remarkable fact is that, under an additional mild monotonous condition, the optimality conditions of orthogonal access and one-to-one interference alignment still apply to TIM with uncertainty in network topology.

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 reading the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization level) is significantly, in fact exponentially, lower than previously believed. More precisely, when K > T/ gcd(N, T) where K is the total number of message in the system and gcd(·,·) means the greatest common divisor, we establish, by providing both a novel code construction and a matching converse, the minimum message size as lcm(N -T, T), where lcm(·,·) 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 lcm(N - T, T).

X-secure and T-private information retrieval (XSTPIR) is a form of private information retrieval where data security is guaranteed against collusion among up to X servers and the user's privacy is guaranteed against collusion among up to T servers. The capacity of XSTPIR is characterized for an arbitrary number of servers N and arbitrary security and privacy thresholds X and T, in the limit as the number of messages K → ∞. Capacity is also characterized for any number of messages if either N = 3, X = T = 1 or if N ≤ X +T. Insights are drawn from these results, about aligning versus decoding noise, dependence of PIR rate on field size, and robustness to symmetric security constraints. In particular, the idea of cross subspace alignment, i.e., introducing a subspace dependence between Reed-Solomon code parameters, emerges as the optimal way to align undesired terms while keeping desired terms resolvable.

We consider the communication scenario where K transmitters are each connected to a common receiver with an orthogonal noiseless link. One of the transmitters has a message for the receiver, who is prohibited from learning anything in the information theoretic sense about which transmitter sends the message (transmitter anonymity is guaranteed). The capacity of anonymous communications is the maximum number of bits of desired information that can be anonymously communicated per bit of total communication. For this anonymous communication problem over a parallel channel with K transmitters and one receiver, we show that the capacity is 1/K, i.e., to communicate 1 bit anonymously, each transmitter must send a 1 bit signal. Furthermore, it is required that each transmitter has at least 1 bit correlated randomness (that is independent of the messages and is not available to the receiver) per message bit and the size of correlated randomness at all K transmitters is at least K - 1 bits per message bit.

Private information retrieval (PIR) is the problem of retrieving, as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other K - 1 messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is 1-1/N regardless of the number of messages K, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least 1/(N -1) bits per desired message bit. Otherwise, if the amount of common randomness is less than 1/(N -1) bits per message bit, then the capacity of SPIR is zero. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.

We introduce the problem of private computation, comprised of N distributed and non-colluding servers, K independent datasets, and a user who wants to compute a function of the datasets privately, i.e., without revealing which function he wants to compute, to any individual server. This private computation problem is a strict generalization of the private information retrieval (PIR) problem, obtained by expanding the PIR message set (which consists of only independent messages) to also include functions of those messages. The capacity of private computation, C, is defined as the maximum number of bits of the desired function that can be retrieved per bit of total download from all servers. We characterize the capacity of private computation, for N servers and K independent datasets that are replicated at each server, when the functions to be computed are arbitrary linear combinations of the datasets. Surprisingly, the capacity, C=(1+1/N+ ⋯ +1/NK-1)-1, matches the capacity of PIR with N servers and K messages. Thus, allowing arbitrary linear computations does not reduce the communication rate compared to pure dataset retrieval. The same insight is shown to hold even for arbitrary non-linear computations when the number of datasets K → ∞.

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 capacity-achieving 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.

We consider the problem of private information retrieval (PIR) with colluding servers and eavesdroppers (abbreviated as ETPIR). The ETPIR problem is comprised of K messages and N servers where each server stores all K messages, a user who wants to retrieve one of the K messages without revealing the desired message index to any set of T colluding servers, and an eavesdropper who can listen to the queries and answers of any E servers but is prevented from learning any information about the messages. The information theoretic capacity of ETPIR is defined to be the maximum number of desired message symbols retrieved privately per information symbol downloaded. We show that the capacity of ETPIR is C = (1 - (E/N))(1 + (T - E/N - E) + · · · + ((T - E/N - E))K-1)-1 when E <; T, and C = (1 - (E/N)) when E ≥ T. To achieve the capacity, the servers need to share a common random variable (independent of the messages), and its size must be at least (E/N) · (1/C) symbols per message symbol. Otherwise, with less amount of shared common randomness, ETPIR is not feasible and the capacity reduces to zero. An interesting observation is that the ETPIR capacity expression takes different forms in two regimes. When E <; T, the capacity equals the inverse of a sum of a geometric series with K terms and decreases with K; this form is typical for capacity expressions of PIR. When E ≥ T, the capacity does not depend on K, a typical form for capacity expressions of SPIR (symmetric PIR, which further requires data-privacy, i.e., the user learns no information about other undesired messages); the capacity does not depend on T either. In addition, the ETPIR capacity result includes multiple previous PIR and SPIR capacity results as special cases.

We introduce the problem of private computation, comprised of N distributed and non-colluding servers, K datasets, and a user who wants to compute a function of the datasets privately, i.e., without revealing which function he wants to compute to any individual server. This private computation problem is a strict generalization of the private information retrieval (PIR) problem, by expanding the PIR message set (which consists of only independent messages) to also include functions of those messages. The capacity of private computation, C, is defined as the maximum number of bits of the desired function that can be retrieved per bit of total download from all servers. We characterize the capacity of an elemental private computation setting, with N = 2 servers and K = 2 datasets that are replicated at each server, for linear computations. Surprisingly, the capacity, C = 2/3, matches the capacity of PIR with N = 2 servers and K = 2 messages. Thus, allowing arbitrary linear computations does not reduce the communication rate compared to pure dataset retrieval. The same insight is shown to hold at the opposite extreme where the number of datasets K → ∞, the number of servers N can be arbitrary, and arbitrary (including non-linear) computations are allowed.

We consider the communication scenario where K transmitters are each connected to a common receiver with an orthogonal noiseless link. One of the transmitters has a message for the receiver, who is prohibited from learning anything in the information theoretic sense about which transmitter sends the message (transmitter anonymity is guaranteed). The capacity of anonymous communications is the maximum number of bits of desired information that can be anonymously communicated per bit of total communication. For this anonymous communication problem over a parallel channel with K transmitters and 1 receiver, we show that the capacity is 1/K, i.e., to communicate 1 bit anonymously, each transmitter must send a 1 bit signal. Further, it is required that each transmitter has at least 1 bit correlated randomness (that is independent of the messages) per message bit and the size of correlated randomness at all K transmitters is at least K - 1 bits per message bit.

We consider the storage-retrieval rate tradeoff in private information retrieval systems using a Shannon-theoretic approach. Our focus is on the canonical two-message two-database case, for which a coding scheme based on random codebook generation, joint typicality encoding, and the binning technique is proposed. It is first shown that when the retrieval rate is kept optimal, the proposed non-linear scheme uses less storage than the optimal linear scheme. Since the other extreme point corresponding to using the minimum storage requires both messages to be retrieved, the performance through space-sharing of the two points can also be achieved. However, using the proposed scheme, further improvement can be achieved over this simple strategy. Although the random-coding based scheme has a diminishing but nonzero probability of error, the coding error can be eliminated if variable-length codes are allowed. Novel outer bounds are finally provided and used to establish the superiority of the non-linear codes over linear codes.

The capacity of symmetric private information retrieval with K messages, N servers (out of which any T may collude) and an omniscient Byzantine adversary (who can corrupt any B answers) is shown to be (1-) T+2B/N [1], under the requirement of zero probability of error. In this work, we show that by weakening the adversary slightly (either providing secret low rate channels between the servers and the user, or limiting the observation of the adversary), and allowing vanishing probability of error, the capacity increases to (1-) T+2B/N.

A (K, N, T, Kc) instance of private information retrieval from MDS coded data with colluding servers (in short, MDS-TPIR), is comprised of K messages and N distributed servers. Each message is separately encoded through a (Kc, N) MDS storage code. A user wishes to retrieve one message, as efficiently as possible, while revealing no information about the desired message index to any colluding set of up to T servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either T or Kcbelongs to {1, N}. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti, and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting (K, N, T, Kc) = (2, 4, 2, 2), which achieves the rate 3/5, exceeding the conjectured capacity, 4/7. Insights from the counterexample lead us to capacity characterizations for various instances of MDS-TPIR, including all cases with (K, N, T, Kc) = (2, N, T, N -1), where N and T can be arbitrary.

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of K messages from N non-communicating replicated databases (each holds all K messages) while keeping the identity of the desired message index a secret from each individual database. The information theoretic capacity of PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. T-private PIR is a generalization of PIR to include the requirement that even if any T of the N databases collude, the identity of the retrieved message remains completely unknown to them. Robust PIR is another generalization that refers to the scenario where we have M ≥ N databases, out of which any M-N may fail to respond. For K messages and M ≥ N databases out of which at least some N must respond, we show that the capacity of T-private and Robust PIR is (1 + T/N + T2/N2+ · · · + TK-1/NK-1)-1. The result includes as special cases the capacity of PIR without robustness (M = N) or T-privacy constraints (T = 1).

Private information retrieval (PIR) is the problem of retrieving one message out of K messages from N noncommunicating replicated databases, where each database stores all K messages, in such a way that each database learns no information about which message is being retrieved. The capacity of PIR is the maximum number of bits of desired information per bit of downloaded information among all PIR schemes. The capacity has recently been characterized for PIR as well as several of its variants. In every case it is assumed that all the queries are generated by the user simultaneously. Here we consider multiround PIR, where the queries in each round are allowed to depend on the answers received in previous rounds. We show that the capacity of multiround PIR is the same as the capacity of single-round PIR. The result is generalized to also include T-privacy constraints. Combined with previous results, this shows that there is no capacity advantage from multiround over single-round schemes, non-linear over linear schemes or from E-error over zero-error schemes. However, we show through an example that there is an advantage in terms of storage overhead. We provide an example of a multiround, non-linear, E-error PIR scheme that requires a strictly smaller storage overhead than the best possible with single-round, linear, zero-error PIR schemes.

The main result of this paper is that an orthogonal access scheme, such as time division multiple access achieves the all-unicast degrees of freedom (DoF) region of the topological interference management problem if and only if the network topology graph is chordal bipartite, i.e., every cycle that can contain a chord, does contain a chord. The all-unicast DoF region includes the DoF region for any arbitrary choice of a unicast message set, so e.g., the results of Maleki and Jafar on the optimality of orthogonal access for the sum-DoF of one-dimensional convex networks are recovered as a special case. The result is also established for the corresponding topological representation of the index coding problem.

An extension of private information retrieval (PIR) with colluding servers is considered. The N servers are partitioned into M disjoint sets, such that collusion can only occur between servers that belong to the same set. Specifically, the m-th set is comprised of Nmservers, of which any Tmcan collude. The capacity of this PIR problem is shown to be C = (1 + (Σm = 1MNm/Tm)-1 + ⋯ + (Σm = 1MNm/Tm)-(κ-1))-1.

A (K, N, T, Kc) instance of the MDS-TPIR problem is comprised of K messages and N distributed servers. Each message is separately encoded through an (N, Kc) MDS storage code. A user wishes to retrieve one message, as efficiently as possible, while revealing no information about the desired message index to any colluding set of up to T servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either T or Kcbelongs to {1, N}. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting (K, N, T, Kc) = (2,4, 2, 2), which achieves the rate 3/5, exceeding the conjectured capacity, 4/7.

A private information retrieval (PIR) scheme is a mechanism that allows a user to retrieve any one out of K messages from N non-communicating replicated databases, each of which stores all K messages, without revealing anything (in the information theoretic sense) about the identity of the desired message index to any individual database. If the size of each message is L bits and the total download required by a PIR scheme from all N databases is D bits, then D is called the download cost and the ratio L/D is called an achievable rate. For fixed K, N ϵ ℕ, the capacity of PIR, denoted by C, is the supremum of achievable rates over all PIR schemes and over all message sizes, and was recently shown to be C = (1+1/N +1/N2+⋯+1/NK-1)-1. In this paper, for arbitrary K and N, we explore the minimum download cost DLacross all PIR schemes (not restricted to linear schemes) for arbitrary message lengths L under arbitrary choices of alphabet (not restricted to finite fields) for the message and download symbols. If the same M-ary alphabet is used for the message and download symbols, then we show that the optimal download cost in M-ary symbols is DL= ⌈L/C⌉. If the message symbols are in M-ary alphabet and the downloaded symbols are in M'-ary alphabet, then we show that the optimal download cost in M'-ary symbols, DLϵ {⌈L'/C⌉, ⌈L'/C⌉-1, ⌈L'/C⌉ - 2}, where L' = ⌈L logM'M⌉, i.e., the optimal download cost is characterized to within two symbols.

In the private information retrieval (PIR) problem, a user wishes to retrieve, as efficiently as possible, one out of K messages from N non-communicating databases (each holds all K messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For K messages and N databases, we show that the PIR capacity is (1+1/N+1/N2+· · ·+1/NK-1)-1. A remarkable feature of the capacity achieving scheme is that if we eliminate any subset of messages (by setting the message symbols to zero), the resulting scheme also achieves the PIR capacity for the remaining subset of messages.

In order to gain new insights into multiple-input- multiple-output (MIMO) interference networks, the optimality of Σk=1KMk/2 (half the cake per user) degrees of freedom is explored for a K-user MIMO interference channel where the cross-channels have arbitrary rank constraints, and the kth transmitter and receiver are equipped with Mkantennas each. The result consolidates and significantly generalizes results from prior studies by Krishnamurthy et al., of rank-deficient interference channels where all users have M antennas; and by Tang et al., of full rank interference channels where the kth user pair has Mkantennas. The broader outcome of this paper is a novel class of replication-based outer bounds for arbitrary rank-constrained MIMO interference networks where replicas of existing users are added as auxiliary users and the network connectivity is chosen to ensure that any achievable scheme for the original network also works in the new network. The replicated network creates a new perspective of the problem, so that even simple arguments such as user cooperation become quite powerful when applied in the replicated network, giving rise to stronger outer bounds, than when applied directly in the original network. Remarkably, the replication-based bounds are broadly applicable not only to MIMO interference channels with arbitrary rank-constraints, but much more broadly, even beyond Gaussian settings.

In the private information retrieval (PIR) problem a user wishes to retrieve, as efficiently as possible, one out of K messages from N non-communicating databases (each holds all K messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For K messages and N databases, we show that the PIR capacity is (1 + 1/N + 1/N2+ ⋯+1/NK-1)-1. A remarkable feature of the capacity achieving scheme is that if it is projected onto any subset of messages by eliminating the remaining messages, it also achieves the PIR capacity for that subset of messages.

Blind interference alignment (BIA) refers to interference alignment schemes that are designed only based on channel coherence pattern knowledge at the transmitters (the “blind” transmitters do not know the exact channel values). Private information retrieval (PIR) refers to the problem where a user retrieves one out of K messages from N non-communicating databases (each holds all K messages) without revealing anything about the identity of the desired message index to any individual database. In this paper, we identify an intriguing connection between PIR and BIA. Inspired by this connection, we characterize the information theoretic optimal download cost of PIR, when we have K = 2 messages and the number of databases, N, is arbitrary.

It has been recently shown by Geng et al. that in a K-user Gaussian interference network, if for each user, the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all signal strengths measured in dB scale), then power control and treating interference as noise (TIN) is sufficient to achieve the entire generalized degrees of freedom (GDoF) region. Motivated by the intuition that the deterministic model of Avestimehr et al. (Avestimehr-Diggavi-Tse deterministic model) is particularly suited for exploring the optimality of TIN, the results of Geng et al. are first re-visited under the ADT deterministic model, and are shown to directly translate between the Gaussian and deterministic settings. Next, we focus on the extension of these results to parallel interference networks, from a sum-capacity/sum-GDoF perspective. To this end, we interpret the explicit characterization of the sum capacity/sum GDoF of a TIN optimal network (without parallel channels) as a minimum weighted matching problem in combinatorial optimization, and obtain a simple characterization in terms of a partition of the interference network into vertex-disjoint cycles. Aided by insights from the cyclic partition, the sum-capacity optimality of TIN for K-user parallel interference networks is characterized for the ADT deterministic model, leading ultimately to the corresponding GDoF results for the Gaussian setting. In both the cases, subject to a mild invertibility condition, the optimality of TIN is shown to extend to parallel networks in a separable fashion.

In this paper, we propose a novel “genie chains” approach to obtain information theoretic degrees of freedom (DoF) outer bounds for MIMO wireless interference networks. This new approach creates a chain of mappings from genie signals provided to a receiver to the exposed signal spaces at that receiver, and then the exposed signal spaces serve as the genie signals for the next receiver in the chain subject to certain linear independence requirements. Our approach essentially converts an information theoretic DoF outer bound problem into a linear algebra problem. Several applications of the genie chains approach are presented.

By introducing a novel outer bound, we find Σk=1kMk/2 degrees of freedom (half the cake per user) for a K-user multiple-inputmultiple-output (MIMO) interference channel (IC) where the cross-channels have arbitrary rank constraints, and the kthtransmitter and receiver are equipped with Mkantennas each. The result consolidates and significantly generalizes results from prior studies by Krishnamurthy et al., of rank-deficient interference channels where all users have M antennas; and by Tang et al., of full rank interference channels where the kthuser pair has Mkantennas.

It has been shown recently by Sun et al. that in a K user parallel Gaussian interference network, if over each sub-channel, for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all signal strengths measured in dB scale), then separate coding over each sub-channel and treating interference as noise (TIN) is sufficient to achieve the sum generalized degrees of freedom (GDoF), subject to a mild invertibility condition [1]. In this work, we show that the weighted sum GDoF is similarly separable, i.e., separate coding and TIN is sufficient to achieve the weighted sum GDoF, subject to a similar mild invertibility condition. This is proved by translating the weighted GDoF optimization problem to the sum GDoF problem of a class of compound parallel Gaussian interference networks, giving rise to new weighted GDoF outer bounds that are strictly stronger than what is implied by the sum GDoF bounds obtained previously.

In a K-user Gaussian interference channel, it has been shown that if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in decibel scale), then treating interference as noise (TIN) is optimal from the perspective of generalized degrees of freedom (GDoF) and achieves the entire channel capacity region to within a constant gap. In this paper, we show that for such TINoptimal interference channels, even if the message set is expanded to include an independent message from each transmitter to each receiver, operating the new channel as the original interference channel and treating interference as noise is still optimal for the sum capacity up to a constant gap. Furthermore, we extend the result to the sum-GDoF optimality of TIN in the general setting of X channels with arbitrary numbers of transmitters and receivers.

An interference alignment perspective is used to identify the simplest instances (minimum possible number of edges in the alignment graph, not more than 2 interfering messages at any destination) of index coding problems where non-Shannon information inequalities are necessary for capacity characterization. In particular, this includes the first known example of a multiple unicast (one destination per message) index coding problem where non-Shannon information inequalities are shown to be necessary. The simplest multiple unicast example has 7 edges in the alignment graph and 11 messages. The simplest multiple groupcast (multiple destinations per message) example has 6 edges in the alignment graph, 6 messages, and 10 receivers. For both the simplest multiple unicast and multiple groupcast instances, the best outer bound based on only Shannon inequalities is 2/5, which is tightened to 11/28 by the use of the Zhang-Yeung non-Shannon type information inequality, and the linear capacity is shown to be 5/13 using the Ingleton inequality. Conversely, identifying the minimal challenging aspects of the index coding problem allows an expansion of the class of solved index coding problems up to (but not including) these instances.

We study the degrees of freedom (DoF) of the layered 2 × 2 × 2 multiple-input-multiple-output (MIMO) interference channel where each node is equipped with arbitrary number of antennas, the channels between the nodes have arbitrary rank constraints, and subject to the rank-constraints the channel coefficients can take arbitrary values. The DoF outer bounds reveal a fundamental rank-matching phenomenon, reminiscent of impedance matching in circuit theory. It is well known that the maximum power transfer in a circuit is achieved not for the maximum or minimum load impedance but for the load impedance that matches the source impedance. Similarly, the maximum DoF in the rank-constrained 2 × 2 × 2 MIMO interference network is achieved not for the maximum or minimum ranks of the destination hop, but when the ranks of the destination hop match the ranks of the source hop. In fact, for mismatched settings of interest, the outer bounds identify a DoF loss penalty that is precisely equal to the rank-mismatch between the two hops. For symmetric settings, we also provide achievability results to show that along with the min-cut max-flow bounds, the rank-mismatch bounds are the best possible, i.e., they hold for all channels that satisfy the rank-constraints and are tight for almost all channels that satisfy the rank-constraints. Limited extensions-from sum-DoF to DoF region, from 2 unicasts to X message sets, from 2 hops to more than 2 hops and from 2 nodes per layer to more than 2 nodes per layer-are considered to illustrate how the insights generalize beyond the elemental 2 × 2 × 2 channel model.

In a K-user Gaussian interference channel, it has been shown that if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in dB scale), then treating interference as noise (TIN) is optimal from the perspective of generalized degrees-of-freedom (GDoF) and achieves the entire channel capacity region to within a constant gap. In this work, we show that for such TIN-optimal interference channels, even if the message set is expanded to include an independent message from each transmitter to each receiver, operating the new channel as the original interference channel and treating interference as noise is still optimal for the sum capacity up to a constant gap.

It has been shown recently by Geng et al. that in a K user Gaussian interference network, if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all signal strengths measured in dB scale), then power control and treating interference as noise (TIN) is sufficient to achieve the entire generalized degrees of freedom (GDoF) region. Motivated by the intuition that the deterministic model of Avestimehr et al. (ADT deterministic model) is particularly suited for exploring the optimality of TIN, the results of Geng et al. are first re-visited under the ADT deterministic model, and corresponding TIN optimality results are obtained. Next, we focus on the extension of these results to ADT deterministic parallel interference networks, from a sum-capacity perspective. To this end, we interpret the explicit characterization of the sum-capacity of a TIN optimal network (without parallel channels) as a minimum weighted matching problem in combinatorial optimization, and obtain a simple characterization in terms of a partition of the interference network into vertex-disjoint cycles. Aided by insights from the cyclic partition, the sum-capacity optimality of TIN for K user parallel interference networks is characterized for the ADT deterministic model. Subject to a mild invertibility condition the optimality of TIN is shown to extend to parallel networks in a separable fashion.

The topological interference management problem refers to the study of the DoF of partially connected wireless communication networks with no channel state information at the transmitters (no CSIT) beyond the network topology, i.e., a knowledge of which channel coefficients are non-zero. While the problem is originally studied with single input sources and single output destinations (SISO), in this work we explore the implications of multiple inputs and multiple outputs (MIMO), highlighting fundamental differences and new phenomena.

The topological interference management problem refers to the study of the capacity of partially connected linear (wired and wireless) communication networks with no channel state information at the transmitters (no CSIT) beyond the network topology, i.e., a knowledge of which channel coefficients are zero (weaker than the noise floor in the wireless case). While the problem is originally studied with fixed topology, in this work we explore the implications of varying connectivity, through a series of simple and conceptually representative examples. Specifically, we highlight the synergistic benefits of coding across alternating topologies.

The robust principles of treating interference as noise (TIN) when it is sufficiently weak, and avoiding it when it is not, form the background for this work. Combining TIN with the topological interference management (TIM) framework that identifies optimal interference avoidance schemes, a baseline TIM-TIN approach is proposed which decomposes a network into TIN and TIM components, allocates the signal power levels to each user in the TIN component, allocates signal vector space dimensions to each user in the TIM component, and guarantees that the product of the two is an achievable number of signal dimensions available to each user in the original network.

We show that an M×N user MIMO X network with A antennas at each node has A(MN/(M+N-1)) degrees of freedom (DoF), thus resolving in this case a discrepancy between the spatial scale invariance conjecture (scaling the number of antennas at each node by a constant factor will scale the total DoF by the same factor) and a decomposability property of overconstrained wireless networks. While the best previously known general DoF outer bound is consistent with the spatial invariance conjecture, the best previously known general DoF inner bound, inspired by the K user MIMO interference channel, was based on the decomposition of every transmitter and receiver into multiple single antenna nodes, transforming the network into an AM×AN user SISO X network. While such a decomposition is DoF optimal for the K user MIMO interference channel, a gap remained between the best inner and outer bounds for the MIMO X channel. Here we close this gap with the new insight that the MIMO X network is only one-sided decomposable, i.e., either all the transmitters or all the receivers (but not both) can be decomposed by splitting multiple antenna nodes into multiple single antenna nodes without loss of DoF. The result is extended to SIMO and MISO X networks as well and in each case the DoF results satisfy the spatial scale invariance property.

We show that an M × N user MIMO X network with A antennas at each node has A (MN/M+N-1) degrees of freedom (DoF), thus settling the spatial scale invariance conjecture (scaling the number of antennas at each node by a constant factor will scale the total DoF by the same factor) for this class of networks. The previously known best general DoF inner bound, inspired by the K user interference channel, was based on the decomposition of every transmitter and receiver into multiple single antenna nodes, transforming the network into an AM × AN user SISO X network. While such a decomposition is DoF optimal for the K user interference channel, a gap remained between the best inner and outer bound for the MIMO X channel. Here we close this gap with the new insight that the MIMO X network is only one-sided decomposable, i.e., either all the transmitters or all the receivers (but not both) can be decomposed by splitting multiple antenna nodes into multiple single antenna nodes without loss of DoF. The result is extended to SIMO and MISO X networks as well and in each case the DoF results satisfy the spatial scale invariance property. In addition, the feasibility of linear interference alignment is investigated based only on spatial beamforming without symbol extensions. Similar to MIMO interference networks, we show that when the problem is improper, it is infeasible.

We explore the degrees of freedom (DoF) of the K >; 3 user MT× MRMIMO Gaussian interference channel where each transmitter is equipped with MTand each receiver is equipped with MRantennas. Expressing the DoF characterization as a function of the ratio γ = M/N, where M = min(MT, MR) and N = max(MT, MR), we find that when γ ≤ γo= K-1/K(K-2) = γo, the DoF value per user is piecewise linear depending on M and N alternately, similar to the DoF characterization for K = 3 which has been previously obtained. The regime γ >; γo, which is the dominant regime for K >; 3 users and is not encountered in the K = 3 user setting, is the main focus of this paper. Our DoF results in this regime are obtained through a novel “genie chains” approach, which is the main contribution of this work. It is a chain of mappings from genie signals provided to a receiver to the exposed signal spaces at that receiver, which then serve as the genie signals for the next receiver in the chain, until an acceptable genie with the required number of dimensions is obtained, essentially converting an information theoretic problem into a linear algebra problem.