The multiaccess coded caching (MACC) system, as formulated by Hachem {\it et al.}, consists of a central server with a library of $N$ files, connected to $K$ cache-less users via an error-free shared link, and $K$ cache nodes, each equipped with cache memory of size $M$ files. Each user can access $L$ neighboring cache nodes under a cyclic wrap-around topology. Most existing studies operate under the strong assumption that users can retrieve content from their connected cache nodes at no communication cost. In practice, each user retrieves content from its $L$ different connected cache nodes at varying costs. Additionally, the server also incurs certain costs to transmit the content to the users. In this paper, we focus on a cost-aware MACC system and aim to minimize the total system cost, which includes cache-access costs and broadcast costs. Firstly, we propose a novel coded caching framework based on superposition coding, where the MACC schemes of Cheng \textit{et al.} are layered. Then, a cost-aware optimization problem is derived that optimizes cache placement and minimizes system cost. By identifying a sparsity property of the optimal solution, we propose a structure-aware algorithm with reduced complexity. Simulation results demonstrate that our proposed scheme consistently outperforms the scheme of Cheng {\it et al.} in scenarios with heterogeneous retrieval costs.

We consider a $(G,L,K,M,N)$ cache-aided multiple-input multiple-output (MIMO) network, where a server equipped with $L$ antennas and a library of $N$ equal-size files communicates with $K$ users, each equipped with $G$ antennas and a cache of size $M$ files, over a wireless interference channel. Each user requests an arbitrary file from the library. The goal is to design coded caching schemes that simultaneously achieve the maximum sum degrees of freedom (sum-DoF) and low subpacketization. In this paper, we first introduce a unified combinatorial structure, termed the MIMO placement delivery array (MIMO-PDA), which characterizes uncoded placement and one-shot zero-forcing delivery. By analyzing the combinatorial properties of MIMO-PDAs, we derive a sum-DoF upper bound of $\min\{KG, Gt+G\lceil L/G \rceil\}$, where $t=KM/N$, which coincides with the optimal DoF characterization in prior work by Tehrani \emph{et al.}. Based on this upper bound, we present two novel constructions of MIMO-PDAs that achieve the maximum sum-DoF. The first construction achieves linear subpacketization under stringent parameter constraints, while the second achieves ordered exponential subpacketization under substantially milder constraints. Theoretical analysis and numerical comparisons demonstrate that the second construction exponentially reduces subpacketization compared to existing schemes while preserving the maximum sum-DoF.

We consider the $(K,L,M,N)$ multi-access coded caching system introduced by Hachem et al., which consists of a central server with $N$ files and $K$ cache nodes, each of memory size $M$, where each user can access $L$ cache nodes in a cyclic wrap-around fashion. At present, several existing schemes achieve competitive transmission performance, but their subpacketization levels grow exponentially with the number of users. In contrast, schemes with linear or polynomial subpacketization always incur higher transmission loads. We aim to design a multi-access coded caching scheme with linear subpacketization $F$ while maintaining low transmission load. Recently, Cheng et al. proposed a construction framework for coded caching schemes with linear subpacketization (i.e., $F=K$) called non-half-sum disjoint packing (NHSDP). Inspired by this structure, we introduce a novel combinatorial structure named cyclic multi-access non-half-sum disjoint packing (CMA-NHSDP) by extending NHSDP to MACC system. By constructing CMA-NHSDP, we obtain a new class of multi-access coded caching schemes. Theoretical and numerical analyses show that our scheme achieves lower transmission loads than some existing schemes with linear subpacketization. Moreover, the proposed schemes achieves lower transmission load compared to existing schemes with exponential subpacketization in some case.

This paper studies the information theoretic secure aggregation problem in a three-layer hierarchical network with arbitrary heterogeneous data assignment, where clustered users communicate with an aggregation server through an intermediate layer of relays. We consider a more general setting with arbitrary heterogeneous data assignment across users, where `arbitrary' means that the data assignment is given in advance and `heterogeneous' means that the users may hold different numbers of datasets. Each user locally computes the partially aggregated gradients as its input based on the assigned datasets and transmits masked input to its associated relay. The relays then forward the aggregated messages to the server, which aims to recover the sum of the gradients. In this process, while some users may drop out unpredictably, the server needs to correctly recover the desired aggregation from the surviving users. Moreover, the server or any relay may collude with a subset of users. We impose the following security constraints: (i) server security, requiring the server to learn only the sum of gradients without gaining any additional information about individual inputs; and (ii) relay security, ensuring that each relay learns nothing about users' inputs. Under these constraints, we propose an aggregation scheme that guarantees information theoretic security and achieves the optimal two-layer communication loads.

Coded caching is recognized as an effective method for alleviating network congestion during peak periods by leveraging local caching and coded multicasting gains. The key challenge in designing coded caching schemes lies in simultaneously achieving low subpacketization and low transmission load. Most existing schemes require exponential or polynomial subpacketization levels, while some linear subpacketization schemes often result in excessive transmission load. Recently, Cheng et al. proposed a construction framework for linear coded caching schemes called Non-Half-Sum Disjoint Packing (NHSDP), where the subpacketization equals the number of users $K$. This paper introduces a novel combinatorial structure, termed the Non-Half-Sum Latin Rectangle (NHSLR), which extends the framework of linear coded caching schemes from $F=K$ (i.e., the construction via NHSDP) to a broader scenario with $F=\mathcal{O}(K)$. By constructing NHSLR, we have obtained a new class of coded caching schemes that achieves linearly scalable subpacketization, while further reducing the transmission load compared with the NHSDP scheme. Theoretical and numerical analyses demonstrate that the proposed schemes not only achieves lower transmission load than existing linear subpacketization schemes but also approaches the performance of certain exponential subpacketization schemes.

This paper investigates the fundamental limits and optimal signal distribution design for Integrated Sensing and Communication (ISAC) systems operating under strictly noncoherent conditions. Unlike conventional coherent frameworks that rely on perfect channel state information, we consider a block-fading MIMO channel where the channel realizations are unknown to both the transmitter and the receiver. We adopt a realization-wise perspective to characterize the noncoherent performance tradeoff across different signal-to-noise ratio (SNR) regimes. In the high-SNR regime, we derive a lower bound for the noncoherent mutual information and define a metric, termed sensing-induced rate loss, to quantify the communication penalty incurred by sensing-oriented beamforming. We then employ a projected gradient algorithm to optimize the spatial power allocation, balancing the conflict between the unitary space-time modulation-based structure for communication and the task-oriented spatial power allocation for sensing. Conversely, in the low-SNR regime, we perform a first-order asymptotic analysis of the ergodic minimum mean squared error (EMMSE). Our theoretical derivation reveals a fundamental synergy: the sensing-optimal strategy collapses to a rank-one transmission along the dominant eigenvector of the target response, which incurs no first-order communication loss in the low-SNR regime. This result demonstrates that the conflicting tradeoff observed at high SNR vanishes asymptotically at low SNR, enabling perfect alignment between sensing and communication objectives.

This paper studies the multi-access coded caching (MACC) problem with arbitrary user-cache access topology, which extends existing MACC models that rely on highly structured and combinatorially designed topologies. We consider a MACC system consisting of a single server, $Λ$ cache-nodes, and $K$ user-nodes. The server stores $N$ equal-size files, each cache-node has a storage capacity of $M$ files, and each user-node $k\in[K]$ can access an arbitrary subset of cache-nodes $\mathcal{A}_k\subseteq[Λ]$ and retrieve the cached content stored in cache-nodes $\mathcal{A}_k$. The objective is to design a universal framework for the MACC delivery problem. Decoding conflicts among the requested packets are captured by a conflict graph, and the design of the delivery is reduced to a graph coloring problem, where achieving a lower transmission load corresponds to coloring the graph using fewer colors. Under this formulation, the classical DSatur algorithm achieves a transmission load close to the index-coding (IC) converse bound, thereby providing a practical benchmark. However, its computational complexity becomes prohibitive for large-scale graphs. To overcome this limitation, we develop a learning-driven approach using graph neural networks (GNNs) that efficiently constructs coded multicast transmissions with performance close to the theoretical bounds and generalizes across different user-cache access topologies and numbers of users. In addition, we extend the IC converse bound to MACC systems with arbitrary access topology and propose a low-complexity greedy approximation that closely matches the IC converse bound. Numerical results demonstrate that the proposed approach achieves performance close to the DSatur algorithm and the IC converse bound, while significantly reducing computational complexity, making it well-suited for large-scale MACC systems.

