Motivated by their applications in DNA-based storage systems, codes capable of correcting consecutive deletions have attracted significant attention. An important class of such codes consists of those that can correct multiple consecutive deletion errors, commonly referred to as multiple $b$-burst deletion-correcting codes. In this paper, we investigate the fundamental limits of multiple $b$-burst deletion-correcting codes. Specifically, we first characterize several structural properties of the associated deletion balls. Then, leveraging these properties, we derive several upper bounds and a combinatorial lower bound on the maximum size of such codes. As a consequence, our bounds improve upon the previously known results for general parameter regimes and are shown to be asymptotically optimal for certain cases.

In this paper, we study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at mostrfiles. We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds. For graph-based systems, we determine the exact PIR capacity for path graphs and improve upon existing results for complete bipartite graphs and complete graphs. For multigraph-based systems, we propose a PIR scheme that leverages the symmetry of the underlying graph-based construction, yielding a capacity lower bound for such multigraphs. Furthermore, we establish several general upper and lower bounds on the PIR capacity of multigraphs, which are tight in certain cases.

In large-scale distributed storage systems, erasure coding is employed to ensure reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to significant storage savings without compromising reliability. Such adaptations, known ascode conversions, motivate the design ofconvertible codes, which enable efficient transformations between codes of different parameters. In this work, we study the setting in which λ codewords of an initial [nI=kI+rI,kI] MDS code are merged into a single codeword of a final [nF= λkI+rF,kF= λkI] MDS code. We begin by presenting three constructions that achieve optimalaccess cost, defined as the total number of disks accessed during the conversion process. The first two constructions apply when λ ≤rIand impose specific divisibility conditions onrIand the field sizeq. These schemes minimize both the per-symbol and the overall access cost. The third construction, which builds on a prior scheme by Kong, achieves minimal access cost while supporting arbitrary parameter regimes. All three constructions require field sizes that are linear in the final code length, and notably, the third construction achieves a field size that matches the lower bound implied by the MDS conjecture in almost all cases. In addition, we propose a construction that optimizes thebandwidth cost, defined as the total number of symbols transmitted during conversion. This scheme is a refinement of Maturana and Rashmi’s bandwidth-optimal construction based on the piggybacking framework, and achieves reduced sub-packetization.The code will be available at https://github.com/ZhilongNiu/SDMoMFE.

In this work, we consider the problem of variable packet-error coding, which emerges in network communication scenarios where a source transmits information to a destination through multiple disjoint paths. The objective is to design codes with dynamic error-correcting capabilities that adapt to a varying number of errors. Specifically, we first provide a bound on the rate-distortion trade-off for general variable packet-error coding schemes. Then, we present a construction that uses higherorder MDS codes and provides a variable packet-error coding scheme that achieves a better rate-distortion trade-off compared to known results for general parameter regimes.

In large-scale distributed storage systems, erasure coding provides reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to storage savings, without compromising reliability. During such adaptations (also called code conversions), data encoded with multiple codewords of an initial [$n^{I}, k^{I}$] code are transformed into multiple codewords of a final$\left[n^{F}, k^{F}\right]$code. The convertible codes framework aims to design initial and final codes to enable resource-efficient conversions. In this paper, we study the scenario where$\lambda \geq 2$codewords of an initial$\left[n^{I}=k^{I}+r^{I}, k^{I}\right]$MDS code are merged into a single codeword of a final$\left[n^{F}=\lambda k^{I}+r^{F}, k^{F}=\lambda k^{I}\right]$MDS code. Some initial code symbols are retained in the final codeword, while others are newly generated. The access cost is the total number of symbols read or written during the conversion procedure to produce new symbols. In this paper, we present three convertible code constructions. The first two require$\lambda \leq r^{I}$and impose certain divisibility conditions on$r^{I}$and the field size$q$. However, they minimize the access cost incurred for generating each new symbol individually and for all symbols cumulatively. The third construction, a modification of an earlier construction by Kong, minimizes the cumulative access cost and works for all parameters. All the code constructions require field sizes linear in the block length of the final code and achieve the smallest known field sizes across MDS convertible codes in the literature.

Abstract. Incidence problems between geometric objects is a key area of focus in the field of discrete geometry. Among them, the study of incidence problems over finite fields has received a considerable amount of attention in recent years. In this paper, by characterizing the singular values and singular vectors of the corresponding incidence matrix through group algebras, we prove a bound on the number of incidences between points and varieties of a certain form over finite fields. Our result leads to a new incidence bound for points and flats in finite geometries, which improves previous results for certain parameter regimes. As another application of our point-variety incidence bound, we extend a result on pinned distance problems by Phuong, Thang, and Vinh, and independently by Cilleruelo et al. under a weaker condition.

