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 investigates the coded caching problem in a multi-access multiple-input single-output (MAMISO) network with the combinatorial topology. The considered system consists of a server containing $N$ files, $Λ$ cache nodes, and $K$ cache-less users, where each user can access a unique subset of $r$ cache nodes. The server is equipped with $L$ transmit antennas. Our objective is to design a caching scheme that simultaneously achieves a high sum Degree of Freedom (sum-DoF) and low subpacketization complexity. To address this challenge, we formulate the design of multi-antenna placement delivery arrays (MAPDA) as a $0$--$1$ knapsack problem to maximize the achievable DoF, thereby transforming the complex combinatorial caching structure into a tractable optimization framework that yields efficient cache placement and flexible delivery strategies. Theoretical and numerical analyses demonstrate that: for networks with combinatorial topologies, the proposed scheme achieves a higher sum-DoF than existing schemes. Under identical cache size constraints, the subpacketization level remains comparable to existing linear subpacketization schemes. Moreover, under specific system conditions, the proposed scheme attains the theoretical maximum sum-DoF of $\min\{L+KM/N, K\}$ while achieving further reductions subpacketization. For particular combinatorial structures, we further derive optimized constructions that achieve even higher sum-DoF with lower subpacketization. ```

The high overhead of fault-tolerant measurement sequences (FTMSs) poses a major challenge for implementing quantum stabilizer codes. Here, we address this problem by constructing efficient FTMSs for the class of quantum Hamming codes $[\![2^r-1, 2^r-1-2r, 3]\!]$ with $r=3k+1$ ($k \in \mathbb{Z}^+$). Our key result demonstrates that the sequence length can be reduced to exactly $2r+1$-only one additional measurement beyond the original non-fault-tolerant sequence, establishing a tight lower bound. The proposed method leverages cyclic matrix transformations to systematically combine rows of the initial stabilizer matrix and preserving a self-dual CSS-like symmetry analogous to that of the original quantum Hamming codes. This induced symmetry enables hardware-efficient circuit reuse: the measurement circuits for the first $r$ stabilizers are transformed into circuits for the remaining $r$ stabilizers simply by toggling boundary Hadamard gates, eliminating redundant hardware. For distance-3 fault-tolerant error correction, our approach simultaneously reduces the time overhead via shorting the FTMS length and the hardware overhead through symmetry-enabled circuit multiplexing. These results provide an important advance towards the important open problem regarding the design of minimal FTMSs for quantum Hamming codes and may shed light on similar challenges in other quantum stabilizer codes.

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

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.

Coded caching is a promising technique to create coded multicast opportunities for cache-aided networks. By splitting each file intoFequal packets (i.e., the subpacketization levelF) and letting each user cache a set of packets, the transmission load can be significantly reduced via coded multicasting. It has been shown that a higher subpacketization level could potentially lead to a lower transmission load, as more packets can be combined for efficient transmission. On the other hand, a largerFindicates a higher coding complexity and is problematic from a practical perspective whenFis extremely large. Despite many works attempting to design coded caching schemes with low subpacketization levels, a fundamental problem remains open: What is the minimum transmission load given any fixed subpacketization level? In this paper, we consider the classical cache-aided networks with identically uncoded placement and one-shot delivery strategy, and investigate the fundamental trade-off between the transmission load and the subpacketization level. We propose agenerallower bound on the transmission load for any fixed subpacketization by reformulating the centralized coded caching schemes via the combinatorial structure of the corresponding placement delivery array. The lower bound also recovers existing optimality results for the bipartite graph scheme (including the well-known Maddah-Ali and Niesen (MN) scheme and the conjugate MN scheme) as well as the grouping bipartite graph scheme. Furthermore, by carefully exploiting the combinatorial structure and computing the union size of sorted sets, we establish a new optimality result, i.e., the partition scheme can achieve the optimal rate-subpacketization trade-off.

This work considers the device-to-device (D2D) multi-access coded caching problem proposed by Wu et al., where each user has access toLneighboring cache nodes in a cyclic wrap-around fashion and the users communicate with each other in the delivery phase. D2D placement delivery array (DPDA) is a combinatorial structure to design D2D coded caching schemes with uncoded placement and one-shot linear delivery. In order to achieve the maximal local caching gain with a linear subpacketization, we adopt the consecutive cyclic placement proposed for the multi-access coded caching system. First, we derive an upper bound on the coded caching gain of D2D coded caching schemes from DPDA under the consecutive cyclic placement, leading to a lower bound on the communication load. Second, we equivalently represent DPDA as a vector set satisfying certain constraints, and design a vector set satisfying the constraints, which generates a new D2D multi-access coded caching scheme with linear subpacketization for arbitrary number of users and cache node memory ratio. The new scheme either achieves the derived lower bound or achieves a coded caching gain that is only 1 less than the derived upper bound. Performance analysis demonstrates that our proposed scheme, maintaining linear subpacketization, achieves a smaller communication load compared to existing schemes with linear subpacketization. Furthermore, compared to the existing schemes employing sub-exponential subpacketization, it significantly reduces subpacketization and even achieves a lower communication load whenLis relatively large.

Device-to-Device (D2D) assisted coded caching is a promising approach to improve the communication efficiency over networks. However, the basic D2D coded caching scheme requires a subpacketization size that increases exponentially with the number of users. This is infeasible since the file size needs to be extremely large in the server. It is desirable to design a scheme that achieves a small subpacketization size while keeping the rate low. Recently, D2D placement delivery array (DPDA) was proposed to address the high subpacketization issue of D2D coded caching. This paper investigates the design of DPDA from the perspectives of linear algebraic and additive combinatorics. It is shown that a linear subspace possessing certain property can be employed in the design of DPDA. Based on this, a new D2D coded caching scheme with a subquadratic subpacketization size is derived through shortening the binary Reed-Muller codes. In order to obtain a D2D coded caching scheme with a linear subpacketization size, a new combinatorial structure called proper disjoint 3-term arithmetic progression (3-AP) free set is further introduced, and a deterministic algorithm for constructing it is provided with a polynomial complexity. Both the theoretical and numerical results reveal that the proposed schemes have a superior performance in terms of subpacketization size or transmission rate.

The rack-aware storage model improves repair efficiency by exploiting locality within racks to minimize cross-rack traffic in a distributed storage system. While the partially cooperative repair model presents a solution for multiple node failures that reduces the need to exchange data with all other host racks (defined as racks containing failed nodes), thus enhancing system flexibility. In this paper, we focus on rack-aware minimum storage partially cooperative regenerating (MSPCR) codes for repairing multiple node failures. We first derive the lower bound on the repair bandwidth for rack-aware MSPCR codes using extremal combinatorics, and then explicitly construct the first class of (asymptotically) optimal repair schemes for rack-aware MSPCR codes with a sub-packetization level of (s+h− δ)sn, which is smaller than that of the known rack-aware minimumstorage cooperative regenerating (MSCR) codes when δ ≥ 2. By utilizing the grouping technique, we explicitly construct the second class of (asymptotically) optimal repair schemes for rack-aware MSPCR codes with a sub-packetization level of 2n. In particular, when δ = 1, our second codes reduce to rack-aware MSCR codes, while achieving an (h+ 1)-fold reduction in sub-packetization level compared to the known rack-aware MSCR codes.

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.

The characterization of entropy functions is of fundamental importance in information theory. By imposing constraints on their Shannon outer bound, i.e., the polymatroidal region, one obtains the faces of the region and entropy functions on them with special structures. In this series of two papers, we characterize entropy functions on the 2-dimensional faces of the polymatroidal region Γ4. In Part I, we formulated the problem, enumerated all 59 types of 2-dimensional faces of Γ4by an algorithm, and fully characterized entropy functions on 49 types of them. In this paper, i.e., Part II, we will characterize entropy functions on the remaining 10 types of faces, among which 8 types are fully characterized, and 2 types are partially characterized. To characterize these types of faces, we introduce some new combinatorial design structures that are interesting in themselves.

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.

We consider an all-to-all communication problem over a ring network, where N nodes are arranged in a ring topology, and each one wishes to send data to every other node by communicating with its neighbors within a fixed distance. To reduce the communication load, we propose a new coded broadcast scheme that exploits both storage redundancy (i.e., some messages can be stored repeatedly across nodes) and multicast opportunities (i.e., each encoded packet carries multiple messages intended by different nodes). In our schemes, each node transmits each encoded packet based on bits from two messages traveling in opposite directions, and decodes the desired messages based on the local files and priorly recovered messages. Theoretical converse proof shows that our scheme achieves the optimal trade-off between communication load, cache size, and communication distance when N is sufficiently large. The optimality results indicate that in ring-based broadcast, the redundant storage only leads to an additive gain in reducing communication load while the communication distance contributes to a multiplicative gain.

Coded distributed computing (CDC), introduced by Li et al., effectively reduces communication load in MapReduce systems. In cascaded CDC with$K$nodes,$N$input files, and$Q$output functions, each input file is mapped by$r \geq 1$nodes, and each output function is computed by$s>1$nodes, enabling coding for multicast opportunities. However, existing CDC schemes often require splitting data into exponentially many files or functions as$K$grows, increasing complexity and degrading performance. This paper addresses the case of$K / s \in \mathbb{N}$, proposing a low-complexity CDC scheme through carefully designing the strategies of data placement and output function assignment. The proposed scheme offers key advantages:$\mathbf{1}$) multicast gains of$(r+s-1)(1-1 / s)$and approximately$r+s-1$for large$s$, with better communication load than the well-known Li et al.'s scheme; 2) reduce input and output file requirements; and 3) binary field$\mathbb{F}_{2}$operations implement in a one-shot manner, enabling immediate decoding. We also derive a new information-theoretic bound under the proposed strategies, showing that the communication load is order-optimal within a factor of 2 and approximately optimal when$K$is sufficiently large for a given$r$.

In this paper, we study the coded caching problem for the (L,K,M,N) multi-user information retrieval (MIR) system, which consists of a content library of N files, an L-antenna base station (BS) without direct library access, and K single-antenna users, each equipped with a cache of M files. The users communicate with each other assisted by the BS to decode their required files. M. Abolpour et al. proposed an MIR coded caching scheme (referred to as the ASMST scheme), where the uplink/downlink normalized delivery time (NDT) achieves the information-theoretic lower bound for the multiple-input multiple-output (MISO) coded caching system under uncoded cache placement and one-shot linear delivery. However, its subpacketization and computational complexity are extremely high. In order to reduce the computational complexity, we derive that the condition for the uplink/downlink strategy is exactly that for a multi-antenna placement delivery array (MAPDA) with the optimal sum Degree-Of-Freedom (sum-DoF). Based on existing MAPDAs, we proposed three new MIR coded caching schemes, which significantly reduce both the subpacketization and computational complexity while maintaining the same uplink/downlink NDT as the ASMST scheme.

The distributed linearly separable computation problem finds extensive applications across domains such as distributed gradient coding, distributed linear transform, real-time rendering, etc. This paper investigates this problem in a decentralized network, where N workers, connected through a shared device-to-device (D2D) link, collaboratively perform the computation task without a central master. Each worker aims to compute a linearly separable function that can be manifested as Kclinear combinations of K messages, where each message is a function of a distinct dataset. The system is designed to tolerate up to N − Nrstragglers, ensuring that each worker can successfully complete the task based on transmissions from any Nrworkers. Our goal is to minimize the communication cost (the number of symbols transmitted by the fastest Nrworkers), under arbitrary computation cost (the number of uncoded datasets assigned to each worker). For the scenario where the computation cost is minimal, we propose a novel distributed computing scheme that is optimal under the widely used cyclic data assignment. Interestingly, we demonstrate that the side information at each worker is ineffective in the decoding phase when Kc≤ KNr/N, while it becomes beneficial as Kcincreases. Additionally, we extend the proposed scheme to scenarios where the computation cost is not necessarily minimum, and derive the optimal computation-communication costs tradeoff under the cyclic assignment when Kcis comparatively large.

Matroidal entropy functions are entropy functions in the form h = logv·rM, wherev≥ 2 is an integer and rMis the rank function of a matroidM. They can be applied into capacity chracterization and code construction of information theory problems such as network coding, secret sharing, index coding and locally repairable code. In this paper, by constructing the variable strength orthogonal arrays of some matroid operations, we characterize matroidal entropy functions induced by regular matroids and some matroids with the same p-characteristic set as uniform matroidU2,4.

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.

The distributed linearly separable computation problem finds extensive applications across domains such as dis-tributed gradient coding, distributed linear transform, real-time rendering, etc. In this paper, we investigate this problem in a fully decentralized scenario, where$\mathrm{N}$workers collaboratively perform the computation task without a central master. Each worker aims to compute a linearly separable computation that can be manifested as$\mathrm{K}_{\mathrm{c}}$linear combinations of$\mathrm{K}$messages, where each message is a function of a distinct dataset. We require that each worker successfully fulfill the task based on the transmissions from any$\mathrm{N}_{\mathrm{r}}$workers, such that the system can tolerate any$\mathrm{N}-\mathrm{N}_{\mathrm{r}}$stragglers. We focus on the scenario where the computation cost (the number of uncoded datasets assigned to each worker) is minimum, and aim to minimize the communication cost (the number of symbols the fastest$\mathrm{N}_{\mathrm{r}}$workers transmit). We propose a novel distributed computing scheme that is optimal under the widely used cyclic data assignment. Interestingly, we demonstrate that the side information at each worker is ineffective in reducing the communication cost when$\mathrm{K}_{\mathrm{c}}\leq \text{KN}_{\mathrm{r}}/\mathrm{N}$, while it helps reduce the communication cost as$\mathrm{K}_{\mathrm{c}}$increases.

This paper investigates the file and demand private coded caching system, which ensures that each user learns no information about other users' demands and non-demanded files. By proposing the innovative multi-layered coded caching schemes, this study significantly improves the achievable memory-load tradeoff compared to baseline caching schemes designed by the optimal file private scheme and demand private scheme. In particular, the proposed schemes increase the quantity of achievable memory-load points, markedly reduce the delivery load at low memory regime, and attain a tighter minimal-rate point$(M=N(K-1),\ R=1)$than the baseline schemes.

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.

Ina$(K, M, N)$coded caching scheme, in order to pursue a low broadcasting rate based on the designed placements at each user's cache we have to divide each file stored in the server into certain packets. However, the implementation complexity of this scheme increases with the number of packets. So it is important to design a scheme with a small subpacketization level and a relatively low transmission load. Placement delivery array (PDA) is a powerful combinatorial structure to characterize the coded caching scheme including the subpacketization and transmission load under uncoded placement. In this paper, using the projective geometry PG$(q,n)$for any prime power$q$and positive integer$n \geq 3$, we propose a novel class of coded caching scheme with polynomial subpacketization which is less than$K^{\lceil\frac{n+2}{t}\rceil-1}$. In addition, when$t=2$, our scheme has$K=\frac{q^{n}-1}{q-1}, M/N < \frac{2}{q}$and subpacketization$F < K^{2}$. Compared to the - optimal schemes under uncoded placement which have the subpacketization exponentially increasing with$K$, our load increases at most$\frac{K}{2 q\binom{n+1}{2}}$times; compared to the existing schemes with low subpacketizations our schemes have also advantages on the subpacketization and load.

In this paper, we study the coded caching scheme for the$(K,L,M_{\text {T}},M_{\text {U}},N)$partially connected linear network, where there are N files each of which has an equal size,$K+L-1$transmitters, and K users; each user and transmitter caches at most$M_{\text {U}}$and$M_{\text {T}}$files, respectively; each user locally communicates with L nearby transmitters. The goal is to design caching and delivery schemes to reduce the transmission latency measured by the metric named normalized delivery time (NDT). By delicately designing the data placement of the transmitters and users according to the topology, we show that a combinatorial structure called multiple-antenna placement delivery array (MAPDA), which was originally proposed for the multiple-input single-output broadcast channels, can be also helpful in designing schemes for the partially connected linear network. Then, based on existing MAPDAs and our constructing approach, we propose new schemes that achieve the optimal NDT when$ {M_{\text {T}}}+ {M_{\text {U}}}\geq N$and smaller NDT than that of the existing schemes when (${M_{\text {T}}}+ {M_{\text {U}}}\leq N$,$\frac {M_{\text {U}}}{N}+\frac {M_{\text {T}}}{N} \frac {L}{K}\left \lceil {{\frac {K}{L} }}\right \rceil \geq 1$) or ($ {M_{\text {U}}}+ {M_{\text {T}}}\lt N, \frac {K}{L}\notin \mathbb {Z}^{+}$). Moreover, our schemes operate in one-shot linear delivery and significantly reduce the subpacketizations compared to the existing scheme, which implies that our schemes have a wider range of applications and lower complexity of implementation.

Distributed multi-task learning (MTL) is a learning paradigm where distributed users simultaneously learn multiple tasks by leveraging the correlations among tasks. However, distributed MTL suffers from a more severe communication bottleneck than single-task learning as more than one models need to be transmitted in the communication phase. To address this issue, we investigate the hierarchical MTL system where distributed users wish to jointly learn different learning models orchestrated by a central server with the help of multiple relays. We propose a coded distributed computing scheme for hierarchical MTL systems that jointly exploits the network topology and relays’ computing capability to create coded multicast opportunities to improve communication efficiency. We theoretically prove that the proposed scheme can significantly reduce the communication loads both in the uplink and downlink transmissions between relays and the server. To further illustrate the optimality of the proposed scheme, we derive information-theoretic lower bounds on the minimum uplink and downlink communication loads and prove that the gaps between achievable upper bounds and lower bounds are within the minimum number of connected users among all relays. In particular, when the network topology can be delicately designed, the proposed scheme can achieve the information-theoretic optimal communication loads. Experiments on real-world datasets show that our proposed scheme can greatly reduce the overall training time compared to the conventional hierarchical MTL scheme.

Coded caching is an effective technique to reduce the data transmission load by exploiting the cache contents across the network. However, most coded caching schemes are designed for static networks that consist of only a placement phase and a delivery phase. In practice, a network maybe dynamic with multiple rounds of placement and delivery phases, and the number of users within the network may vary. In these dynamic networks, a conventional coded caching scheme may lead to the undesired updates at the existing users’ cache contents. This paper proposes a centralized coded caching scheme for dynamic networks that can support multiple rounds with newly joining users. It prevents cache contents of the existing users from being updated, extending the service duration of cache devices. Further recognizing the need of information security in coded caching, the considered dynamic networks are featured by two constraints: 1) the library files must be kept secure from a wiretapper who has access to the shared link; 2) any subset of users cannot obtain information from the demands of other users. This consideration leads to another dynamic coded caching scheme that ensures information security. It is shown that the proposed schemes can yield a small subpacketization level and achieve a good rate-memory tradeoff.

An$(H,r,M,N)$combination network is a symmetric relay network that involves a central server equipped with$N$files that communicates with$K$users through$H$cache-less intermediate relays, where each user maintains a local cache of size$M$files and is connected to a distinct subset of$r$relays. In this setting, the well-known uniform scheme is proposed by Zewail and Yener via Minimum Distance Separable (MDS) codes. For practical reasons, this paper studies a more general combination network where each distinct subset of$r$relays is connected to$\Lambda $users, referred to as$(H,r,\Lambda,M,N)$dense-user combination network. Although the Zewail-Yener scheme is also feasible for the considered system, it causes high computational complexity since the use of$(H,r)_{q}$MDS code involves expensive multiplication operations in large finite field. In this paper, we aim to design coded caching schemes not only to minimize the worst-case link-load, but also to be implemented over the minimum operation field, i.e., binary field$\mathbb {F}_{2}$. First, we propose a construction which can transform any coded caching scheme for the shared-link model to the considered dense-user combination network. By applying the transformation approach based on the seminal work proposed by Maddah-Ali and Niesen, we present the MAN-based scheme that operates in binary field. To further reduce the link-load under small memory regions, we propose a hybrid scheme that can extend any caching scheme for the original$(H,r,M,N)$combination network to the considered$(H,r,\Lambda,M,N)$dense-user combination network by an ingenious outer-inner construction. From the theoretical analysis of computation complexity, the proposed schemes can significantly reduce the number of bit operations. From numerical comparisons, the link-loads of proposed schemes are close to or even better than that of Zewail-Yener scheme, while significantly reducing the operation field.

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.

Coded distributed computing (CDC) introduced by Li et al. can greatly reduce the communication load for MapReduce computing systems. In the cascaded CDC with$K$workers,$N$input files and$Q$output functions, each input file will be mapped by$r$workers and each output function will be computed by$s$workers such that coding techniques can be applied to create multicast opportunities. The main drawback of most existing CDC schemes is that they require the original data to be split into a large number of input files that grows exponentially with$K$, which would significantly increase the coding complexity and degrade the system performance. In this paper, we first use a classical combinatorial structure$t$-design, for any integer$t\geq 2$, to develop a low-complexity and communication-efficient CDC with$r=s$. Our scheme has much smaller$N$and$Q$than the existing schemes under the same parameters$K$,$r$, and$s$; and achieves smaller communication loads compared with the state-of-the-art schemes when$K$is relatively large. Remarkably, unlike the previous schemes that realize on large operation fields, our scheme operates in one-shot communication on the minimum binary field$\mathbb{F}_2$. With a derived lower bound on the communication load under one-shot linear delivery, we show that the$t$-design scheme is asymptotically optimal. Furthermore, we show that our construction method can incorporate the other combinatorial structures that have a similar property to$t$-design. For instance, we use$t$-GDD to obtain another one-shot asymptotically optimal CDC scheme over$\mathbb{F}_2$that has different parameters from$t$-design. Finally, we show that our construction method can also be used to construct CDC schemes with$r\neq s$that have small file number and output function number.

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.

In this paper, we consider a two-dimensional caching-aided ultra-dense network caching system, which consists of a server containing N files, K1K2cache nodes that are arranged neatly on the grid with K1rows and K2columns, and U cacheless users randomly distributed around cache nodes. The server connects to users through an error-free shared-link, and the users can be served by nearby cache nodes and freely retrieve the cache content from it. Our goal is to minimize the transmission load in the worst case while meeting all possible users’ demands. We propose a coded caching scheme based on Maddah-Ali and Niesen scheme (MN scheme), which uses the placement strategy of MN scheme to the cache nodes and uses the delivery strategy of MN scheme multiple rounds for different types of users according to their geometrical locations. We prove that our scheme is order optimal and can greatly improve the transmission performance compared with conventional uncoded caching schemes.

Coded caching is an effective technique to reduce the data transmission load by exploiting the cache contents across the network. However, most coded caching schemes are designed for static networks that consist of only a placement phase and a delivery phase among a constant number of users. In practice, a network maybe dynamic with multiple rounds of placement and delivery phases, and the number of users may vary. In such dynamic networks, a conventional coded caching scheme may lead to the undesired content updates at the users’ cache, which is caused by the newly joining users. This paper proposes a centralized coded caching scheme for dynamic networks that can support multiple rounds and accommodate the newly joining users during this process. It prevents cache contents of the existing users from being updated. It is shown that the proposed scheme can yield a reduced subpacketization level and achieve a good rate-memory tradeoff.

In this paper, we consider a hierarchical distributed multi-task learning (MTL) system where distributed users wish to jointly learn different models orchestrated by a central server with the help of a layer of multiple relays. Since the users need to download different learning models in the downlink transmission, the distributed MTL suffers more severely from the communication bottleneck compared to the single-task learning system. To address this issue, we propose a coded hierarchical MTL scheme that exploits the connection topology and introduces coding techniques to reduce communication loads. It is shown that the proposed scheme can significantly reduce the communication loads both in the uplink and downlink transmissions between relays and the server. Moreover, we provide informationtheoretic lower bounds on the optimal uplink and downlink communication loads, and prove that the gaps between achievable upper bounds and lower bounds are within the minimum number of connected users among all relays.

This paper considers a hierarchical caching system where a server connects with multiple mirror sites, each connecting with a distinct set of users, and both mirror sites and users are equipped with caching memories. Although there already exist works studying this setup and proposing coded caching schemes to reduce transmission loads, two main problems are remained to address: 1) the optimal communication load R1under the uncoded placement for the first layer is still unknown. 2) the previous schemes are based on Maddah-Ali and Niesen’s data placement and delivery, which require high subpacketization level. How to achieve a good tradeoff between transmission loads and subpacketization level for the hierarchical caching system is unclear. In this paper, we aim to address these two problems. We first propose a new combination structure named hierarchical placement delivery array (HPDA), which characterizes the data placement and delivery for a hierarchical caching system. Then we construct two classes of HPDAs, where the first class leads to a scheme achieving the optimal R1for some cases, and the second class requires a smaller subpacketization level at the cost of slight increase in transmission loads.

Coded caching technique is an efficient approach to reduce the transmission load in networks. In this paper, we consider a new widespread caching system called$(K_{1},K_{2},U,r,M,N)$two-dimensional (2D) caching-aided ultra-dense networks (UDNs) with a server containing$N$files,$K_{1}K_{2}$cache nodes arranged neatly on a grid with$K_{1}$rows and$K_{2}$columns, and$U$cache-less users randomly distributed around cache nodes. Each cache node can cache at most$M\leq N$files and has a certain service region by Euclidean distance. The server connects to users through the error-free shared link and the users in the service region of a cache node can freely retrieve all cached contents of this cache node. We aim to design a coded caching scheme for 2D caching-aided UDN system to reduce the transmission load in the worst case while meeting all possible users’ demands. First, we divide all possible users into four classes according to their geographical locations. Then our first order optimal scheme is proposed based on the Maddah-Ali and Niesen scheme. Furthermore, by compressing the transmitted signals of our first scheme based on Maximum Distance Separable (MDS) code, we obtain an improved order optimal scheme with a smaller transmission load.

This work considers the multi-access caching system proposed by Hachem et al., where each user has access to$L$neighboring caches in a cyclic wrap-around fashion. We first propose a placement strategy called the consecutive cyclic placement, which achieves the maximal local caching gain. Then under the consecutive cyclic placement, we derive an upper bound on the coded caching gain of any PDA, thus obtaining a lower bound on the rate of PDA-based coded caching schemes. Finally, we construct a class of PDAs under the consecutive cyclic placement, leading to a multi-access coded caching scheme with linear subpacketization, which achieves the derived lower bound on the rate for some parameters; while for other parameters, the achieved coded caching gain is only 1 less than the derived upper bound on the coded caching gain. Analytical and numerical comparisons of the proposed scheme with existing schemes are provided to validate the performance.

Coded caching is an effective technique to decongest the amount of traffic in the backhaul link. In such a scheme, each file hosted in the server is divided into a number of packets to pursue a low broadcasting rate based on the designed placements at each user’s cache. However, the implementation complexity of this scheme increases with the number of packets. It is important to design a scheme with a small subpacketization level and a relatively low transmission rate. Recently, placement delivery array (PDA) was proposed to address the subpacketization bottleneck of coded caching. This paper investigates the design of PDA from a new perspective, i.e., the injective arc coloring of regular digraphs. It is shown that the injective arc coloring of a regular digraph can yield a PDA with the same number of rows and columns. Based on this, a new class of regular digraphs are defined and the upper bounds on the injective chromatic index of such digraphs are derived. Consequently, four new coded caching schemes with a linear subpacketization level and a relatively small transmission rate are proposed, one of which generalizes the existing scheme for the scenario with a more flexible number of users.

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 this paper, we characterize matroidal entropy functions, i.e., entropy functions in the form h = log v • r, where v ≥ 2 is an integer and r is the rank function of a matroid M. By constructing the variable strength arrays of some matroid operations, we characterized matroidal entropy functions induced by regular matroids and some matroids with the same p-characteristic set as uniform matroid U2,4.

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.

Coded caching is an effective technique to utilize multicasting opportunities to reduce the data transmission load in cached networks. In such a scheme, each file in the data center or library is usually divided into a number of packets to pursue a low broadcasting rate based on the designed placements at each user’s cache. However, the implementation complexity of this scheme increases with the number of packets. It is crucial to design a scheme with a small subpacketization level, while maintaining a relatively low transmission rate. Recently, a combinatorial structure called placement delivery array (PDA) was proposed as an effective tool to design coded caching schemes with a low subpacketization level. This paper proposes a novel PDA construction by selecting proper orthogonal arrays (POAs). It generalizes the existing construction, making it suitable to the scenario with a more flexible memory size. Based on the proposed PDA construction, a new coded caching scheme with the coded placement is further proposed. It is shown that the proposed schemes can yield a lower subpacketization level or transmission rate over the benchmark schemes.

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.

Coded caching is a technique to create coded multicast opportunities for cache-aided networks. In coded caching problem, a fundamental but open question is: what is the minimum transmission load given any fixed subpacketization level? In this paper, we propose a lower bound on the transmission load for any fixed subpacketization by studying the combinatorial structure of corresponding placement delivery array, which was introduced by Yan et al. to reformulate the centralized coded caching schemes. Then we show that some schemes generated by the well known scheme proposed by Maddah-Ali and Niesen (MN), and some scheme generated by Packing (a classic concept of combinatorial design theory), can achieve our lower bound. This implies that our lower bound is tight for some cases.

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.

Coded caching is an emerging technique to reduce the data transmission load during the peak-traffic times. In such a scheme, each file in the data center or library is divided into a number of packets to pursue a low broadcasting rate based on the designed placements at each user’s cache. However, the implementation complexity of this scheme increases with the number of packets. It is crucial to design a scheme with a small subpacketization level, while maintaining a relatively low transmission rate. Recently, a combinatorial structure called placement delivery array (PDA) was proposed as an effective tool to design coded caching schemes with a relatively low subpacketization level. This paper proposes a novel PDA construction by selecting proper orthogonal arrays (POAs), which generalizes the existing construction but with a more flexible memory size. Based on the proposed PDA construction, an effective transform is further proposed to enable a coded caching scheme to achieve a smaller subpacketization level. Moreover, two new coded caching schemes with the coded placement are derived. It is shown that the proposed schemes can yield a lower subpacketization level or transmission rate over the benchmark schemes.

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.

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.

In coded caching system we prefer to design a coded caching scheme with low subpacketization and small transmission rate (i.e., the low implementation complexity and the efficient transmission during the peak traffic times). Placement delivery arrays (PDA) can be used to design code caching schemes. In this article we propose a framework of constructing PDAs via Hamming distance. As an application, two classes of coded caching schemes with linear subpacketizations and small transmission rates are obtained.

Coded caching systems have been widely studied to reduce the data transmission during the peak traffic time. In practice, two important parameters of a coded caching system should be considered, i.e., the transmission rate which is the maximum amount of the data transmission during the peak traffic time, and the subpacketization level, the number of divided packets of each file when we implement a coded caching scheme. Although there exists a tradeoff between transmission rate and subpacketization, we prefer to design a scheme with transmission rate and subpacketization as small as possible since they reflect the transmission efficiency and complexity of the caching scheme, respectively. In this paper, we first characterize a coded caching scheme from the viewpoint of linear algebra and show that designing a linear coded caching scheme is equivalent to constructing three classes of matrices satisfying some rank conditions. Then based on the invariant subspaces in linear algebra and combinatorial design theory, a new class of coded caching schemes over F2is obtained by constructing these three classes of matrices. It turns out that the transmission rate of our new scheme is the same as the scheme construct by Yan et al. (IEEE Trans. Inf. Theory 63, 5821-5833, 2017), but the subpacketization is significantly reduced. Finally by means of these matrices, we show that the minimum storage regenerating codes can also be used to construct coded caching schemes.

In caching system, it is desirable to design a coded caching scheme with the transmission load$R$and subpacketization$F$as small as possible, in order to improve efficiency of transmission in the peak traffic times and to decrease implementation complexity. Yan et al. reformulated the centralized coded caching scheme as designing a corresponding$F\times K$array called placement delivery array (PDA), where$F$is the subpacketization and$K$is the number of users. Motivated by several constructions of PDAs, we introduce a framework for constructing PDAs, where each row is indexed by a row vector of some matrix called row index matrix and each column’s index is labelled by an element of a direct product set. Using this framework, a new scheme is obtained, which can be regarded as a generalization of some previously known schemes. When$K$is equal to${\binom{m}{ t}}q^{t}$for positive integers$m$,$t$with$t < m$and$q\geq 2$, we show that the row index matrix must be an orthogonal array if all the users have the same memory size. Furthermore, the row index matrix must be a covering array if the coded gain is${\binom{m}{ t}}$, which is the maximal coded gain under our framework. Consequently the lower bounds on the transmission load and subpacketization of the schemes are derived under our framework. Finally, using orthogonal arrays as the row index matrix, we obtain two more explicit classes of schemes which have significantly advantages on the subpacketization while the transmission load is equal or close to that of the schemes constructed by Shangguan et al. for the same number of users and memory size.

In coded caching system, we prefer to design a scheme with the rate R and the packet number F of each file split as small as possible since the efficiency of transmission in the peak traffic times increases with the decreasing of R and the realizing complexity increases with the increasing of F. Up to now, almost all of the previously known schemes can be realized by the combinatorial structure which is called placement delivery array (PDA). In this paper, we also study the schemes by means of PDAs. We first show that given the minimum rate, the scheme proposed by Maddah-Ali and Niesen (MN scheme) has the minimum packet number which is too large in practice. From the view point of combinatorial design, two variant MN schemes, which can significantly reduce the packet number by increasing some rate, are obtained. Especially one of these schemes has better performance than the scheme generated by the well known grouping method.

In an (H, r) combination network, a single content library is serving for (rH)users through H relays, where each user has local cache memories and simultaneously accesses a subset of r relays on orthogonal non-interfering and error-free channels. The combinatorial placement delivery array (CPDA in short) can be used to realize a coded caching scheme for combination networks. In this paper, a new algorithm used to realize a scheme for combination networks based on a CPDA is proposed. Based on the fixed CPDA, the scheme realized by our algorithm has smaller subpacketization. Then we focus on directly constructing CPDAs for any positive integers H and r with r <; H and obtain two new classes of CPDAs. Compared with the previously known CPDAs, the schemes realized by our CPDAs have significant advantages on the subpacketization levels with some costing of transmission rates.

Coded caching scheme provides us an effective framework to realize additional coded multicasting gain by exploiting coding into multiple transmitted signals. The goal of coded caching design is to jointly optimize the placement and delivery scheme so as to minimize the amount of transmitted coded signals. However, few research efforts consider multiple-round coded caching design problem, in which fixed and mobile users may coexist in one network, namely different number of active users present in successive rounds. Obviously, such dynamic network configurations may lead to undesired frequent placement caching content updating at user sides, if we assume coded caching scheme for all users in each round separately. Thus how to tailor the coded caching design, such that the frequent caching content updating in the placement phase can be avoided, and simultaneously retaining full caching gain in delivery phase in multiple rounds will become highly desirable. In this paper, by carefully examining the bipartite graph representation of the coded caching scheme, a dynamic centralized coded caching design is proposed on the basis of the concatenating-based placement and the saturating matching based delivery scheme. Our analysis unveils that, the proposed dynamic coded caching scheme can realize the flexible coded multicast, and is order optimal.

Locally repairable codes are desirable for distributed storage systems to improve the repair efficiency. In this paper, a connection between locally repairable codes with multiple disjoint repair sets and packings is derived under the condition that each repair set contains exactly one check symbol. Particularly, conditions under which an optimal locally repairable code corresponds to a packing are also characterized. As an application of this connection, some optimal locally repairable codes can be obtained by packings. Specifically, two constructions of locally repairable codes are proposed which not only generalize some known explicit constructions but also give optimal locally repairable codes with flexible new parameters.

Coded caching, which could significantly reduce the maximum amount of transmission rate during the peak traffic times in wireless network, has been widely studied recently. Apart from the transmission rate, sub-packetization F reflecting the implementation complexity, is also concerned in coded caching. The grouping method proposed by Shanmugam et al. is wellknown and widely used to reduce the sub-packetization level of the coded caching problem. In this paper, we propose a concatenating construction method for coded caching schemes, which generalizes the grouping method. Moreover, we demonstrate the advantage of our method in reducing the transmission rate over the grouping method. In particular, some new explicit schemes are obtained from previously known schemes. From one of these schemes, we can derive all the results by Tang and Ramamoorthy as special cases. Furthermore, the analysis and comparison of these new schemes are also performed.

Coded caching scheme recently has become quite popular in the wireless network, since the maximum transmission amount R reduces effectively during the peak-traffic times. To realize a coded caching scheme, each file must be divided into F packets, which usually increases the computation complexity of a coded caching scheme. So we prefer to design a scheme with R and F as small as possible in practice. However, there exists a tradeoff between R and F. In this paper, we generalize the schemes constructed by Shangguan et al. (IEEE TRANSACTIONS ON INFORMATION THEORY, 64, 5755-5766, 2018) and Yan et al. (IEEE TRANSACTIONS ON INFORMATION THEORY 63, 5821-5833, 2017), respectively. These two classes of schemes have a wider range of application due to the more flexible memory size than the original ones. By comparing with the previous known deterministic schemes, our new schemes have advantages on R or F.

Ji et al. (IEEE TRANSACTIONS ON INFORMATION THEORY, 62(2): 849-869, 2016) first studied coded caching in device-to-device (D2D) networks, and proposed a D2D coded caching scheme, which is referred to as the JCM scheme. In practice, we prefer to design a scheme with its two important targets, i.e., the rate (the maximal total amount of transmission) and packet number F, as small as possible. In this paper, we first propose a simple array called D2D placement delivery array (DPDA) to characterize the placement phase and the delivery phase in D2D networks. Consequently, some D2D coded caching schemes can be realized by an appropriate DPDA. Second, a lower bound on the rate of a DPDA is derived. And, we show that the JCM scheme achieves our lower bound. However, it is well known that its packet number F increases exponentially with the number of users K. So, we propose two classes of new schemes by constructing DPDAs. One reduces the packet number exponentially with K compared with the JCM scheme while keeping the rate near to our lower bound. The other further reduces F to increasing sub-exponentially with K.

Parent-identifying schemes provide a way to identify causes from effects for some information systems, such as digital fingerprinting and group testing. In this paper, we consider the combinatorial structures for parent-identifying schemes. First, we establish an equivalent relationship between the parent-identifying schemes and forbidden configurations. Based on this relationship, we derive the probabilistic existence lower bounds for two related combinatorial structures, that is, t-parent-identifying set systems (t-IPPS) and t-multimedia parent-identifying codes (t-MIPPC), which are used in broadcast encryption and multimedia fingerprinting, respectively. The probabilistic lower bound for the maximum size of a t-IPPS has the asymptotically optimal order of magnitude in many cases, and that for t-MIPPC provides the asymptotically optimal code rate when t = 2 and the best known asymptotic code rate when t ≥ 3. Furthermore, we analyze the structure of 2-IPPS and prove some bounds for certain cases.

This paper presents a reference sharing mechanism-based self-embedding watermarking scheme. The host image is embedded with watermark bits including the reference data for content recovery and the authentication data for tampering location. The special encoding matrix derived from the generator matrix of selected systematic Maximum Distance Separable (MDS) code is adopted. The reference data is generated by encoding all the representative data of the original image blocks. On the receiver side, the tampered image blocks can be located by the authentication data. The reference data embedded in one image block can be shared by all the image blocks to restore the tampered content. The tampering coincidence problem can be avoided at the extreme. The maximal tampering rate is deduced theoretically. Experimental results show that, as long as the tampering rate is less than the maximal tampering rate, the content recovery is deterministic. The quality of recovered content does not decrease with the maximal tampering rate.

Caching is a promising solution to satisfy the ever-increasing demands for the multi-media traffics. In caching networks, coded caching is a recently proposed technique that achieves significant performance gains over the uncoded caching schemes. However, to implement the coded caching schemes, each file has to be split into F packets, which usually increases exponentially with the number of users K. Thus, designing caching schemes that decrease the order of F is meaningful for practical implementations. In this paper, by reviewing the Ali-Niesen caching scheme, the placement delivery array (PDA) design problem is first formulated to characterize the placement issue and the delivery issue with a single array. Moreover, we show that, through designing appropriate PDA, new centralized coded caching schemes can be discovered. Second, it is shown that the Ali-Niesen scheme corresponds to a special class of PDA, which realizes the best coding gain with the least F. Third, we present a new construction of PDA for the centralized coded caching system, wherein the cache size M at each user (identical cache size is assumed at all users) and the number of files N satisfies M/N = 1/q or (q - 1)/q (q is an integer, such that q ≥ 2). The new construction can decrease the required F from the order O(eK·((M/N) ln(N/M)+(1-(M/N)) ln (N/(N-M))) of Ali-Niesen scheme to O(eK·(M/N) ln(N/M)) or O(eK·(1-(M/N)) ln(N/(N-M))), respectively, while the coding gain loss is only 1.

Let $$\mathbb{C }$$ be a code of length $$n$$ over an alphabet of $$q$$ letters. The descendant code $$\mathsf{desc}(\mathbb C _0)$$ of $$\mathbb C _0 = \{\mathbf{c}^1, \mathbf{c}^2, \ldots , \mathbf{c}^t\} \subseteq \mathbb{C }$$ is defined to be the set of words $$\mathbf{x} = (x_1, x_2, \ldots ,x_n)$$ such that $$x_i \in \{c^1_i, c^2_i, \ldots , c^t_i\}$$ for all $$i=1, \ldots , n$$ . $$\mathbb{C }$$ is a $$\overline{t}$$ -separable code if for any two distinct $$\mathbb{C }_1, \mathbb{C }_2 \subseteq \mathbb{C }$$ such that $$|\mathbb{C }_1| \le t$$ , $$|\mathbb{C }_2| \le t$$ , we always have $$\mathsf{desc}(\mathbb{C }_1) \ne \mathsf{desc}(\mathbb{C }_2)$$ . The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let $$M(\overline{t},n,q)$$ be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for $$M(\overline{2},2,q)$$ by a graph theoretical approach, and a new lower bound for $$M(\overline{2},2,q)$$ by deleting suitable points and lines from a projective plane, which coincides with the improved upper bound in some places. This corresponds to the bounds of maximum size of bipartite graphs with girth $$6$$ and a construction of such maximal bipartite graphs.

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia information. Separable codes can be used to construct fingerprints resistant to the averaging collusion attack on multimedia contents. In this paper, we investigate -separable codes from a combinatorial point of view. We first derive several upper bounds on the sizes of -separable codes, and then turn our attention to the constructions of optimal -separable codes with short length. Two infinite families of optimal -separable codes of length 2 are constructed from projective planes, and all optimal -separable codes of length 3 are explicitly constructed by means of difference matrices. These optimal -separable codes with short length can be used to construct good -separable codes with long length by a known composition construction.

Seven infinite classes of relative difference families with variable block sizes are presented explicitly. In particular, a balanced (gv,g,K,1)-DF withg=Σk∈K[(k2-k)/2] is explicitly given for: (i)K={3,4,5} and everyvcoprime to 6; (ii)K={3,4,6}, {3,5,6} or {3,4,5,6} and everyvcoprime to 30. As far as the authors are aware, these difference families can be viewed as the first explicit constructions of infinite classes of optimal variable-weight optical orthogonal codes with more than two weights. It is observed, however, that there are infinitely many values ofvfor which an optimal (v,W,1,Q) -OOC exists, whatever the set of weightsWand the weight distribution sequenceQare.

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia information. AND anti-collusion codes can be used to construct fingerprints resistant to collusion attacks on multimedia contents. In this paper, we first investigate AND anti-collusion codes and related detection algorithms from a combinatorial viewpoint, and then introduce a new concept of logical anti-collusion code to improve the traceability of multimedia fingerprinting. It reveals that frameproof codes have traceability for multimedia contents. Relationships among anti-collusion codes and other structures related to fingerprinting are discussed, and constructions for both AND anti-collusion codes and logical anti-collusion codes are provided.