This paper considers a new secure gradient coding problem with uncoded groupwise keys, formalized as a (K, N, N_r, M, S) secure gradient coding model, where a user aims to compute the sum of the gradients from K datasets with the assistance of N distributed servers. We consider arbitrary heterogeneous data assignment, where each dataset is assigned to at least M servers. The user should recover the sum of gradients from the transmissions of any N_r servers. The security constraint guarantees that even if the user receives the transmitted messages from all servers, it cannot obtain any other information about the datasets except the sum of gradients. Compared to existing secure gradient coding works, we introduce a practical constraint on secret keys, namely uncoded groupwise keys, where the keys are mutually independent and each key is shared by precisely S servers. An achievable secure gradient coding scheme with uncoded groupwise keys is proposed, which is then proven to be optimal if S > M and to be order optimal within a factor of 2 otherwise.

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.

Distributed linearly separable computation is a fundamental problem in large-scale distributed systems, requiring the computation of linearly separable functions over different datasets across distributed workers. This paper studies a heterogeneous distributed linearly separable computation problem, including one master and N distributed workers. The linearly separable task function involves Kc linear combinations of K messages, where each message is a function of one dataset. Distinguished from the existing homogeneous settings that assume each worker holds the same number of datasets, where the data assignment is carefully designed and controlled by the data center (e.g., the cyclic assignment), we consider a more general setting with arbitrary heterogeneous data assignment across workers, where `arbitrary' means that the data assignment is given in advance and `heterogeneous' means that the workers may hold different numbers of datasets. Our objective is to characterize the fundamental tradeoff between the computable dimension of the task function and the communication cost under arbitrary heterogeneous data assignment. Under the constraint of integer communication costs, for arbitrary heterogeneous data assignment, we propose a universal computing scheme and a universal converse bound by characterizing the structure of data assignment, where they coincide under some parameter regimes. We then extend the proposed computing scheme and converse bound to the case of fractional communication costs.

In the $(L,K,M,N)$ cache-aided multiple-input single-output (MISO) broadcast channel (BC) system, the server is equipped with $L$ antennas and communicates with $K$ single-antenna users through a wireless broadcast channel where the server has a library containing $N$ files, and each user is equipped with a cache of size $M$ files. Under the constraints of uncoded placement and one-shot linear delivery strategies, many schemes achieve the maximum sum Degree-of-Freedom (sum-DoF). However, for general parameters $L$, $M$, and $N$, their subpacketizations increase exponentially with the number of users. We aim to design a MISO coded caching scheme that achieves a large sum-DoF with low subpacketization $F$. An interesting combinatorial structure, called the multiple-antenna placement delivery array (MAPDA), can be used to generate MISO coded caching schemes under these two strategies; moreover, all existing schemes with these strategies can be represented by the corresponding MAPDAs. In this paper, we study the case with $F=K$ (i.e., $F$ grows linearly with $K$) by investigating MAPDAs. Specifically, based on the framework of Latin squares, we transform the design of MAPDA with $F=K$ into the construction of a combinatorial structure called the $L$-half-sum disjoint packing (HSDP). It is worth noting that a $1$-HSDP is exactly the concept of NHSDP, which is used to generate the shared-link coded caching scheme with $F=K$. By constructing $L$-HSDPs, we obtain a class of new schemes with $F=K$. Finally, theoretical and numerical analyses show that our $L$-HSDP schemes significantly reduce subpacketization compared to existing schemes with exponential subpacketization, while only slightly sacrificing sum-DoF, and achieve both a higher sum-DoF and lower subpacketization than the existing schemes with linear subpacketization.

To overcome the 180° coverage limitation of conventional reflective Reconfigurable Intelligent Surfaces (RIS) in challenging Non-Line-of-Sight (NLoS) environments like underground coal mines, this paper proposes the deployment of a Simultaneously Transmitting and Reflecting RIS (STAR-RIS). The STAR-RIS achieves full 360° signal coverage, effectively addressing the spatial constraints of complex tunnel topologies. Furthermore, we introduce a “Position-Flexible” approach, where the entire panel’s location is dynamically adjusted to maximize the average sum-rate across wideband OFDM subcarriers. By exploiting frequency diversity, the proposed system effectively combats the severe frequency-selective fading inherent in multipath-rich mine tunnels. This holistic movement strategy is specifically designed to enhance hardware reliability in harsh, dust-prone mining conditions by mitigating failure risks associated with complex element-wise mechanical actuation. We formulate a joint optimization problem involving broadband active beamforming, passive phase shifts, and the STAR-RIS coordinates. To solve this non-convex problem, an Alternating Optimization (AO) algorithm is developed. Specifically, the STAR-RIS location is optimized via Projected Gradient Ascent (PGA), while the beamforming and phase-shift coefficients are refined using Successive Convex Approximation (SCA) and Semidefinite Relaxation (SDR). Simulation results confirm that the proposed system significantly improves the sum rate, validating its effectiveness for robust underground wireless connectivity.

This paper proposes the Low Upload and Storage Cost (LUSC) scheme, a coded distributed computing (CDC) approach that accelerates Convolutional Neural Network (CNN) inference on resource-constrained edge devices. LUSC introduces a new encoding and decoding mechanism that exploits the periodicity and evenness of cosine functions, reducing communication and storage overhead while ensuring numerical stability. Orthogonal decoding matrices derived from this cosine-based design guarantee stable inversion and preserve numerical precision. By leveraging the duality property of cosine functions, LUSC reduces the number of workers required for decoding, enabling finer-grained task decomposition and further lowering upload and storage costs. When combined with a spatial and channel grid partition (SCGP) strategy, LUSC (including other matrix-multiplication-based CDC schemes) can be applied to convolutions, accelerating CNN inference while maintaining resilience to stragglers. Experimental results demonstrate that LUSC consistently outperforms existing numerically stable CDC schemes, providing efficient inference with reduced communication and storage costs and maintaining robustness under straggler conditions.

The Fluid Antenna System (FAS) overcomes the spatial degree-of-freedom limitations of conventional static antenna arrays in wireless communications.This capability critically depends on acquiring full Channel State Information across all accessible ports. Existing studies focus exclusively on narrowband FAS, performing channel estimation solely in the spatial domain. This work proposes a channel estimation and spatial equalization framework for wideband FAS, revealing for the first time an inherent group-sparse structure in aperture-limited FAS channels. First, we establish a group-sparse recovery framework for space-frequency characteristics in FAS, formally characterizing leakage-induced sparsity degradation from limited aperture and bandwidth as a structured group-sparsity problem. By deriving dictionary-adapted group restricted isometry property, we prove tight recovery bounds for a convex ℓ1/ℓ2-mixed norm optimization formulation that preserves leakage-aware sparsity patterns. Second, we develop a descending correlation group orthogonal matching pursuit algorithm that systematically relaxes leakage constraints to reduce subcoherence. This approach enables FSC recovery with accelerated convergence and superior performance compared to conventional compressive sensing methods like OMP or GOMP. Third, we formulate spatial equalization as a mixed-integer linear programming problem, complement this with a greedy algorithm maintaining near-optimal performance. Simulation results demonstrate the proposed channel estimation algorithm effectively resolves energy misallocation and enables recovery of weak details, achieving superior recovery accuracy and convergence rate. The SE framework suppresses deep fading phenomena and largely reduces time consumption overhead while maintaining equivalent link reliability.

Integrated sensing and communication (ISAC) systems provide significant enhancements in performance and resource efficiency compared to individual sensing and communication systems, primarily attributed to the collaborative use of wireless resources, radio waveforms, and hardware platforms. This paper focuses on the bistatic ISAC systems with separated multi-receiver and one sensor. Compared to a monostatic ISAC system, the main challenge in the bistatic setting is that the information messages are unknown to the sensor and therefore they are seen as interference, while the channel between the transmitters and the sensor is unknown to the transmitters. In order to mitigate the interference at the sensor while maximizing the communication degree of freedom, we introduce two strategies, namely, blind interference alignment and topological interference management. Although well-known in the context of Gaussian interference channels, these strategies are novel in the context of bistatic ISAC. For the bistatic ISAC models with heterogeneous coherence time or with heterogeneous connectivity, the achieved ISAC tradeoff points in terms of communication and sensing degrees of freedom are characterized. In particular, we show that the new tradeoff outperforms the time-sharing between the sensing-only and the communication-only schemes. Simulation results demonstrate that the proposed schemes significantly improve the channel estimation error for the sensing task, compared to treating interference as noise at the sensor and successive interference cancellation.