Error-correcting codes resilient to synchronization errors such as insertions and deletions are known as insdel codes. In this paper, we present several new combinatorial upper and lower bounds on the maximum size ofq-ary insdel codes. Our main upper bound is a sphere-packing bound obtained by solving a linear programming (LP) problem. It improves upon previous results for cases when the distancedor the alphabet sizeqis large. Our first lower bound is derived from a connection between insdel codes and matchings in special hypergraphs. This lower bound, together with our upper bound, shows that for fixed block lengthnand edit distanced, whenqis sufficiently large, the maximum size of insdel codes is$ \frac {q^{n-\frac {d}{2}+1}}{\binom {n}{\frac {d}{2}-1}}(1 \pm o(1))$. The second lower bound refines Alon et al.’s recent logarithmic improvement on Levenshtein’s GV-type bound and extends its applicability to largeqandd.

Batch codes are a type of codes specifically designed for coded distributed storage systems and private information retrieval protocols. These codes have received much attention in recent years due to their ability to enable efficient and secure storage in distributed systems. In this paper, we study an array code version of the batch codes, which is called the batch array code (BAC). Under the setting of BAC, each node stores a bucket containing multiple code symbols and responds with a locally computed linear combination of the symbols in its bucket during the recovery of a requested symbol. We demonstrate that BACs can support the same type of requests as the original batch codes but with reduced redundancy. Specifically, we establish information theoretic lower bounds on the code lengths and provide several code constructions that confirm the tightness of the lower bounds for certain parameter regimes.

Modern large-scale distributed storage systems use erasure codes to protect against node failures with low storage overhead. In practice, the failure rate and other factors of storage devices in the system may vary significantly over time, and leads to changes of the ideal code parameters. To maintain the storage efficiency, this requires the system to adjust parameters of the currently used codes. The changing process of code parameters on encoded data is called code conversion. As an important class of storage codes, locally repairable codes (LRCs) can repair any codeword symbol using a small number of other symbols. This feature makes LRCs highly efficient for addressing single node failures in the storage systems. In this paper, we investigate the code conversions for locally repairable codes in the merge regime. We establish a lower bound on the access cost of code conversion for general LRCs and propose a construction of LRCs that can perform code conversions with access cost matching this bound. This construction yields a family of LRCs with optimal conversion processes over a field size linear in the code length. As a special case, it provides a family of RS codes with optimal conversion processes, which could be of particular practical interest.

Private information retrieval (PIR) codes and batch codes are two important types of codes that are designed for coded distributed storage systems and private information retrieval protocols. These codes have been the focus of much attention in recent years, as they enable efficient and secure storage and retrieval of data in distributed systems. In this paper, we introduce a new class of codes called (s, t)-batch codes. These codes are a type of storage codes that can handle any multi-set oftrequests, comprised ofsdistinct information symbols. Importantly, PIR codes and batch codes are special cases of (s, t)-batch codes. The main goal of this paper is to explore the relationship between the number of redundancy symbols and the (s, t)-batch code property. Specifically, we establish a lower bound on the number of redundancy symbols required and present several constructions of (s, t)-batch codes. Furthermore, we extend this property to the case where each request is a linear combination of information symbols, which we refer to asfunctional(s, t)-batch codes.

As a crucial technique for integrated circuits (IC) test response compaction, X-compact employs a special kind of codes called X-codes for reliable compressions of the test response in the presence of unknown logic values (Xs). From a combinatorial view point, Fujiwara and Colbourn introduced an equivalent definition of X-codes and studied X-codes of small weights that have good detectability and X-tolerance. An (m,n,d,x) X-code is an m× n binary matrix with column vectors as its codewords. The parametersd,xcorrespond to the test quality of the code. In this paper, bounds and constructions for constant weighted X-codes are investigated. First, we obtain a general result on the maximum number of codewords n for an (m,n,d,x) X-code of weight w, and we further improve this lower bound for the case with x=2 and w=3 through the probabilistic method. Then, using tools from additive combinatorics and finite fields, we present some explicit constructions for constant weighted X-codes with d=3,7 and x=2, which are optimal for the case when d=3, w=4 and nearly optimal for the case when d=3, w=3. We also consider a special class of X-codes introduced by Fujiwara and Colbourn and improve the best known lower bound on the maximum number of codewords for this kind of X-codes.

As an important coding scheme in modern distributed storage systems, locally repairable codes (LRCs) have attracted a lot of attentions from perspectives of both practical applications and theoretical research. As a major topic in the research of LRCs, bounds and constructions of the corresponding optimal codes are of particular concerns. In this work, codes with (r,δ)-locality which have optimal minimal distance w.r.t. the bound given by Prakash et al. are considered. Through parity-check matrix approach, constructions of both optimal (r,δ)-LRCs with all symbol locality ( (r,δ)a-LRCs) and optimal (r,δ)-LRCs with information locality ( (r,δ)i-LRCs) are provided. As a generalization of a work of Xing and Yuan, these constructions are built on a connection between sparse hypergraphs and optimal (r,δ)-LRCs. With the help of constructions of large sparse hypergraphs, the lengths of codes obtained from our construction can be super-linear in the alphabet size. This improves upon previous constructions when the minimal distance of the code is at least 3δ+1. As two applications, optimal H-LRCs with super-linear lengths and GSD codes with unbounded lengths are also constructed.