In thesequence reconstruction problem, a codewordxis transmitted through several identical channels where each channel produces a noisy read ofx, and the problem is to analyze how to uniquely reconstructxbased on these noisy reads. Levenshtein has studied the minimum number of reads which guarantees unique reconstruction ofx, which is one sufficient condition for unique reconstruction. In this paper, we move on to a different perspective and propose a new framework for unique reconstruction. Our new sufficient condition for unique reconstruction takes both the number of reads and the distances among the reads into consideration. We offer both theoretical analysis and corresponding efficient reconstruction algorithms for our reconstruction framework.

Composite DNA is a recent novel method to increase the information capacity of DNA-based data storage above the theoretical limit of 2 bits/symbol. In this method, every composite symbol does not store a single DNA nucleotide but a mixture of the four nucleotides in a predetermined ratio. By using different mixtures and ratios, the alphabet can be extended to have much more than four symbols in the naire approach. While this method enables higher data content per synthesis cycle, potentially reducing the DNA synthesis cost, it also imposes significant challenges for accurate DNA sequencing since the baselevel errors can easily change the mixture of bases and their ratio, resulting in changes to the composite symbols. With this motivation, we propose efficient constrained coding techniques to enforce the biological constraints, including the runlength-limited constraint and the GC-content constraint, into every DNA synthesized oligo, regardless of the mixture of bases in each composite letter and their corresponding ratio. Our contributions include computing the capacity of the constrained channel, constructing efficient encoders/decoders, and providing the best options for the composite letters to obtain capacityapproaching codes. For certain codes' parameters, our methods incur only one redundant symbol.

We consider the problem of private information retrieval from MDS coded databases with colluding servers, i.e., MDS-TPIR, which is comprised of$M$files and$N$servers, where each file is stored using an ($N, K$) -MDS code. A user wants to retrieve one file without disclosing the index of the desired file to any set of up to$T$colluding servers. Freij-Hollanti et al. proposed a conjecture of the PIR capacity in this setting, which was later disproved by Sun and Jafar by a counterexample with$(M, N, T, K)=(2,4,2,2)$. In this paper, we generalize the counterexample for$(M, N, T, K)=(2, N, 2, K)$whose PIR rate outperforms known results. Our scheme can be generalized in various ways, for arbitrary$M$, for$T=3$, and for multi-file PIR.

High costs remain a primary limitation in the practical application of DNA storage, particularly in the synthesis process. This work focuses on a common synthesis method that generates multiple DNA strands in parallel from a fixed supersequence, one nucleotide at a time. The synthesis time is determined by the length of this supersequence. We investigate the maximum sizes and capacities of codes that restrict the maximum synthesis time while adhering to two critical biochemical constraints in a DNA storage channel: the runlength-limited constraint and the GC-content constraint. For specific parameters, we also present an encoding algorithm for codes that restrict the maximum synthesis time and satisfy both constraints.

Composite DNA is a novel approach that enables DNA-based data storage to exceed the theoretical limit of 2 bits per symbol. In this approach, every composite symbol does not store a single DNA nucleotide but a mixture of the four nucleotides in a predetermined ratio. By using different mixtures and ratios, the alphabet can be extended to have far more than four symbols compared to the naive approach. Although this method increases data density per synthesis cycle and potentially reduces DNA synthesis costs, it also introduces significant challenges for accurate DNA sequencing since the base-level errors can easily change the mixture of bases and their ratio, leading to changes in the composite symbols.With this motivation, we investigated error-correcting codes for composite DNA in a general setting. Consider a data storage scenario where m reads are provided for each composite DNA sequence, and for each composite symbol, the difference between the observation ratio and the original ratio in its base mixture is at most ϵ. We further assume that at most δm sequences have errors, for some 0 ≤ δ ≤ 1, and each of them suffers from at most t edit errors (i.e., substitutions, insertions, and deletions). Given arbitrary values of m, ϵ, δ and t, our task is to design a codebook such that every codeword can be uniquely reconstructed. In this work, we focus on single edit error, i.e., t = 1, and for several cases, we show that our proposed codes are asymptotically optimal.

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.