In decentralized federated learning (FL), multiple clients collaboratively learn a shared machine learning (ML) model by leveraging their privately held datasets distributed across the network, through interactive exchange of intermediate model updates. To ensure data security, cryptographic techniques are commonly employed to protect model updates during aggregation. Despite growing interest in secure aggregation, existing works predominantly focus on protocol design and computational guarantees, with limited understanding of the fundamental information-theoretic limits of such systems. Moreover, optimal bounds on communication and key usage remain unknown in decentralized settings, where no central aggregator is available. Motivated by these gaps, we study the problem of decentralized secure aggregation (DSA) from an information-theoretic perspective. Specifically, we consider a network ofKfully-connected users, each holding a private input—an abstraction of local training data—who aim to securely compute the sum of all inputs. The security constraint requires that no user learns anything beyond the input sum, even when colluding with up toTother users. We characterize the optimal rate region, which specifies the minimum achievable communication and secret key rates for DSA. In particular, we show that to securely compute one symbol of the desired input sum, each user must (i) transmit at least one symbol to others, (ii) hold at least one symbol of secret key, and (iii) all users must collectively hold no fewer thanK−1independent key symbols. Our results establish the fundamental performance limits of DSA, providing insights for the design of provably secure and communication-efficient protocols in decentralized learning.

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.

Coded caching is a promising technique for effectively reducing peak traffic by using local caches and the multicast gains generated by these local caches. Coded caching schemes have been widely investigated, following the seminal work of Maddah-Ali and Niesen. Explicit coding constructions have been proposed for a variety of network topologies with information-theoretically optimal or near-optimal transmission loadR. An important parameter in these constructions is the subpacketizationF, i.e., the number of subpackets that each content file needs to be divided into. In particular, the original scheme of Maddah-Ali and Niesen as well as several other variants requireFto grow exponentially with the number of usersK. In practice, files have finite size and too largeFyields impractically small subpackets. Therefore, it is important to design coded caching schemes withFandRas small as possible. At present, the few known schemes with subpacketization linear inKachieve large load. In this paper, we consider the linear scaling regimeF = O(K)and design schemes with a lower transmission loadR. Specifically, we first introduce a new combinatorial structure called non-half-sum disjoint packing (NHSDP) which can be used to generate a coded caching scheme withK = O(F). A class of new schemes is then obtained by constructing NHSDP. Theoretical analysis and numerical results demonstrate that (i) in comparison to existing schemes with linear subpacketization, the proposed scheme achieves a lower load; (ii) the proposed scheme also attains a lower load than some existing schemes with polynomial subpacketization in some cases; and (iii) the proposed scheme achieves load values comparable to those of existing schemes with exponential subpacketization in some cases. Furthermore, the newly introduced concept of NHSDP is closely related to classical combinatorial structures, including cyclic difference packings (CDP), non-three-term arithmetic progressions (NTAP), and perfect hash families (PHF). These relationships underscore the significance of NHSDP as a combinatorial structure of independent interest in the field of combinatorial design, even beyond its application to coded caching.

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.

Integrated sensing and communication (ISAC) systems provide significant enhancements in performance and resource efficiency compared to individual sensing and communication systems, primarily attributed to the collaborative use of wireless resources, radio waveforms, and hardware platforms. The performance limits of a system are crucial for guiding its design; however, the performance limits of ISAC systems remain an open question. This paper focuses on the bistatic ISAC systems with dispersed multi-receivers and one sensor. Compared to the monostatic ISAC systems, the main challenge is that that the communication messages are unknown to the sensor and thus become its interference, while the channel information between the transmitters and the sensor is unknown to the transmitters. In order to mitigate the interference at the sensor while maximizing the communication degree of freedom, we introduce the blind interference alignment strategy for various bistatic ISAC settings, including interference channels, MU-MISO channels, and MU-MIMO channels. Under each of such system, the achieved ISAC tradeoff points by the proposed schemes in terms of communication and sensing degrees of freedom are characterized, which outperforms the time-sharing between the two extreme sensing-optimal and communication-optimal points. Simulation results also demonstrate that the proposed schemes significantly improve on the ISAC performance compared to treating interference as noise at the sensor.

Coded caching is a promising technique to effectively reduce peak traffic by using local caches and the multicast gains generated by these local caches. We aim to design a coded caching scheme to minimize subpacketization$F$and transmission load$R$, since these two metrics are key measures of scheme implementation complexity and transmission efficiency, respectively. In this paper, we focus on studying linear subpacketization coded caching schemes with low transmission load. We first introduce a new combinatorial structure, called non-half-sum disjoint packing (NHSDP), which can be used to construct coded caching schemes where the number of users is equal to the subpacketization, i.e.$K=F$. Then by constructing NHSDPs, we obtain a new class of coded caching schemes which achieve lower load compared to the existing schemes with linear subpacketization and even some of the existing schemes with polynomial subpacketization. Moreover, the novel concept of NHSDPs is closely related to the classical combinatorial structures, including cyclic difference packing, non-three-term arithmetic progressions, and perfect hash family.

In this paper, we study gradient coding in a hierarchical setting, where there are intermediate nodes between the server and the workers. This structure reduces the bandwidth requirements at the server, which is a significant bottleneck in conventional gradient coding systems. In this paper, the intermediate nodes, referred to as relays, process the data received from workers and send the results to the server for the final gradient computation. Our main contribution is deriving the optimal communication-computation trade-off by designing a linear coding scheme inspired by coded computing techniques, considering straggling and adversarial nodes among both relays and workers. The processing of the data in the relays makes it possible to achieve both the relay-to-server and the worker-to-relay communication loads simultaneously optimal with regard to the computation load.

This paper studies the ergodic achievable rates of a primitive Gaussian diamond channel with Rayleigh fading. The system is modeled as a two-hop relay channel where a single user communicates with a central processor (CP) through two relays. These relays are agnostic to the user's codebooks and are considered “primitive” because the fronthaul links are error-free but have limited capacity. In this setup, the channel state information (CSI) is assumed to be available only at the relays and not at the CP. Despite the simplicity of this configuration, deriving an accurate characterization of the ergodic capacity is surprisingly challenging. To address this, we first establish an analytical rate upper bound, assuming that the relays can cooperate and that the CP has access to the CSI as well. In order to obtain lower bounds, we resort to specific analytically/numerically tractable achievability strategies. When designing such strategies, we need to take into account that the CP has no CSI and that each relay has only statistical knowledge of the CSI other relay. Under these constraints, we propose two achievable schemes employing different estimation and compression methods at relays. Simulation results show that these schemes achieve performance close to the derived upper bound over a wide range of system parameters.

This paper considers a multi-message secure aggregation with demand privacy problem, in which a server aims to compute$K_{c} \geq 1$linear combinations of local inputs from$K$distributed and non-colluding users. The problem addresses two tasks: (1) security, ensuring that the server can only obtain the desired linear combinations without any else information about the users' inputs, and (2) privacy, preventing users from learning about the server's computation task. In addition, the effect of user dropouts is considered, where at most$K-U$users can drop out and the identity of these users cannot be predicted in advance. We propose two schemes for$\mathrm{K}_{\mathrm{c}}=1$and$2 \leq \mathrm{K}_{\mathrm{c}}<\mathrm{U}$, respectively. For$\mathrm{K}_{\mathrm{c}}=1$, we introduce multiplicative encryption of the server's demand using a random variable, where users share coded keys offline and transmit masked models in the first round, followed by aggregated coded keys in the second round for task recovery. For$2 \leq \mathrm{K}_{\mathrm{c}}<\mathrm{U}$, we use robust symmetric private computation to recover linear combinations of keys in the second round. The objective is to minimize the number of symbols sent by each user during the two rounds. Our proposed schemes have achieved the optimal rate region when$\mathrm{K}_{\mathrm{c}}=1$and the order optimal rate (within 2) when$2 \leq \mathrm{K}_{\mathrm{c}}<\mathrm{U}$.

Gradient coding enables a user node to efficiently aggregate gradients computed by server nodes from local datasets, achieving low communication costs while ensuring resilience against straggling servers. This paper considers the secure gradient coding problem, where a user aims to compute the sum of the gradients from K datasets with the assistance of$N$distributed servers. The user is required to recover the sum of gradients from the transmissions of any$\mathrm{N}_{\mathrm{r}}$servers, with each dataset assigned to$N-N_{r}+m$servers. The security constraint guarantees that even if the user receives transmissions from all servers, no additional information about the datasets can be obtained beyond the sum of gradients. It has been shown in the literature that the security constraint does not increase the optimal communication cost of the gradient coding problem, provided that enough source keys are shared among the servers. However, the minimum required source key size to ensure security while achieving the optimal communication cost has been studied only for the case$m=1$. In this paper, we focus on the more general case$m \geq 1$and aim to characterize the minimum required source key size for this purpose. A new information-theoretic converse bound on the source key size and a novel achievable scheme with smartly designed assignments are proposed. Our proposed scheme outperforms the optimal scheme based on the widely used cyclic data assignment and coincides with the converse bound under specific system parameters.

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.

