A $t$-all-symbol PIR code and a $t$-all-symbol batch code of dimension $k$ consist of $n$ servers storing linear combinations of $k$ information symbols with the following recovery property: any symbol stored by a server can be recovered from $t$ pairwise disjoint subsets of servers. In the batch setting, we further require that any multiset of size $t$ of stored symbols can be recovered from~$t$ disjoint subsets of servers. This framework unifies and extends several well-known code families, including one-step majority-logic decodable codes, (functional) PIR codes, and (functional) batch codes. In this paper, we determine the minimum code length for some small values of $k$ and $t$, characterize structural properties of codes attaining this optimum, and derive bounds that show the trade-offs between length, dimension, minimum distance, and $t$. In addition, we study MDS codes and the simplex code, demonstrating how these classical families fit within our framework, and establish new cases of an open conjecture from \cite{YAAKOBI2020} concerning the minimal $t$ for which the simplex code is a $t$-functional batch code.

Distributed storage systems must handle both data heterogeneity, arising from non-uniform access demands, and device heterogeneity, caused by time-varying node reliability. In this paper, we study convertible codes, which enable the transformation of one code into another with minimum cost in the merge regime, addressing the latter. We derive general lower bounds on the read and write costs of linear code conversion, applicable to arbitrary linear codes. We then focus on Reed-Muller codes, which efficiently handle data heterogeneity, addressing the former issue, and construct explicit conversion procedures that, for the first time, combine both forms of heterogeneity for distributed data storage.

We develop a duality theory of locally recoverable codes (LRCs) and apply it to establish a series of new bounds on their parameters. We introduce and study a refined notion of weight distribution that captures the code's locality. Using a duality result analogous to a MacWilliams identity, we then derive an LP-type bound that improves on the best known bounds in several instances. Using a dual distance bound and the theory of generalized weights, we obtain non-existence results for optimal LRCs over small fields. In particular, we show that an optimal LRC must have both minimum distance and block length relatively small compared to the field size.

The performance of Reed–Solomon codes (RS codes, for short) in the presence of insertion and deletion errors has attracted growing attention in recent literature. In this work, we further study this intriguing mathematical problem, focusing on two regimes. First, we study the question of how wellfull-lengthRS codes perform against insertions and deletions. For 2-dimensional RS codes, we provide a complete characterization of codes that cannot correct even a single insertion or deletion. Furthermore, we prove that for sufficiently large field sizeq, nearly all full-length 2-dimensional RS codes can correct up to (1 - δ)qinsertion and deletion errors for any 0k≥ 2, there exists a full-lengthk-dimensional RS code capable of correctingq/(10k) insertion and deletion errors, providedqis large enough. Second, we focus on rate-1/2 RS codes that can correct a single insertion or deletion error. We present a polynomial-time algorithm that constructs such codes over fields of sizeq= Θ(k4). This result matches the existential bound given in [1].

In this paper, we study theRandom Access Problemin DNA storage, which addresses the challenge of retrieving a specific information strand from a DNA-based storage system. In this framework, the data is represented bykinformation strands which represent the data and are encoded intonstrands using a linear code. Then, each sequencing read returns one encoded strand which is chosen uniformly at random. The goal under this paradigm is to design codes that minimize the expected number of reads required to recover an arbitrary information strand. We fully solve the case whenk= 2, showing that the best possible code attains a random access expectation of 1 + 2/ √2+1 ≈ 0.914 · 2 forqlarge enough. Moreover, we extend a previous construction, originally developed fork= 3, to arbitrary values ofk. Our construction usesBk−1sequences overZq−1, that always exist over large finite fields. We show that for everyk≥ 4, this generalized construction outperforms all previous constructions in terms of reducing the random access expectation.

DNA labelingis a tool in molecular biology and biotechnology to visualize, detect, and study DNA at the molecular level. In this process, a DNA molecule islabeledby a set of specific patterns, referred to aslabels, and is then imaged. The resulting image is modeled as an (ℓ + 1)-ary sequence, where ℓ is the number of labels, in which any non-zero symbol indicates the appearance of the corresponding label in the DNA molecule. Thelabeling capacityrefers to the maximum information rate that can be achieved by the labeling process for any given set of labels. The main goal of this paper is to study the minimum number of labels of the same length required to achieve the maximum labeling capacity of 2 for DNA sequences or log2qfor an arbitrary alphabet of sizeq. The solution to this problem requires the study of path unique subgraphs of the de Bruijn graph with the largest number of edges. We provide upper and lower bounds on this value. We draw new connections to existing literature that let us prove an asymptotic result as the label length tends to infinity.

