Source author record

Minquan Cheng

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

19works
4topics
4close collaborators

Published work

19 publications

preprint2026arXiv

A Construction Framework of Coded Caching Scheme for Multi-Access MISO Systems via Knapsack Problem

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 NN files, ΛΛ cache nodes, and KK cache-less users, where each user can access a unique subset of rr cache nodes. The server is equipped with LL 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 00--11 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}\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. ```

preprint2026arXiv

A New Construction Structure on Coded Caching with Linear Subpacketization: Non-Half-Sum Latin Rectangle

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 KK. 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=KF=K (i.e., the construction via NHSDP) to a broader scenario with F=O(K)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.

preprint2026arXiv

A New Construction Structure on MISO Coded Caching with Linear Subpacketization: Half-Sum Disjoint Packing

In the (L,K,M,N)(L,K,M,N) cache-aided multiple-input single-output (MISO) broadcast channel (BC) system, the server is equipped with LL antennas and communicates with KK single-antenna users through a wireless broadcast channel where the server has a library containing NN files, and each user is equipped with a cache of size MM 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 LL, MM, and NN, 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 FF. 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=KF=K (i.e., FF grows linearly with KK) by investigating MAPDAs. Specifically, based on the framework of Latin squares, we transform the design of MAPDA with F=KF=K into the construction of a combinatorial structure called the LL-half-sum disjoint packing (HSDP). It is worth noting that a 11-HSDP is exactly the concept of NHSDP, which is used to generate the shared-link coded caching scheme with F=KF=K. By constructing LL-HSDPs, we obtain a class of new schemes with F=KF=K. Finally, theoretical and numerical analyses show that our LL-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.

preprint2026arXiv

Distributed Linearly Separable Computation with Arbitrary Heterogeneous Data Assignment

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.

preprint2026arXiv

Multiaccess Coded Caching with Heterogeneous Retrieval Costs

The multiaccess coded caching (MACC) system, as formulated by Hachem {\it et al.}, consists of a central server with a library of NN files, connected to KK cache-less users via an error-free shared link, and KK cache nodes, each equipped with cache memory of size MM files. Each user can access LL 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 LL 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.

preprint2026arXiv

Placement Delivery Array for Cache-Aided MIMO Systems

We consider a (G,L,K,M,N)(G,L,K,M,N) cache-aided multiple-input multiple-output (MIMO) network, where a server equipped with LL antennas and a library of NN equal-size files communicates with KK users, each equipped with GG antennas and a cache of size MM 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⌈L/G⌉}\min\{KG, Gt+G\lceil L/G \rceil\}, where t=KM/Nt=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.

preprint2022arXiv

Coded Caching for Two-Dimensional Multi-Access Networks

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 NN files, K1×K2K_1\times K_2 cache-nodes with MM files located at a grid with K1K_1 rows and K2K_2 columns, and K1×K2K_1\times K_2 cache-less users where each user is connected to L2L^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 K1K_1 and K2K_2 are divisible by LL. By partitioning the cache-nodes and users into L2L^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⁡{K1,K2}>L\min\{K_1,K_2\}>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.

preprint2022arXiv

Design of Coded Caching Schemes with Linear Subpacketizations Based on Injective Arc Coloring of Regular Digraphs

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 transmission rate based on the delicate design of contents cached into users and broadcast messages. However, the implementation complexity of this scheme increases with the number of packets. It is desirable 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 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, some new coded caching schemes with a linear subpacketization level and a small transmission rate are proposed, one of which generalizes the existing scheme for the scenario with a more flexible number of users.

preprint2022arXiv

Design of Placement Delivery Arrays for Coded Caching with Small Subpacketizations and Flexible Memory Sizes

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 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 as the number of packets increases. It is crucial to design a scheme with a small subpacketization level, while maintaining a relatively low transmission rate. It is known that the design of caches in users (i.e., the placement phase) and broadcasting (i.e., the delivery phase) can be unified in one matrix, namely the placement delivery array (PDA). This paper proposes a novel PDA construction by selecting proper orthogonal arrays (POAs), which generalizes some known constructions but with a more flexible memory size. Based on the proposed PDA construction, an effective transformation is further proposed to enable a coded caching scheme to have a smaller subpacketization level. Moreover, two new coded caching schemes with the coded placement are considered. It is shown that the proposed schemes yield a lower subpacketization level and transmission rate over some existing schemes.

preprint2022arXiv

Multi-access Coded Caching with Optimal Rate and Linear Subpacketization under PDA and Consecutive Cyclic Placement

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 the optimal coded caching gain from the perspective of Placement Delivery Array (PDA), thus obtaining a lower bound on the rate of PDA. Finally, under the consecutive cyclic placement, we construct a class of PDA, leading to a multi-access coded caching scheme with linear subpacketization, which achieves our derived lower bound for some parameters; while for other parameters, the achieved coded caching gain is only 1 less than the optimal one. Analytical and numerical comparisons of the proposed scheme with existing schemes are provided to validate the performance.

preprint2022arXiv

On the Optimal Memory-Load Tradeoff of Coded Caching for Location-Based Content

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. 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 NN location-based files (e.g., High-Definition maps), KK edge cache nodes located at different regions, and KK 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. For this novel coded caching problem, we propose a highly non-trivial converse bound under uncoded cache placement, 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 33. Finally, we extend the coded caching problem for location-based content to the multiaccess coded caching topology originally proposed by Hachem et al., where each user is connected to LL nearest cache nodes. When L≥2L \geq 2, we characterize the exact optimality on the worst-case load.

preprint2020arXiv

Coded Caching Schemes with Linear Subpacketizations

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

preprint2020arXiv

New coded caching schemes from placement delivery arrays

Coded caching schemes with low subpacketization and small transmission rate are desirable in practice due to the requirement of low implementation complexity and efficiency of the transmission. Placement delivery arrays (PDA in short) can be used to generate coded caching schemes. However, many known coded caching schemes have large memory ratios. In this paper, we realize that some schemes with low subpacketization generated by PDAs do not fully use the users' caching content to create multicasting opportunities and thus propose to overcome this drawback. As an application, we obtain two new schemes with low subpacketizations, which have significantly advantages on the memory ratio and transmission rate compared with the original scheme.

preprint2020arXiv

On Secure Coded Caching via Combinatorial Method

Coded caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the user's local cache memory without knowledge of later demands. The goal of coded caching design is to minimize the transmission rate and the subpacketization. In practice the demand for each user is sensitive since one can get the other users' preferences when it gets the other users' demands. The first coded caching scheme with private demands was proposed by Wan et al. However the transmission rate and the subpacketization of their scheme increase with the file number stored in the library. In this paper we consider the following secure coded caching: prevent the wiretappers from obtaining any information about the files in the server and protect the demands from all the users in the delivery phase. We firstly introduce a combinatorial structure called secure placement delivery array (SPDA in short) to realize a coded caching scheme for our security setting. Then we obtain three classes of secure schemes by constructing SPDAs, where one of them is optimal. It is worth noting that the transmission rates and the subpacketizations of our schemes are independent to the file number. Furthermore, comparing with the previously known schemes with the same security setting, our schemes have significantly advantages on the subpacketizations and for some parameters have the advantage on the transmission rates.

preprint2015arXiv

Bounds and Constructions for 3‾\overline{3}-Separable Codes with Length 33

Separable codes were introduced to provide protection against illegal redistribution of copyrighted multimedia material. Let C\mathcal{C} be a code of length nn over an alphabet of qq letters. The descendant code desc(C0){\sf desc}(\mathcal{C}_0) of C0={c1,c2,…,ct}⊆C\mathcal{C}_0 = \{{\bf c}_1, {\bf c}_2, \ldots, {\bf c}_t\} \subseteq {\mathcal{C}} is defined to be the set of words x=(x1,x2,…,xn)T{\bf x} = (x_1, x_2, \ldots,x_n)^T such that xi∈{c1,i,c2,i,…,ct,i}x_i \in \{c_{1,i}, c_{2,i}, \ldots, c_{t,i}\} for all i=1,…,ni=1, \ldots, n, where cj=(cj,1,cj,2,…,cj,n)T{\bf c}_j=(c_{j,1},c_{j,2},\ldots,c_{j,n})^T. C\mathcal{C} is a t‾\overline{t}-separable code if for any two distinct C1,C2⊆C\mathcal{C}_1, \mathcal{C}_2 \subseteq \mathcal{C} with ∣C1∣≤t|\mathcal{C}_1| \le t, ∣C2∣≤t|\mathcal{C}_2| \le t, we always have desc(C1)≠desc(C2){\sf desc}(\mathcal{C}_1) \neq {\sf desc}(\mathcal{C}_2). Let M(t‾,n,q)M(\overline{t},n,q) denote the maximal possible size of such a separable code. In this paper, an upper bound on M(3‾,3,q)M(\overline{3},3,q) is derived by considering an optimization problem related to a partial Latin square, and then two constructions for 3‾\overline{3}-SC(3,M,q)(3,M,q)s are provided by means of perfect hash families and Steiner triple systems.

preprint2014arXiv

Codes with the Identifiable Parent Property for Multimedia Fingerprinting

Let C{\cal C} be a qq-ary code of length nn and size MM, and C(i)={c(i) ∣ c=(c(1),c(2),…,c(n))T∈C}{\cal C}(i) = \{{\bf c}(i) \ | \ {\bf c}=({\bf c}(1), {\bf c}(2), \ldots, {\bf c}(n))^{T} \in {\cal C}\} be the set of iith coordinates of C{\cal C}. The descendant code of a sub-code C′⊆C{\cal C}^{'} \subseteq {\cal C} is defined to be C′(1)×C′(2)×⋯×C′(n){\cal C}^{'}(1) \times {\cal C}^{'}(2) \times \cdots \times {\cal C}^{'}(n). In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or tt-MIPPC(n,M,q)(n, M, q), so that given the descendant code of any sub-code C′{\cal C}^{'} of a multimedia tt-IPP code C{\cal C}, one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in C′{\cal C}^{'}. We first derive a general upper bound on the size MM of a multimedia tt-IPP code, and then investigate multimedia 33-IPP codes in more detail. We characterize a multimedia 33-IPP code of length 22 in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia 33-IPP code of length 22, and construct several infinite families of (asymptotically) optimal multimedia 33-IPP codes of length 22.

preprint2014arXiv

Multimedia IPP Codes with Efficient Tracing

Binary multimedia identifiable parent property codes (binary tt-MIPPCs) are used in multimedia fingerprinting schemes where the identification of users taking part in the averaging collusion attack to illegally redistribute content is required. In this paper, we first introduce a binary strong multimedia identifiable parent property code (binary tt-SMIPPC) whose tracing algorithm is more efficient than that of a binary tt-MIPPC. Then a composition construction for binary tt-SMIPPCs from qq-ary tt-SMIPPCs is provided. Several infinite series of optimal qq-ary tt-SMIPPCs of length 22 with t=2,3t = 2, 3 are derived from the relationships among tt-SMIPPCs and other fingerprinting codes, such as t‾\overline{t}-separable codes and tt-MIPPCs. Finally, combinatorial properties of qq-ary 22-SMIPPCs of length 33 are investigated, and optimal qq-ary 22-SMIPPCs of length 33 with q≡0,1,2,5(mod6)q \equiv 0, 1, 2, 5 \pmod 6 are constructed.

preprint2014arXiv

Strongly Separable Codes

Binary tt-frameproof codes (tt-FPCs) are used in multimedia fingerprinting schemes where the identification of authorized users taking part in the averaging collusion attack is required. In this paper, a binary strongly tˉ\bar{t}-separable code (tˉ\bar{t}-SSC) is introduced to improve such a scheme based on a binary tt-FPC. A binary tˉ\bar{t}-SSC has the same traceability as a binary tt-FPC but has more codewords than a binary tt-FPC. A composition construction for binary tˉ\bar{t}-SSCs from qq-ary tˉ\bar{t}-SSCs is described, which stimulates the research on qq-ary tˉ\bar{t}-SSCs with short length. Several infinite series of optimal qq-ary 2ˉ\bar{2}-SSCs of length 22 are derived from the fact that a qq-ary 2ˉ\bar{2}-SSC of length 22 is equivalent to a qq-ary 2ˉ\bar{2}-separable code of length 22. Combinatorial properties of qq-ary 2ˉ\bar{2}-SSCs of length 33 are investigated, and a construction for qq-ary 2ˉ\bar{2}-SSCs of length 33 is provided. These 2ˉ\bar{2}-SSCs of length 33 have more than 12.5%12.5\% codewords than 22-FPCs of length 33 could have.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.