The reconfigurable intelligent surface (RIS) has garnered considerable attention due to its substantial potential in reconfiguring the electromagnetic environment. In RIS-aided communications, constrained ℓ2-norm maximization problems frequently arise due to the phase configuration requirements. This paper investigates a general discrete ℓp-norm maximization problem, with power aggregation through RIS as a specific example. We propose a mathematically concise iterative framework composed of alternating inner product maximizations, which is well-suited for addressing both ℓ1- and ℓ2-norm maximizations under either discrete or continuous uni-modular variable constraints. The iteration process is proven to be monotonically non-decreasing. Additionally, this framework exhibits a distinctive capability to mitigate performance degradation caused by discrete quantization in practical systems, which is applicable to any algorithm intended for the continuous solution. Furthermore, as an integral component of the alternating iterations framework, we present a divide-and-sort (DaS) method to tackle the discrete inner product maximization problem. In the realm of ℓ∞-norm maximization, the DaS method ensures the identification of the global optimum with polynomial search complexity. We validate the proposed methods’ effectiveness and superiority through numerical and prototype experiments. Finally, we demonstrate that the proposed framework can be extended and applied to a wide range of other engineering problems.

This paper studies a multiaccess coded caching (MACC) problem where the connectivity topology between the users and the caches can be described by a class of combinatorial designs. Our model includes several MACC topologies considered in previous works as special cases. The considered MACC network includes a server containingNfiles, Γ cache nodes andKcacheless users, where each user can accessLcache nodes. The server is connected to the users via an error-free shared link, while the users can directly access the content in their connected cache nodes. Our goal is to minimize the worst-case transmission load on the shared link in the delivery phase. The main limitation of the existing MACC works is that only some specific access topologies are considered, including the only cases where the number of usersKscales either linearly or exponentially in Γ. We overcome this limitation by formulating a new access topology derived from two classical combinatorial structures, referred to as thet-design and thet-group divisible design. By leveraging the properties of these combinatorial structures, we propose two classes of coded caching schemes for a flexible number of users, where the number of users can scale linearly, polynomially or exponentially with the number of cache nodes. As a by-product, by extending the proposed scheme to the original dedicated coded caching scenario (i.e., each user has its own cache), the resulting scheme can unify several existing coded caching schemes.

Bistatic sensing refers to scenarios where the transmitter (illuminating the target) and the sensing receiver (estimating the target state) are physically separated, in contrast to monostatic sensing, where both functions are co-located. In practical settings, bistatic sensing may be required either due to inherent system constraints or as a means to mitigate the strong self-interference encountered in monostatic configurations. A key practical challenge in bistatic radio-frequency radar systems is the synchronization and calibration of the separate transmitter and sensing receiver. In this paper, we are not concerned with these signal processing aspects and take a complementary information-theoretic perspective on bistatic integrated sensing and communication (ISAC). Namely, we aim to characterize the capacity-distortion function—the fundamental tradeoff between communication capacity and sensing accuracy. We consider a general discrete channel model for a bistatic ISAC system and derive a multi-letter representation of its capacity-distortion function. Then, we establish single-letter upper and lower bounds and provide exact single-letter characterizations for degraded bistatic ISAC channels. Numerical examples illustrate the theoretical results, highlighting the benefits of ISAC over separate communication and sensing, as well as the role of leveraging communication to assist sensing in bistatic systems.

This paper investigates a stacked intelligent metasurfaces (SIM)-assisted integrated sensing and communications (ISAC) system. An extended target model is considered, where the base station (BS) aims to estimate the complete target response matrix relative to the SIM. Under the constraints of minimum signal-to-interference-plus-noise ratio (SINR) for the communication users (CUs) and maximum transmit power, we jointly optimize the transmit beamforming at the BS and the end-to-end transmission matrix of the SIM, to minimize the Cramér-Rao bound (CRB) for target estimation. Effective algorithms such as alternating optimization (AO) and semidefinite relaxation (SDR) are employed to solve the non-convex SINR-constrained CRB minimization problem. Finally, we design and build a hardware platform for SIM, and experimentally evaluate the performance of SIM-aided communication and sensing tasks.

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.

Elasticity plays an important role in modern cloud computing systems. Elastic computing allows virtual machines (i.e., computing nodes) to be preempted when high-priority jobs arise, and also allows new virtual machines to participate in the computation. This paper consider the elastic computing with heterogeneous speeds under uncoded storage. In 2018, Yang et al. introduced Coded Storage Elastic Computing (CSEC) to address the elasticity using coding technology, with lower storage and computation load requirements. However, CSEC is limited to certain types of computations (e.g., linear) due to the coded data storage based on linear coding. Then Centralized Uncoded Storage Elastic Computing (CUSEC) with heterogeneous computation speeds was proposed, which directly copies parts of data into the virtual machines. In all existing works in elastic computing, the storage assignment is centralized, meaning that the number and identity of all virtual machines possible used in the whole computation process are known during the storage assignment. In this paper, we consider Decentralized Uncoded Storage Elastic Computing (DUSEC) with heterogeneous computation speeds, where any available virtual machine can join the computation which is not predicted and thus coordination among different virtual machines' storage assignments is not allowed. Under a decentralized storage assignment originally proposed in coded caching by Maddah-Ali and Niesen, we propose a computing scheme with closed-form optimal computation time. We also run experiments over MNIST dataset with Softmax regression model through the Tencent cloud platform, and the experiment results demonstrate that the proposed DUSEC system approaches the state-of-art best storage assignment in the CUSEC system in computation time.

In this paper, we consider a remote source coding problem with binary phase shift keying (BPSK) modulation sources, where observations are corrupted by additive white Gaussian noise (AWGN). An intermediate node, such as a relay, receives these observations and performs further compression to find the optimal trade-off between complexity and relevance. This problem can be formulated as an information bottleneck (IB) problem with Bernoulli sources and Gaussian mixture observations, for which no closed-form solution is known. To address this challenge, we propose a unified achievable scheme that employs three different compression strategies for intermediate node processing, i.e., two-level quantization, multi-level deterministic quantization, and soft quantization with tanh function. Comparative analyses with existing methods, such as the Blahut-Arimoto (BA) algorithm and the Information Dropout approach, are performed through numerical evaluations. The proposed analytic scheme is observed to consistently approach the (numerically) optimal performance over a range of signal-to-noise ratios (SNRs), confirming its effectiveness in the considered setting.

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.

Bistatic Integrated Sensing and Communication (ISAC) systems circumvent the issue of strong self-interference present in monostatic ISAC systems by employing a pair of physically separated sensing transceivers. They maintain the advantage of co-designing radar sensing and communications on shared spectrum and hardware. Motivated by the favorable attributes of bistatic radar, this paper investigates bistatic ISAC. In this setup, a transmitter sends messages to a communication receiver, while a sensing receiver at another location conducts a “decoding-and-estimation” (DnE) operation to obtain the state of the communication receiver. We propose three achievable DnE strategies based on the degree of information decoding at the sensing receiver: blind estimation, partial decoding-based estimation, and full decoding-based estimation. We explore the corresponding rate-distortion regions associated with each strategy. Furthermore, we provide a specific example to illustrate the comparison of the rate-distortion regions among the three DnE strategies and demonstrate the advantage of ISAC over independent communication and sensing.

Reconfigurable intelligent surface (RIS) has been treated as a core technique in improving wireless propagation environments for the next generation wireless communication systems. This paper proposes a new coded caching problem, referred to as Reconfigurable Intelligent Surface (RIS)-assisted multiple-antenna coded caching, which is composed of a server with multiple antennas and some single-antenna cache-aided users. Different from the existing multi-antenna coded caching problems, we introduce a passive RIS (with limited number of units) into the systems to further increase the multicast gain (i.e., degrees of freedom$(\mathbf{DoF}))$in the transmission, which is done by using RIS-assisted interference nulling. That is, by using RIS, we can ‘erase’ any path between one transmission antenna and one receive antenna. We first propose a new RIS-assisted interference nulling approach to search for the phase-shift coefficients of RIS for the sake of interference nulling, which converges faster than the state-of-the-art algorithm. After erasing some paths in each time slot, the delivery can be divided into several non-overlapping groups including transmission antennas and users, where in each group the transmission antennas serve the contained users without suffering interference from the transmissions by other groups. The division of groups for the sake of maximizing the DoF could be formulated into a combinatorial optimization problem. We propose a grouping algorithm which can find the optimal solution with low complexity, and the corresponding coded caching scheme achieving this DoF.

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.