Recently, codes for correcting a burst of errors have attracted significant attention. One of the most important reasons is that bursts of errors occur in certain emerging techniques, such as DNA storage. In this paper, we investigate a type of error, called a$(t,s)$-burst, which deletes t consecutive symbols and inserts s arbitrary symbols at the same coordinate. Note that a$(t,s)$-burst error can be seen as a generalization of a burst of insertions ($t=0$), a burst of deletions ($s=0$), and a burst of substitutions ($t=s$). Our main contribution is to give explicit constructions of q-ary$(t,s)$-burst correcting codes with$\log n + O(1)$bits of redundancy for any given constant non-negative integers t, s, and$q \geq 2$. These codes have optimal redundancy up to an additive constant. Furthermore, we apply our$(t,s)$-burst correcting codes to combat other various types of errors and improve the corresponding results. In particular, one of our byproducts is a permutation code capable of correcting a burst of t stable deletions with$\log n + O(1)$bits of redundancy, which is optimal up to an additive constant.

Codes correcting insertion and deletion errors have received considerable attention in recent years due to their applications in DNA storage and other communication and storage systems with synchronization errors. Given two sequences$u$and v, their insdel (short for insertion and deletion) distance is defined as the minimum number of insertions and deletions needed to transform one sequence into the other. Let$I_{q}(n,d)$be the maximum size of a code$\mathcal{C}\subseteq\Sigma^{n}$where$\vert \Sigma\vert =q$, such that any two distinct codewords have insdel distance at least$d$. In this paper, we analyze the upper bound of$I_{q}(n, d)$and improve the results from Liu and Xing [IEEE-IT. 69(2), 928–940, 2023].

In 2001, Levenshtein proposed the sequence reconstruction problem under various channels, indicating that the core problem is to determine the maximum size of the intersection of two error balls centered at two distinct codewords from a certain codebook. For the 3-deletion channel, let$D_{3}(x)$be the the error ball centered at$x\in\{0,1\}^{n}$. In this paper, we consider the sequence reconstruction problem for the 3-deletion channel, when the codebook is an arbitrary 2-deletion correcting code. Pham et al. [IEEE ISIT2022, pp. 992–997] has shown that the maximum size of the intersection of two error balls in this setting is upper bounded by 20, and thus 21 distinct reads are sufficient for unique reconstruction. Our main contribution is to explicitly characterize the pair of codewords$(x,\ y)$such that$\vert \mathcal{D}_{3}(x)\cap \mathcal{D}_{3}(y)\vert \in\{19,20\}$, which will shed light on the design of reconstruction codes for a smaller number of reads.

Motivated by DNA based data storage system, we investigate errors that occur when synthesizing DNA strands in parallel, where each strand is appended one nucleotide at a time by the machine according to a template supersequence. If there is a cycle such that the machine fails, then the strands meant to be appended at this cycle will not be appended, and we refer to this as a synthesis defect. In this paper, we present two families of codes correcting these synthesis defects, which are t-known-synthesis-defect correcting codes and t-synthesis-defect correcting codes. For the first one, it is assumed that the defective cycles are known, and each of the codeword is a quaternary sequence. We provide constructions for this family of codes for$t=1,2$, with redundancy log 4 and$2\log n+O(1)$, respectively. For the second one, the codeword is a set of$M$ordered sequences, and we give a construction for$t=1$to show a strategy for constructing this family of codes. Finally, we derive a lower bound on the redundancy for single-known-synthesis-defect correcting codes, which assures that our construction is almost optimal.

We study a model in which a codeword$x$is transmitted through several identical channels, where each channel produces a noisy read of$x$. The sequence reconstruction problem, proposed by Levenshtein, asks for how to uniquely re-construct$x$based on these noisy reads. Most of previous works focused on the minimum number of reads which guarantees unique reconstruction of$x$in the worst case. In this paper, we move on to a new perspective on the sequence reconstruction problem, and propose a different sufficient condition for unique reconstruction which takes both the number of reads and the distances among the reads into consideration. We offer both theoretical analysis and corresponding efficient reconstruction algorithms.

The PIR (Private information retrieval) array code is as an array version of the PIR codes proposed by Fazeli et al., and both codes aim at designing distributed storage systems with m servers which can implement classical k-PIR protocols while reducing the storage overhead. The central problem in PIR array codes is to maximize k/m, known as the virtual server rate. Blackburn and Etzion provided an asymptotically optimal construction and it has been conjectured to be exactly optimal. We provide a new upper bound of the virtual server rate by linear programming, indicating the optimality of Blackburn-Etzion construction for a wide range of parameters. Besides, we give a general construction of PIR array codes with much fewer servers, with a slight sacrifice on the virtual server rate.