We investigate the fundamental limits of the recently proposedrandom access coverage depth problemfor DNA data storage. Under this paradigm, it is assumed that the user information consists ofkinformation strands, which are encoded intonstrands via a generator matrixG. During the sequencing process, the strands are read uniformly at random, as each strand is available in a large number of copies. In this context, the random access coverage depth problem refers to the expected number of reads (i.e., sequenced strands) required to decode a specific information strand requested by the user. This problem heavily depends on the generator matrixG, and besides computing the expectation for different choices ofG, the goal is to construct matrices that minimize the maximum expectation over all possible requested information strands, denoted byTmax(G). In this paper, we introduce new techniques to investigate the random access coverage depth problem, capturing its combinatorial nature and identifying the structural properties of generator matrices that are advantageous. We establish two general formulas to determineTmax(G) for arbitrary generator matrices. The first formula depends on the linear dependencies between columns ofG, whereas the second formula takes into account recovery sets and their intersection structure. We also introduce the concept ofrecovery balanced codesand provide three sufficient conditions for a code to be recovery balanced. These conditions can be used to computeTmax(G) for various families of codes, such as MDS, simplex, Hamming, and binary Reed-Muller codes. Additionally, we study the performance of modified systematic MDS and simplex matrices, showing that the best results forTmax(G) are achieved with a specific combination of encoded strands and replication of the information strands.

We investigate the fundamental limits of the recently proposed random access coverage depth problem for DNA data storage. Under this paradigm, it is assumed that the user information consists of$k$information strands, which are encoded into$n$strands via some generator matrix$G$. In the sequencing process, the strands are read uniformly at random, since each strand is available in a large number of copies. In this context, the random access coverage depth problem refers to the expected number of reads (i.e., sequenced strands) until it is possible to decode a specific information strand, which is requested by the user. The goal is to minimize the maximum expectation over all possible requested information strands, and this value is denoted by$T_{\max}(G)$. This paper introduces new techniques to investigate the random access coverage depth problem, which capture its combinatorial nature. We establish two general formulas to find$T_{\max}(G)$for arbitrary matrices. We introduce the concept of recovery balanced codes and combine all these results and notions to compute$T_{\max}(G)$for MDS, simplex, and Hamming codes. We also study the performance of modified systematic MDS matrices and our results show that the best results for$T_{\max}(G)$are achieved with a specific mix of encoded strands and replication of the information strands.

DNA labeling is a tool in molecular biology and biotechnology to visualize, detect, and study DNA at the molec-ular level. In this process, a DNA molecule is labeled by a set of specific patterns, referred to as labels, and is then imaged. The resulting image is modeled as an$(\ell+1)$-ary sequence, where$\ell$is the number of labels, in which any nonzero symbol indicates the appearance of the corresponding label in the DNA molecule. The labeling capacity refers to the maximum information rate that can be achieved by the labeling process for any given set of labels. The main goal of this paper is to study the minimum number of labels of the same length required to achieve the maximum labeling capacity of 2 for DNA sequences or$\log_{2}q$for an arbitrary alphabet of size$q$. The solution to this problem requires the study of path unique subgraphs of the de Bruijn graph with the largest number of edges. We provide upper and lower bounds on this value.

Abstract We investigate the asymptotic density of error-correcting codes with good distance properties and prescribed linearity degree, including (sub)linear and nonlinear codes. We focus on the general setting of finite translation-invariant metric spaces, and then specialize our results to the Hamming metric, to the rank metric, and to the sum-rank metric. Our results show that the asymptotic density of codes heavily depends on the imposed linearity degree and the chosen metric.

We initiate the study of the duality theory of locally recoverable codes, with a focus on the applications. We characterize the locality of a code in terms of the dual code, and introduce a class of invariants that refine the classical weight distribution. In this context, we establish a duality theorem analogous to (but very different from) a MacWilliams identity. As an application of our results, we obtain two new bounds for the parameters of a locally recoverable code, including an LP bound that improves on the best available bounds in several instances.

Abstract. We investigate two fundamental questions intersecting coding theory and combinatorial geometry, with emphasis on their connections. These are the problem of computing the asymptotic density of MRD codes in the rank metric, and the Critical Problem for combinatorial geometries by Crapo and Rota. In the first part of the paper, we use methods from semifield theory to derive two lower bounds for the density function of full-rank, square MRD codes. The first bound is sharp when the matrix size is a prime number and the underlying field is sufficiently large, while the second bound applies to the binary field. We then take a new look at the Critical Problem for combinatorial geometries, approaching it from a qualitative, often asymptotic, viewpoint. We illustrate the connection between this very classical problem and that of computing the asymptotic density of MRD codes. Finally, in the third part of the paper we study the asymptotic density of some special families of codes in the rank metric, including the symmetric, alternating, and Hermitian ones. In particular, we show that the optimal codes in these three contexts are sparse.

We consider the problem of describing the typical (possibly) non-linear code of minimum distance bounded from below over a large alphabet. We concentrate on block codes with the Hamming metric and on subspace codes with the injection metric. In sharp contrast with the behavior of linear block codes, we show that the typical non-linear code in the Hamming metric of cardinality $q^{n-d+1}$ is far from having minimum distance d, i.e., from being MDS. We also give more precise results about the asymptotic proportion of block codes with good distance properties within the set of codes having a certain cardinality. We then establish the analogous results for subspace codes with the injection metric, showing also an application to the theory of partial spreads in finite geometry.