This paper studies the beamforming optimization challenge in reconfigurable intelligent surface (RIS)-aided multiple-input single-output (MISO) systems, where the RIS phase configuration is discrete. Conventional optimization meth-ods for this discrete optimization problem necessitate resource-intensive exponential search and thus fall within the universal (NP-hard) category. We formally define this task as a discrete inner product maximization problem. Leveraging the inherent structure of this problem, we propose an efficient divide-and-sort (Da$S$) search algorithm to reach the global optimality for the maximization problem. The complexity of the proposed algorithm can be minimized to$\mathrm{O}(2^{B}N)$, a linear correlation with the count of phase discrete levels$2^{B}$and reflecting units$N$. This is notably lower than the exhaustive search complexity of$\mathcal{O}(2^{BN})$. Numerical evaluations and experiments over real prototype also demonstrate the efficiency of the proposed DaS algorithm. Finally, by using the proposed algorithm, we show that over some resolution quantization level on each RIS unit (4-bit and above), there is no noticeable difference in power gains between continuous and discrete phase configurations.

A fair beam allocation framework through reconfigurable intelligent surfaces (RISs) is proposed, incorporating the Max-min criterion. This framework focuses on designing explicit beamforming functionalities through optimization. Firstly, realistic models, grounded in geometrical optics, are introduced to characterize the input/output behaviors of RISs, effectively bridging the gap between the requirements on explicit beamforming operations and their practical implementations. Then, a highly efficient algorithm is developed for Max-min optimizations involving quadratic forms. Leveraging the Moreau-Yosida approximation, we successfully reformulate the original problem and propose an iterative algorithm to obtain the optimal solution. A comprehensive analysis of the algorithm’s convergence is provided. Importantly, this approach exhibits excellent extensibility, making it readily applicable to address a broader class of Max-min optimization problems. Finally, numerical and prototype experiments are conducted to validate the effectiveness of the framework. With the proposed beam allocation framework and algorithm, we clarify that several crucial redistribution functionalities of RISs, such as explicit beam-splitting, fair beam allocation, and wide-beam generation, can be effectively implemented. These explicit beamforming functionalities have not been thoroughly examined previously.

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.

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.

This paper studies a novel multi-access coded caching (MACC) model in the two-dimensional (2D) topology, which is a generalization of the one-dimensional (1D) MACC model proposed by Hachem et al. The 2D MACC model is formed by a server containing$N$files,$K_{1}\times K_{2}$cache-nodes with$M$files located at a grid with$K_{1}$rows and$K_{2}$columns, and$K_{1}\times K_{2}$cache-less users where each user is connected to$L^{2}$nearby cache-nodes. The server is connected to the users through an error-free shared link, while the users can retrieve the cached content of the connected cache-nodes without cost. Our objective is to minimize the worst-case transmission load over all possible users’ demands. In this paper, we first propose a grouping scheme for the case where$K_{1}$and$K_{2}$are divisible by$L$. By partitioning the cache-nodes and users into$L^{2}$groups such that no two users in the same group share any cache-node, we use the shared-link coded caching scheme proposed by Maddah-Ali and Niesen for each group. Then for any model parameters satisfying$\min \{K_{1},K_{2}\}\geq L$, we propose a transformation approach which constructs a 2D MACC scheme from two classes of 1D MACC schemes in vertical and horizontal projections, respectively. As a result, we can construct 2D MACC schemes that achieve maximum local caching gain and improved coded caching gain, compared to the baseline scheme by a direct extension from 1D MACC schemes. In addition, we propose new information theoretic converse bounds under the uncoded placement constraint by leveraging the network topology.

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.

This paper studies a novel multi-access coded caching (MACC) model where the topology between users and cache nodes is a generalization of those already studied in previous work, such as combinatorial and cross-resolvable design topologies. Our goal is to minimize the worst-case transmission load in the delivery phase from the server over all possible user requests. By formulating the access topology as two classical combinatorial structures, t-design and t-group divisible design, we propose two classes of coded caching schemes for a flexible number of users, where the number of users can scale linearly, polynomially or exponentially with the number of cache nodes. In addition, our schemes can unify most schemes for the shared link network and unify many schemes for the multi-access network except for the cyclic wrap-around topology.

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.

Integrated sensing and communications (ISAC) is recognized as a key enabling technology for future wireless networks. To shed light on the fundamental performance limits of ISAC systems, this paper studies the deterministic-random tradeoff between sensing and communications (S&C) from a rate-distortion perspective under vector Gaussian channels. We model the ISAC signal as a random matrix that carries information, whose realization is perfectly known to the sensing receiver, but is unknown to the communication receiver. We characterize the sensing mutual information conditioned on the random ISAC signal, and show that it provides a universal lower bound for distortion metrics of sensing. Furthermore, we prove that the distortion lower bound is minimized if the sample covariance matrix of the ISAC signal is deterministic. We then offer our understanding of the main results by interpreting wireless sensing as non-cooperative source-channel coding, and reveal the deterministic-random tradeoff of S&C for ISAC systems. Finally, we provide sufficient conditions for the achievability of the distortion bound by analyzing specific examples.

Coded distributed computing (CDC), originally proposed by Li et al., leverages coded multicast messages to exchange computed intermediate values among the distributed computing nodes, such that the overall communication load could be reduced by a factor of r, the number of input files assigned to each node. However, in the original CDC framework, each output function/task is composed of intermediate values from all input files. In this paper, we propose a new CDC problem for sparse functions with structured support, where each output function depends on a subset of the input files. For a symmetric structured support for which the input files are divided into G equal-length batches and each output function depends on the same number of G′batches, we propose a novel CDC scheme that is strictly better by a factor G/G′than directly employing the original CDC scheme in the considered problem. Furthermore, by proposing a new converse bound, we prove that the communication load of the proposed CDC scheme is order optimal within a constant multiplicative factor of 6.

This paper studies the fundamental limits of the shared-link coded caching problem with correlated files, where a server with a library of${\mathsf N}$files communicates with${\mathsf K}$users who can locally cache${\mathsf M}$files. Given an integer${\mathsf r}\in [{\mathsf N}]$, correlation is modelled as follows: each${\mathsf r}$-subset of files contains a unique common block. The tradeoff between the cache size and the average transmitted load over the uniform demand distribution is studied. First, a converse bound under the constraint of uncoded cache placement (i.e., each user directly stores a subset of the library bits) is derived. Then, a caching scheme for the case where every user demands a distinct file (possible for${\mathsf N}\geq {\mathsf K}$) is shown to be optimal under the constraint of uncoded cache placement. This caching scheme is further proved to be decodable and optimal under the constraint of uncoded cache placement when (i)${\mathsf K} {\mathsf r} {\mathsf M}\leq 2 {\mathsf N}$or${\mathsf K} {\mathsf r} {\mathsf M}\geq ({\mathsf K}-1) {\mathsf N}$or${\mathsf r}\in \{1,2, {\mathsf N}-1, {\mathsf N}\}$, and (ii) when the number of distinct demanded files is no larger than four. Finally, a new delivery scheme based on interference alignment which jointly serves the users’ demands is shown to be order optimal to within a factor of 2 under the constraint of uncoded cache placement. As an extension, the above exact and order optimal results can be extended to the worst-case load. As by-products, an extension of the proposed scheme for${\mathsf M}= {\mathsf N}/ {\mathsf K}$is shown to reduce the load of state-of-the-art schemes for the coded caching problem where the users can request multiple files; the proposed scheme for distinct demands can be extended to the coded distributed computing problem with a central server, which achieves the optimal transmission load over the binary field.

Caching prefetches some library content at users’ memories during the off-peak times (i.e., placement phase), such that the number of transmissions during the peak-traffic times (i.e., delivery phase) are reduced. A coded caching strategy was originally proposed by Maddah-Ali and Niesen (MN) leading to a multicasting gain compared to the conventional uncoded caching, where each message in the delivery phase is useful to multiple users simultaneously. The load of the MN scheme is optimal under uncoded placement, but the subpacketization level is$O\left({2^{H\left({\frac {M}{N}}\right)K}}\right)$, where$K$is the number of users,$\frac {M}{N}$is the memory ratio of each user and$H\left({\frac {M}{N}}\right)$is the binary entropy at$\frac {M}{N}$. In order to reduce the subpacketization while retaining the multicast opportunities in the delivery phase, Yan et al. proposed a combinatorial structure called placement delivery array (PDA) to design coded caching schemes with uncoded placement and clique-covering delivery. In this paper, we consider the coded caching problem from the perspective of PDA. First we propose a Cartesian product method, which constructs an$mK_{1}$-user PDA based on the piece-wise$m$-fold Cartesian product of a special$K_{1}$-user PDA (called a base PDA) while keeping the memory ratio and load unchanged. Since a base PDA must satisfy some restrictive constraints, we propose a transformation from any existing PDA to a base PDA, which makes the Cartesian product method applicable to any existing PDA. As applications of the Cartesian product method, three new coded caching schemes (i.e., Schemes A, B, C) are obtained, whose performance are validated via analytical and numerical comparisons. It is worth noting that Scheme A is asymptotically optimal under uncoded placement, in the sense that the achieved coded caching gain is only decreased by 1 with respect to the coded caching gain of the MN scheme. When the number of users is$K=mq$and memory ratio is$\frac {z}{q}$, the needed subpacketization is at most$O\left ({\sqrt {\frac {K}{q}}2^{-\frac {K}{q}}}\right)$of that of the MN scheme for large$m$, which implies that for fixed number of users and memory ratio, when we choose$q$and$z$coprime, the subpacketization can be reduced the most, since the value of$\frac {K}{q}$is maximized. Moreover, Scheme A works for arbitrary memory ratio.