Multimedia codes with the identifiable parent property (MIPPCs) were proposed to resist collusion attacks for multimedia fingerprinting. However, the largest possible code rate of binary MIPPCs is far from being understood yet. In this paper, we aim to establish lower and upper bounds for the largest code rate of binary MIPPCs. To that end, we introduce a new concept of locally thin and fat families (LTFFs) and establish relationships between LTFFs and binary MIPPCs. Accordingly, new lower and upper bounds for binary MIPPCs and LTFFs are derived by means of the probabilistic method and combinatorial techniques. In particular, the order of magnitude for the largest rate of binary MIPPCs is determined. It is shown that the code rate of binary MIPPCs outperforms other existing binary fingerprinting codes (e.g. binary separable codes) as well.

Motivated by applications in DNA-based storage and communication systems, we study deletion and insertion errors simultaneously in a burst. In particular, we study a type of error named$t$-deletion-$s$-insertion-burst ($(t,s)$-burst for short) which is a generalization of the (2, 1)-burst error proposed by Schoeny et al. Such an error deletes$t$consecutive symbols and inserts an arbitrary sequence of length$s$at the same coordinate. We provide a sphere-packing upper bound on the size of binary codes that can correct a$(t,s)$-burst error, showing that the redundancy of such codes is at least$\log (n-t+2)+t-1$. For$t\geq 2s$, an explicit construction of binary$(t,s)$-burst correcting codes with redundancy$\log n+(t-s-1)\log \log n+O_{t}(1)$is given, where$O_{t}(\cdot)$suppresses factors that depend only on$t$. Additionally, we construct a binary (3, 1)-burst correcting code with redundancy at most$\log n+9$, which is optimal up to an additive constant.

Permutation codes and multi-permutation codes have been widely considered due to their various applications, especially in flash memory. In this paper, we consider permutation codes and multi-permutation codes against a burst of stable deletions. In particular, we propose a construction of permutation codes correcting a burst stable deletion of length$s$, with redundancy$\log n+ 2\log \log n+O(1{)}$. Compared to the previous known results, our improvement relies on a different strategy to retrieve the missing symbol on the first row of the array representation of a permutation. We also generalize our constructions for multi-permutations and the variable length burst model. Furthermore, we propose a linear-time encoder with optimal redundancy for single stable deletion correcting permutation codes.

Motivated by applications in DNA-based storage and communication systems, we study deletion and insertion errors simultaneously in a burst. In particular, we study a type of error named t-deletion-1-insertion-burst ((t, 1)-burst for short) proposed by Schoeny et. al, which deletes t consecutive symbols and inserts an arbitrary symbol at the same position. We provide a sphere-packing upper bound on the size of binary codes that can correct (t, 1)-burst errors, showing that the redundancy of such codes is at least log n + t − 1. An explicit construction of a binary (t, 1)-burst correcting code with redundancy log n+(t−2) log log n+O(1) is given. In particular, we construct a binary (3, 1)-burst correcting code with redundancy at most log n + 9, which is optimal up to a constant.

Motivated by applications in DNA-based storage, we study explicit encoding and decoding schemes of binary strings satisfying locally balanced constraints, where the (ℓ, δ)-locally balanced constraint requires that the weight of any consecutive substring of length ℓ is between $\frac{\ell }{2} - \delta $ and $\frac{\ell }{2} + \delta $. In this paper we present coding schemes for the strongly locally balanced constraints and the locally balanced constraints, respectively. Moreover, we introduce an additional result on the linear recurrence formula of the number of binary strings which are (6, 1)-locally balanced, as a further attempt to both capacity characterization and new coding strategies.

Fractional repetition (FR) codes are a special family of regenerating codes with the repair-by-transfer property. The constructions of FR codes are naturally related to combinatorial designs, graphs, and hypergraphs. Given the file size of an FR code, it is desirable to determine the minimum number of storage nodes needed. The problem is related to an extremal graph theory problem, which asks for the minimum number of vertices of an α-regular graph such that any subgraph with k vertices has at most δ edges. In this paper, we present a class of regular graphs for this problem to give the bounds for the minimum number of storage nodes for the FR codes.