We consider the cache-aided multiple-input single-output (MISO) broadcast channel, which consists of a server with$L$antennas and$K$single-antenna users, where the server contains$N$files of equal length and each user is equipped with a local cache of size$M$files. Each user requests an arbitrary file from library. The objective is to design a coded caching scheme based on uncoded placement and one-shot linear delivery, to achieve the maximum sum Degree-of-Freedom (sum-DoF) with low subpacketization. It was shown in the literature that under the constraint of uncoded placement and one-shot linear delivery, the maximum sum-DoF is$\min \left\{{L+\frac {KM}{N},K}\right\}$. However, previously proposed schemes for this setting incurred either an exponential subpacketization order in$K$, or required specific conditions in the system parameters$L$,$K$,$M$and$N$. In this paper, we propose a new combinatorial structure called multiple-antenna placement delivery array (MAPDA). Based on MAPDA and Latin square, the first proposed scheme achieves the maximum sum-DoF$\min \left\{{L+\frac {KM}{N},K}\right\}$with the subpacketization of$K$when$\frac {KM}{N}+L=K$. Subsequently, for the general case we propose a transformation approach to construct an MAPDA from any$g$-regular PDA (a class of placement delivery arrays for the shared link caching problem where each integer in the array occurs$g$times). When$g$-regular PDA corresponds to the Maddah-Ali and Niesen scheme, the resulting MAPDA yields the maximum sum-DoF$\min \left\{{L+\frac {KM}{N},K}\right\}$with reduced subpacketization compared to the existing schemes. The general scheme can be extended to the multiple independent single-antenna transmitters (servers) corresponding to the cache-aided interference channel proposed by Naderializadeh et al. and the scenario of transmitters equipped with multiple antennas.

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.

Hachem et al. formulated a multiaccess coded caching model which consists of a central server connected to K users via an error-free shared link, and K cache-nodes. Each cache-node is equipped with a local cache and each user can access L neighbouring cache-nodes in a cyclic wraparound fashion. In this paper, we take the privacy of the users’ demands into consideration, i.e., each user, while retrieving its own demanded file, cannot obtain any information on the demands of the other users. By storing some private keys at the cache-nodes, we develop a novel transformation approach to turn any non-private coded caching scheme (satisfying some constraints) into a private one.

Caching is an efficient technique to reduce the peak-time traffic by prefetching some library content at users’ memories during the off-peak hours. Maddah-Ali and Niesen (MN) proposed the first coded caching scheme, which achieves a multicasting gain over the conventional uncoded caching. However, its high subpacketization makes it impractical. In order to reduce the subpacketization while retaining the multicast opportunities, Yan et al. proposed a combinatorial structure called placement delivery array (PDA) to design coded caching schemes. In this paper, we propose a new framework for constructing a PDA for mK1users, by taking the m-fold Cartesian product of a PDA for K1users. By applying the proposed framework to the MN scheme, a new coded caching scheme is obtained, which works for any number of users and any memory regime. While reducing the coded caching gain by only one, the needed subpacketization is at most $O\left( {\sqrt {\frac{K}{q}} {2^{ - \frac{K}{q}}}} \right)$ of that of the MN scheme, where K is the number of users, 0 < z/q < 1 is the memory ratio of each user, and q, z are coprime.

This paper considers the cache-aided multiple-input single-output (MISO) broadcast channel (BC) consisting of one server and K users, where the server with L antennas accesses to N files and each user with single antenna has a cache of M files. The objective of this problem is to maximize the sum Degree-of-Freedom (sum-DoF) of the system. It was proved that under uncoded cache placement and one-shot zero-forcing (ZF) delivery, the maximum sum-DoF is L + KM/N. However, previously proposed schemes achieving the maximum sum-DoF either require an exponential order of K or work for some limited cases. In this paper, we propose a new combinatorial structure called multiple-antenna placement delivery array (MAPDA), which generalizes the coded caching schemes under uncoded cache placement and one-shot ZF delivery. We then propose two schemes (for the case $\frac{{KM}}{N} + L = K$ and the general case, respectively), which can achieve the maximum sum-DoF with reduced subpacketization with respect to the existing schemes. The first scheme is based on the Latin square, while the second scheme is obtained by an approach which transforms a class of schemes for the original shared-link coded caching model to the MISO system.

This paper formulates the multi-access coded caching (MACC) problem under the two-dimensional (2D) topology, which is a generalization of the one-dimensional (1D) MACC problem originally considered by Hachem et al. The novel 2D MACC system includes a server containing N files, K1×K2cache-nodes (each of size M units) placed on a grid with K1rows and K2columns, and K1×K2cache-less users, each of which accesses to L2nearby cache-nodes. More precisely, focus on any row (or column) of the grid, each user can access L consecutive cache-nodes in a cyclic wrap-around fashion, referred to as row (or column) 1D MACC problem in the 2D MACC system. The users are connected to the server through an error-free shared link, while they can also retrieve the content stored at the accessible cache-nodes without cost. Our objective is to minimize the worst-case transmission load among all possible users’ demands. This work proposes a baseline scheme firstly, which directly extends an existing 1D MACC scheme to the 2D model by using a Minimum Distance Separable (MDS) code. Then two improved schemes are designed. In the grouping scheme, we divide the cache-nodes and users into L2groups by their positions, such that any two users in the same group do not share any cache-node, and then utilize the seminal shared-link coded caching scheme proposed by Maddah-Ali and Niesen for each group. Then we propose the hybrid scheme, consisting in a highly non-trivial way to construct a 2D MACC scheme by using two 1D MACC problems under vertical and horizontal projections.

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.

Elasticity is one important feature in modern cloud computing systems and can result in computation failure or significantly increase computing time. Such elasticity means that virtual machines over the cloud can be preempted under a short notice (e.g., hours or minutes) if a high-priority job appears; on the other hand, new virtual machines may become available over time to compensate the computing resources. Coded Storage Elastic Computing (CSEC) introduced by Yang et al. in 2018 is an effective and efficient approach to overcome the elasticity and it costs relatively less storage and computation load. However, one of the limitations of the CSEC is that it may only be applied to certain types of computations (e.g., linear) and may be challenging to be applied to more involved computations because the coded data storage and approximation are often needed. Hence, it may be preferred to use uncoded storage by directly copying data into the virtual machines. In addition, based on our own measurement, virtual machines on Amazon EC2 clusters often have heterogeneous computation speed even if they have exactly the same configurations (e.g., CPU, RAM, I/O cost). In this paper, we introduce a new optimization framework on Uncoded Storage Elastic Computing (USEC) systems with heterogeneous computing speed to minimize the overall computation time. Under this framework, we propose optimal solutions of USEC systems with or without straggler tolerance using different storage placements. Our proposed algorithms are evaluated using power iteration applications on Amazon EC2.

Caching at the wireless edge nodes is a promising way to boost the spatial and spectral efficiency, for the sake of alleviating networks from content-related traffic. Coded caching originally introduced by Maddah-Ali and Niesen significantly speeds up communication efficiency by transmitting multicast messages simultaneously useful to multiple users. Most prior works on coded caching are based on the assumption that each user may request all content in the library. However, in many applications the users are interested only in a limited set of content that depends on their location. For example, assisted self-driving vehicles may access super High-Definition maps of the area through which they are travelling. Motivated by these considerations, this paper formulates the coded caching problem for location-based content with edge cache nodes. The considered problem includes a content server with access to${\mathsf N}$location-based files (e.g., High-Definition maps),${\mathsf K}$edge cache nodes located at different regions, and${\mathsf K}$users (i.e., vehicles) each of which is in the serving region of one cache node and can retrieve the cached content of this cache node with negligible cost. Depending on the location, each user only requests a file from a location-dependent subset of the library. The objective is to minimize the worst-case load (i.e., the worst-case number of broadcasted bits from the content server among all possible demands). For this novel coded caching problem, we propose a highly non-trivial converse bound under uncoded cache placement (i.e., each cache node directly copies some library bits in its cache), which shows that a simple achievable scheme is optimal under uncoded cache placement. In addition, this achievable scheme is also proved to be generally order optimal within a factor of 3. Finally, we extend the coded caching problem for location-based content to the multiaccess coded caching topology originally proposed by Hachemet al., where each user is connected to${\mathsf L}$nearest cache nodes. When${\mathsf L}\geq 2$, we characterize the exact optimality on the worst-case load.

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.

Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the users’ local caches. For the shared-link network with end-user-caches, Maddah-Ali and Niesen proposed a two-phase coded caching strategy. In practice, users may communicate with the server through intermediate relays. This paper studies the tradeoff between the memory size M and the network load R for the networks where a server with N files is connected to H relays (without caches), which in turn are connected to K users equipped with caches of M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, converse bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly pushed into the user caches without any coding. In this case, once the cache contents and the users’ demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well-known “acyclic index coding converse bound” results in converse bounds that are not tight for combination networks with end-user-caches. A novel converse bound that leverages the network topology is proposed, which is the tightest converse bound known to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived. Several novel caching schemes are proposed, based on the Maddah-Ali and Niesen cache placement. These schemes leverage the structure of the combination network or/and perform interference elimination at the end-users. The proposed schemes are proved: (i) to be (order) optimal for some (N, M, H, r) parameters regimes under the constraint of uncoded cache placement, and (ii) to outperform the state-of-the-art schemes in numerical evaluations.

This paper studies the multiaccess caching systems formulated by Hachem et al., including a central server containing$N$files connected to$K$cache-less users through an error-free shared link, and$K$cache-nodes, each equipped with a cache memory size of$M$files. Each user has access to$L$neighbouring cache-nodes with a cyclic wrap-around topology. The coded caching scheme proposed by Hachem et al. suffers from the case that$L$does not divide$K$, where the needed number of transmissions (a.k.a. load) is at most four times the load expression for the case where$L$divides$K$. Our main contribution is to propose a novel transformation approach to smartly extend the MN scheme to the multiaccess caching systems, such that the load expression of the scheme by Hachem et al for the case where$L$divides$K$, remains achievable in full generality. The resulting scheme has the maximum local caching gain (i.e., the cached contents stored at any$L$neighbouring cache-nodes are different such that each user can totally retrieve$L M$files from the connected cache-nodes) and the same coded caching gain as the related MN scheme. Moreover, our transformation approach can also be used to extend other coded caching schemes (satisfying some conditions) for the original MN caching systems to the multiaccess systems, such that the resulting scheme achieves the maximum local caching gain and the same coded caching gain as the considered caching scheme.

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.

The coded caching scheme originally proposed by Maddah-Ali and Niesen (MAN) transmits coded multicast messages from a server to users equipped with caches via a capacitated shared-link and was shown to be information theoretically optimal within a constant multiplicative factor. This work extends the MAN scheme to a class of two-hop wired-wireless networks including one server connected via fronthaul links to a layer of H helper nodes (access points/base stations), which in turn communicate via a wireless access network to K users, each equipped with its own cache. Two variants are considered, which differ in the modeling of the access segment. Both models should be regarded as abstractions at the “network layer” for physical scenarios such as local area networks and cellular networks, spatially distributed over a certain coverage area. The key of our approach consists of routing MAN-type multicast messages through the network and formulating the optimal routing scheme as an optimization problem that can be solved exactly or for which we give powerful heuristic algorithms. Our approach addresses at once many of the open practical problems identified as stumbling blocks for the application of coded caching in practical scenarios, namely: asynchronous streaming sessions, finite file size, scalability of the scheme to large and spatially distributed networks, user mobility and random activity (users joining and leaving the system at arbitrary times), decentralized prefetching of the cache contents, end-to-end encryption of HTTPS requests, which renders the helper nodes oblivious of the users' demands.

This paper considers the multiaccess coded caching systems formulated by Hachemet al., including a central server containing$N$files connected to$K$cache-less users through an error-free shared link, and$K$cache-nodes, each equipped with a cache memory size of$M$files. Each user has access to$L$neighbouring cache-nodes with a cyclic wrap-around topology. The coded caching scheme proposed by Hachemet al.suffers from the case that$L$does not divide$K$, where the needed number of transmissions (a.k.a. load) is at most four times the load expression for the case where$L$divides$K$. Our main contribution is to propose a noveltransformationapproach to smartly extend the schemes satisfying some conditions for the well known shared-link caching systems to the multiaccess caching systems. Then we can get many coded caching schemes with different subpacketizations for multiaccess coded caching system. These resulting schemes have the maximum local caching gain (i.e., the cached contents stored at any$L$neighbouring cache-nodes are different such that the number of retrieval packets by each user from the connected cache-nodes is maximal) and the same coded caching gain as the original schemes. Applying the transformation approach to the well-known shared-link coded caching scheme proposed by Maddah-Ali and Niesen, we obtain a new multiaccess coded caching scheme that achieves the same load as the scheme of Hachemet al.but for any system parameters. Under the constraint of the cache placement used in this new multiaccess coded caching scheme, our delivery strategy is approximately optimal when$K$is sufficiently large. Finally, we also show that the transmission load of the proposed scheme can be further reduced by compressing the multicast message.

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.

Maddah-Ali and Niesen (MAN) in 2014 showed that coded caching in single bottleneck-link broadcast networks allows serving an arbitrarily large number of cache-equipped users with a total link load (bits per unit time) that does not scale with the number of users. Since then, the general topic of coded caching has generated enormous interest both from the information theoretic and (network) coding theoretic viewpoint, and from the viewpoint of applications. Building on the MAN work, this paper considers a particular network topology referred to as cache-aided Fog Radio Access Network (Fog-RAN), that includes a Macro-cell Base Station (MBS) co-located with the content server, several cache-equipped Small-cell Base Stations (SBSs), and many users without caches. Some users are served directly by the MBS broadcast downlink, while other users are served by the SBSs. The SBSs can also exchange data via rounds of direct communication via a side channel, referred to as “sidelink”. For this novel Fog-RAN model, the fundamental tradeoff among (a) the amount of cache memory at the SBSs, (b) the load on the downlink (from MBS to directly served users and SBSs), and (c) the aggregate load on the sidelink is studied, under the standard worst-case demand scenario. We propose a converse bound whose key novelty is to jointly bound the downlink load an the sidelink load. For the achievability, by leveraging the network topology, we propose two classes of memory-loads point, where the SBS sidelink load is minimum and the MBS downlink load is minimum, respectively. By memory-sharing between these two classes of memory-loads points, some exact or order optimality results are obtained. Several existing models (e.g., Device-to-Device coded caching, single bottleneck-link coded caching with shared caches, single bottleneck-link caching coded caching with cache-less users) are recovered as special cases of this network model and by-product results of independent interest are given. Finally, the role of topology-aware versus topology-agnostic caching is discussed.

Coded caching is an information theoretic scheme to reduce high peak hours traffic by partially prefetching files in the users local storage during low peak hours. This paper considers heterogeneous decentralized caching systems where users' caches and content library files may have distinct sizes. The server communicates with the users through a Gaussian broadcast channel. The main contribution of this paper is a novel joint coded caching and modulation strategy to map the multicast messages generated in the coded caching delivery phase to the symbols of a signal constellation, such that users can leverage their cached content to demodulate the desired symbols with higher reliability and for the sake of simplicity, in this paper we focus only on “uncoded” modulation and symbol-by-symbol error probability. However, our scheme in conjunction with multilevel coded modulation can be extended to channel coding over a larger block lengths.

This paper considers the MapReduce-like coded distributed computing framework originally proposed by Li et al., which uses coding techniques when distributed computing servers exchange their computed intermediate values, in order to reduce the overall traffic load. In their original model, servers are connected via an error-free common communication bus allowing broadcast transmissions. However, this assumption is one of the major limitations for practical implementations since real-world data centers may have network topologies far more involved than a single broadcast bus. We formulate a topological coded distributed computing problem, where the computing servers communicate with each other through some switch network. By using a special instance of fat-tree topologies, referred to as t-ary fat-tree proposed by Al-Fares et al. which can be built by some inexpensive switches, we propose a coded distributed computing scheme to achieve the optimal max-link communication load (defined as the maximum load over all links) over any network topology.

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.

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.