Aprivate proximity retrieval(PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance$r$from the user’s record$x$. The user’sprivacyat each server is given by the fraction of the record$x$that is kept private. In this paper, this research is initiated and protocols that offer trade-offs between privacy, computational complexity, and storage are studied. In particular, we assume that each server stores a copy of the database and study the required minimum number of servers by our protocol which provides a given privacy level. Each server receives a query in the protocol and the set of queries forms a code. The main focus in the paper is dedicated to studying the family of codes generated by the set of queries. These codes will be shown to satisfy a specific covering property and will be calledprivate proximity retrieval intersection covering codes. In particular, since the query every server receives is a codeword, the goal is to minimize the number of codewords in such a code which is the minimum number of servers required by the protocol. These codes are closely related to a family of codes known ascovering designs. We introduce several lower bounds on the sizes of such codes as well as several constructions. This work focuses on the case when the records are binary vectors together with the Hamming distance. Other metrics such as the Johnson metric are also investigated.

Three new constraints are introduced in this paper. These constraints are characterized by limitations on the Hamming weight of every subword of some fixed even length ℓ. In the (ℓ, δ)-locally-balanced constraint, the Hamming weight of every length-ℓ subword is bounded between ℓ/2 - δ and ℓ/2 + δ. The strong-(ℓ,δ)-locally-balanced constraint imposes the locally-balanced constraint for any subword whose length is at least ℓ. Lastly, the Hamming weight of every length-ℓ subword which satisfies the (ℓ, δ)-locally-bounded constraint is at most ℓ/2 - δ. It is shown that the capacity of the strong-(ℓ, δ)-locally-balanced constraint does not depend on the value of ℓ and is identical to the capacity of the (2δ + 1)-RDS constraint. The latter constraint limits the difference between the number of zeros and ones in every prefix of the word to be at most 2δ + 1. This value is also a lower bound on the capacity of the (ℓ, δ)-locally-balanced constraint, while a corresponding upper bound is given as well. Lastly, it is shown that if δ is not large enough, namely for δ <; √ℓ/2, then the capacity of the (ℓ, δ)-locally-bounded constraint approaches 1 as ℓ increases.

A functional k-Private Information Retrieval (k-PIR) code of dimension s consists of n servers storing linear combinations of s linearly independent information symbols. Any linear combination of the s information symbols can be recovered by k disjoint subsets of servers. The goal is to find the minimum number of servers for given k and s. We provide lower bounds on the minimum number of servers and constructions which yield upper bounds on this number. For k ≤ 4, exact bounds on this number are proved. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known PIR problem based on a coded database to reduce the storage overhead, when each linear combination contains exactly one information symbol. If any multiset of size k of linear combinations from the linearly independent information symbols can be recovered by k disjoint subset of servers, then the servers form a functionalk-batch code. A functional k-batch code is a functional k-PIR code, where all the k linear combinations in the multiset are equal. We provide some bounds on the minimum number of servers for functional k-batch codes. In particular we present a random construction and a construction based on simplex codes, Write-Once Memory (WOM) codes, and Random I/O (RIO) codes.

A private proximity retrieval (PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance r from the user's record x. The user's privacy at each server is given by the fraction of the record x that is kept private. The distortion of a PPR scheme measures how accurately the user can calculate the identities of the desired files. We assume that each server stores a copy of the database. This paper studies protocols that offer trade-offs between perfect privacy and low computational complexity and storage.In this paper, this study is initiated. The work focuses on the case when the records are binary vectors together with the Hamming distance. In particular, for a given privacy level, we investigate the minimum number of servers that guarantee a prescribed distortion value. The collusions of pairs of servers as well as other distance measures are investigated.

Private information retrieval has been reformulated in an information-theoretic perspective in recent years. The two most important parameters considered for a PIR scheme in a distributed storage system are the storage overhead and PIR rate. The complexity of the computations done by the servers for the various tasks of the distributed storage system is an important parameter in such systems which didn't get enough attention in PIR schemes. As a consequence, we take into consideration a third parameter, the access complexity of a PIR scheme, which characterizes the total amount of data to be accessed by the servers for responding to the queries throughout a PIR scheme. We use a general covering codes approach as the main tool for improving the access complexity. With a given amount of storage overhead, the ultimate objective is to characterize the tradeoff between the rate and access complexity of a PIR scheme. This covering codes approach raises a new interesting coding problem of generalized coverings similarly to the well-known generalized Hamming weights.

A functional k-PIR code of dimension s consists of n servers storing linear combinations of s linearly independent information symbols. Any linear combination of the s information symbols can be recovered by k disjoint subsets of servers (the reason for this somehow abused definition will be explained in the sequel). The goal is to find the smallest number of servers for given k and s. We provide lower bounds on the number of servers and constructions which yield upper bounds. For k ≤ 4 we provide exact bounds on the number of servers. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known private information retrieval problem based on a coded database to reduce the storage overhead. If any multiset of size k of linear combinations from the linearly independent information symbols can be recovered by k disjoint subset of servers, then the servers form a functional k-batch code. A functional k-batch code is also a functional k-PIR, where all the k linear combinations in the multiset are equal. We provide some bounds on the number of servers for functional k-batch codes. In particular we present a random construction and a construction based on simplex codes, WOM codes, and RIO codes.

Given a database, the private information retrieval (PIR) protocol allows a user to make queries to several servers and retrieve a certain item of the database via the feedbacks without revealing the identity of the specific item to any single server. Classic k-server PIR protocols work on replicated databases, i.e., each of the k servers stores a whole copy of the database. Recently, new PIR models were proposed with coding techniques arising from the distributed storage system. In these new models, each server only stores a fraction 1/s of the whole database, where s > 1 is the given rational number. The PIR array codes are recently proposed by Fazeli, Vardy, and Yaakobi to characterize the new models. The central problem in designing a PIR array code with m servers and the k-PIR property (which indicates that these m servers may emulate a classic k-server PIR protocol) is to maximize k/m, known as the virtual server rate. Our main contribution to this problem is twofold. First, for the case 12, a new upper bound on the rate of a PIR array code is presented. Besides, we also have some discussions on an asymptotically optimal construction by Blackburn and Etzion.

The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. Yanet al.reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into$F$pieces, where$F$grows exponentially with the number of users$K$. Such a constraint is obviously infeasible in the practical setting, especially when$K$is large. Thus, it is desirable to design caching schemes with constant rate$R$(independent of$K$) as well as smaller$F$. In this paper, we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with$F$growing linearly with$K$do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with$F$growing sub-exponentially with$K$do exist.

Various kinds of secure codes and their related hash families are broadly studied combinatorial structures for protecting copyrighted materials. The codewords in such a structure can be regarded as a subset of$Q^{N}$, the set of all$q$-ary vectors of given length$N$, satisfying some constraints. We use a hypergraph model to characterize the combinatorial structure. By applying a result of Dukeet al.on the lower bound of the independence number of hypergraphs, we provide a new approach to evaluate the lower bounds for several kinds of secure codes and related hash families. In particular, the general method is illustrated via the examples of existence results on some perfect hash families, frameproof codes, and separable codes.

For a Gray code in the scheme of rank modulation for flash memories, the codewords are permutations, and two consecutive codewords are obtained using a push-to-the-top operation. We consider the snake-in-the-box code under Kendall’s$\tau $-metric, which is a Gray code capable of detecting one Kendall’s$\tau $-error. We answer two open problems posed by Horovitz and Etzion. First, we prove the validity of a construction given by them, resulting in a snake of size$M_{2n+1}=({(2n+1)!}/{2})-2n+1$. Second, we come up with a different construction aiming at a larger snake of size$M_{2n+1}=({(2n+1)!}/{2})-2n+3$. The construction is applied successfully to$S_{7}$.

Snake-in-the-box codes under Kendall’s$\tau $-metric are studied in the rank modulation scheme for flash memories, where codewords are a subset of permutations in$S_{n}$with minimal Kendall’s$\tau $-distance two, and two cyclically consecutive codewords are connected via a push-to-the-top operation. Studies so far restrict the push-to-the-top operations only on odd indices, resulting in a snake consisting of permutations with the same parity, and thus, the minimal distance constraint is easily satisfied. Asymptotically optimal snake codes have been constructed this way in$S_{2n+1}$. As for$S_{2n+2}$, this framework keeps the last element fixed, and thus, a snake in$S_{2n+2}$is equivalent to a snake in$S_{2n+1}$, which is rather trivial. If one wants to do better, then it is inevitable to have some push-to-the-top operations on even indices, resulting in a combination of odd and even permutations in the snake, which increases the difficulty to guarantee the minimal Kendall’s$\tau $-distance constraint. Thus, Horovitz and Etzion pose the open problem to prove or disprove that the size of the largest snake in$S_{2n+2}$is not larger than the size of the largest snake in$S_{2n+1}$. A first step toward this problem is a negative answer by Wang and Fu, who construct a snake in$S_{2n+2}$with exactly one more permutation than an optimal snake in$S_{2n+1}$. In this paper, we give an explicit construction of a snake in$S_{2n+2}$with size asymptotically approaching$({1}/{4})|S_{2n+2}|$.