Data shuffling of training data among different computing nodes (workers) has been identified as a core element to improve the statistical performance of modern large-scale machine learning algorithms. Data shuffling is often considered as one of the most significant bottlenecks in such systems due to the heavy communication load. Under a master-worker architecture (where a master has access to the entire dataset and only communication between the master and the workers is allowed) coding has been recently proved to considerably reduce the communication load. This work considers a different communication paradigm referred to as decentralized data shuffling, where workers are allowed to communicate with one another via a shared link. The decentralized data shuffling problem has two phases: workers communicate with each other during the data shuffling phase, and then workers update their stored content during the storage phase. The main challenge is to derive novel converse bounds and achievable schemes for decentralized data shuffling by considering the asymmetry of the workers' storages (i.e., workers are constrained to store different files in their storages based on the problem setting), in order to characterize the fundamental limits of this problem. For the case of uncoded storage (i.e., each worker directly stores a subset of bits of the dataset), this paper proposes converse and achievable bounds (based on distributed interference alignment and distributed clique-covering strategies) that are within a factor of 3/2 of one another. The proposed schemes are also exactly optimal under the constraint of uncoded storage for either large storage size or at most four workers in the system.

Caching is an efficient way to reduce network traffic congestion during peak hours, by storing some content at the user's local cache memory, even without knowledge of user's later demands. Maddah-Ali and Niesen proposed a two-phase (placement phase and delivery phase) coded caching strategy for broadcast channels with cache-aided users. This paper investigates the same model under the constraint that content is placed uncoded within the caches, that is, when bits of the files are simply copied within the caches. When the cache contents are uncoded and the users' demands are revealed, the caching problem can be connected to an index coding problem. This paper focuses on deriving fundamental performance limits for the caching problem by using tools for the index coding problem that were either known or are newly developed in this work. First, a converse bound for the caching problem under the constraint of uncoded cache placement is proposed based on the “acyclic index coding converse bound.” This converse bound is proved to be achievable by the Maddah-Ali and Niesen's scheme when the number of files is not less than the number of users, and by a newly derived index coding achievable scheme otherwise. The proposed index coding achievable scheme is based on distributed source coding and strictly improves on the widely used “composite (index) coding” achievable bound and its improvements, and is of independent interest. An important consequence of the findings of this paper is that advancements on the coded caching problem posed by Maddah-Ali and Niesen are thus only possible by considering strategies with coded placement phase. A recent work by Yu et al has however shown that coded cache placement can at most half the network load compared to the results presented in this paper.

This paper studies the fundamental limits of the shared-link caching problem with correlated files, where a server with a library of N files communicates with K users who can store M files. Given an integer r G ∈ [N], correlation is modelled as follows: each r-subset of files contains one and one only common block. The tradeoff between the cache size and the average transmitted load is considered. First, a converse bound under the constraint of uncoded cache placement (i.e., each user directly caches a subset of the library bits) is derived. Then, an interference alignment scheme is proposed. The proposed scheme achieves the optimal average load under uncoded cache placement to within a factor of 2 in general, and it is exactly optimal for (i) users demand distinct files, (ii) large or small cache size, namely KrM/N ≤ 2 or KrM/N ≥ K - 1, and (iii) large or small correlation, namely r ∈{1, 2, N - 1, N}. As a by-product, the proposed scheme reduces the (worst-case or average) load of existing schemes for the caching problem with multi-requests.

This paper considers a novel cache-aided Fog Radio Access Network (Fog-RAN) architecture including a Macro-cell Base Station (MBS), several Small-cell Base Stations (SBSs), and users. Some users, not in the reach of any SBS, are directly served by the MBS, while the other users are "offloaded" and receive information only from the SBSs through high throughput links. In order to alleviate the load in the wireless front-haul links between the MBS and the SBSs, caching is employed at the SBSs. The MBS sends coded packets to the SBSs and to the directly served users via wireless multicast transmission on a common downlink channel, modeled as an error-free shared link of fixed capacity. Subsequently, the SBSs communicate among one another in a Device-to-Device (D2D) fashion so as each SBS obtains enough information to decode the files demanded by its connected users. The access links between SBSs and users are assumed to operate at a sufficiently high rate such that they are not the system bottleneck. For this novel Fog-RAN model, the memory-loads tradeoff for the worst-case demands is investigated. The main contributions of this paper are: (i) a novel symmetric inter-file coded cache placement scheme, (ii) a novel D2D delivery scheme to handle the inter-SBS communication phase, that is order optimal when each SBS serves the same number of users, and (iii) a novel asymmetric cache placement with file subpacketization dependent on the network structure, which is exactly optimal in some memory size regimes.

We consider a cache-aided wireless device-to-device (D2D) network of the type introduced by Ji et al., where the placement phase is orchestrated by a central server. We assume that the devices' caches are filled with uncoded data, and the whole content database is contained in the collection of caches. After the cache placement phase, the files requested by the users are serviced by inter-device multicast communication. For such a system setting, we provide the exact characterization of the optimal load-memory trade-off under the assumptions of uncoded placement and one-shot delivery. In particular, we derive both the minimum average (under uniformly distributed demands) and the minimum worst-case sum-load of the D2D transmissions, for given individual cache memory size at disposal of each user. Furthermore, we show that the performance of the proposed scheme is within factor 4 of the information-theoretic optimum. Capitalizing on the one-shot delivery property, we also propose an extension of the presented scheme that provides robustness against random user inactivity.

Maddah-Ali and Niesen's original coded caching scheme for shared-link broadcast networks is now known to be optimal to within a factor two, and has been applied to other types of networks. For practical reasons, this paper considers that a server communicates to cache-aided users through H intermediate relays. In particular, it focuses on combination networks where each of the K = (rH) users is connected to a r distinct r-subsets of relays. By leveraging the symmetric topology of the network, this paper proposes a novel method to generate multicast messages such that each multicast message sent to each relay is useful for the largest possible subset of users connected to this relay. By numerical evaluations, the proposed scheme is shown to reduce the download time compared to the schemes available in the literature. The idea is then extended to decentralized combination networks, more general relay networks, and combination networks with cache-aided relays and users. Also in these cases the proposed scheme outperforms known ones.

This paper investigates the fundamental tradeoff between cache size and download time in the (H, r, M, N) combination network, where a server with N files is connected to H relays (without caches) and each of the K: = Hr users (with caches of size M files) is connected to a different subset of r relays. Existing schemes fall within two categories: either use the uncoded symmetric cache placement originally proposed for the shared-link model and design delivery phase dependent on the network topology, or effectively divide the combination network into H uncoordinated shared-link networks each serving K':= H-1r-1 users; in either case, the placement phase leverages effectively the connectivity of relay s/users. In this paper, a novel strategy is proposed where the coded cache placement is dependent on network topology. The proposed scheme is shown to be information theoretically optimal for large cache size. In addition, when not exactly optimal, the proposed scheme can also outperform existing schemes.

This paper studies the tradeoff between the memory size M and the download time / rate R* for networks where a server with N files is connected to H relays (without caches), which in turns are connected to K users equipped with caches of size M files. When each user is connected to a different subset of r relays, i.e., K = (Hr), the system is referred to as a combination network with end-user-caches. In this work, outer bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly copied in the user caches without any coding. In this case, once the cache contents and the user demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well known “acyclic index coding outer bound” results in bounds that are not tight for combination networks with enduser-caches (as opposed to the case without relays) and provides two novel ways to derive the tightest known outer bounds to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived.

Caching is an efficient way to reduce peak hour network traffic congestion by storing some content at the user's cache without knowledge of later demands. Recently, Maddah-Ali and Niesen proposed a two-phase, placement and delivery phase, coded caching strategy for centralized systems (where coordination among users is possible in the placement phase), and for decentralized systems. This paper investigates the same setup under the assumption that the number of users is larger than the number of files. By using the same uncoded placement strategy of Maddah-Ali and Niesen, a novel coded delivery strategy is proposed to profit from the multicasting opportunities that arise because a file may be demanded by multiple users. The proposed delivery method is proved to be optimal under the constraint of uncoded cache placement for centralized systems with two files. Moreover it is shown to outperform known caching strategies for both centralized and decentralized systems.

Caching is an effective way to reduce peak-hour network traffic congestion by storing some contents at user's local cache. Maddah-Ali and Niesen (MAN) initiated a fundamental study of caching systems by proposing a scheme (with uncoded cache placement and linear network coding delivery) that is provably optimal to within a factor 4.7. In this paper, when the cache contents and the user demands are fixed, we connect the caching problem to an index coding problem and show the optimality of the MAN scheme under the conditions that (i) the cache placement phase is restricted to be uncoded (i.e, pieces of the files can only copied into the user's cache), and (ii) the number of users is no more than the number of files. As a consequence, further improvements to the MAN scheme are only possible through the use of coded cache placement.