The sequence reconstruction problem involves a model where a sequence is transmitted over several identical channels. This model investigates the minimum number of channels required for the unique reconstruction of the transmitted sequence. Levenshtein established that this number exceeds the maximum size of the intersection between the error balls of any two distinct transmitted sequences by one. In this paper, we consider channels subject to multiple bursts of insertions and multiple bursts of deletions, respectively, where each burst has an exact length of valueb. Our key findings are as follows: • Insertion Case: We investigateb-burst-insertion balls of radiustcentered atq-ary sequences of lengthn. We establish that the size of an error ball is independent of its chosen center. Furthermore, we demonstrate that the intersection between error balls centered at two sequences differing only at their first position yields the largest intersection size, denoted byNq,b+(n,t). We also propose a reconstruction algorithm with linear runtime complexity, which processesNq,b+(n,t)+1 distinct output sequences from the channel to recover the correct transmitted sequence. • Deletion Case: We examineb-burst-deletion balls of radiustcentered atq-ary sequences of lengthn. In contrast to burst-insertion balls, we prove that the size of a burst-deletion ball is dependent on its chosen center. Particularly, we show that theb-burst-deletion ball centered at theb-cyclic sequence 0b⸰ 1b⸰ · · · ⸰ (q− 1)b⸰ 0b· · · achieves the largest size. For binary alphabets, we then demonstrate that the intersection ofb-burst-deletion balls centered at 0b⸰ 1b⸰ 0b⸰ 1b· · · and 0b−1⸰ 1 ⸰ 1b⸰ 0b⸰ 1b· · · yields the largest size, denoted byN2,b−(n,t). Moreover, we propose a reconstruction algorithm with linear runtime complexity, which processesN≥N2,b−(n,t)+1 distinct output sequences from the channel to reconstruct the correct transmitted sequence1.

In this paper, we investigate binary reconstruction codes capable of correcting one deletion and one substitution. We define the \emph{single-deletion single-substitution ball} function $ \mathcal{B} $ as a mapping from a sequence to the set of sequences that can be derived from it by performing one deletion and one substitution. A binary \emph{$(n,N;\mathcal{B})$-reconstruction code} is defined as a collection of binary sequences of length $ n $ such that the intersection size between the single-deletion single-substitution balls of any two distinct codewords is strictly less than $ N $. This property ensures that each codeword can be uniquely reconstructed from $ N $ distinct elements in its single-deletion single-substitution ball. Our main contribution is to demonstrate that when $ N $ is set to $ 4n - 8 $, $ 3n - 4 $, $2n+9$, $ n+21 $, $31$, and $7$, the redundancy of binary $(n,N;\mathcal{B})$-reconstruction codes can be $0$, $1$, $2$, $ \log\log n + 3 $, $\log n + 1 $, and $ 3\log n + 4 $, respectively, where the logarithm is on base two.

In this paper, we propose a partitioning technique that decomposes a pair of sequences with overlappingt-deletions-substitution balls into sub-pairs, where the≤t-burst-deletion balls of each sub-pair intersect. This decomposition facilitates the development oft-deletions-substitution correcting codes that leverage approaches from≤t-burst-deletion correction. Building upon established approaches in the≤t-burst-deletion correction domain, we constructt-deletions-substitution correcting codes fort∈ {1, 2} over binary alphabets and fort= 1 in non-binary alphabets, with some constructions matching existing results and others outperforming current methods. Our framework offers new insights into the underlying principles of prior works, elucidates the limitations of current approaches, and provides a unified perspective on error correction strategies.

This paper addresses fundamental challenges in two-dimensional error correction by constructing optimal codes forcriss-cross deletions. We consider ann×narrayXover aq-ary alphabet Σq:= {0, 1, . . . ,q−1} that is subject to a (tr, tc)-criss-cross deletion, which involves the simultaneous removal oftrrows andtccolumns. A codeC⊆ Σn×nqis defined as a (tr, tc)-criss-cross deletion correcting codeif it can successfully correct these deletions. Our primary technical contributions are as follows: •Theoretical Bounds: We derive a sphere-packing type lower bound and a Gilbert-Varshamov type upper bound on the redundancy of optimal codes. Our results indicate that the optimal redundancy for a (tr, tc)-criss-cross deletion correcting code lies between (tr, tc)nlogq+(tr, tc) logn+Oq,tr,tc(1) and (tr, tc)nlogq+2(tr, tc) logn+Oq,tr,tc(1), where the logarithm is on base two, and Oq,tr,tc (1) is a constant that depends solely onq, tr, andtc. •Optimal Constructions: For the case of (1, 1)-criss-cross deletions, we propose two families of constructions that achieve 2nlogq+ 2 logn+Oq(1) bits of redundancy. This redundancy is optimal up to an additive constant termOq(1), which depends solely onq. One family is designed for non-binary alphabets, while the other addresses arbitrary alphabets. For the case of (tr, tc)-criss-cross deletions, we provide a strategy to derive optimal codes when both unidirectional deletions occur consecutively. •Efficient Decoders: We propose decoding algorithms with a time complexity ofO(n2) for our codes, which are optimal for two-dimensional scenarios.

LetB(·) be an error ball function. A set ofq-ary sequences of lengthnis referred to as an (n, q, N; B)-reconstruction codeif each sequencexwithin this set can be uniquely reconstructed from anyNdistinct elements within its error ballB(x). The main objective in this area is to determine or establish bounds for the minimum redundancy of (n, q, N; B)-reconstruction codes, denoted by ρ(n, q, N; B). In this paper, we investigate reconstruction codes where the error ball corresponds to either thet-deletion ball Dt(·) or thet-insertion ball It(·). Our primary technical contributions include: • Establishing a fundamental connection between reconstruction codes for deletions and insertions. Specifically, for any positive integersn, t, q, N, any (n, q, N; It)-reconstruction code is also an (n, q, N; Dt)-reconstruction code. This leads to the inequality ρ(n, q, N; Dt) ≤ ρ(n, q, N; It). • Identifying a significant distinction between reconstruction codes for deletions and insertions whenN=O(nt−1) andt≥ 2. For deletions, we prove that there exists some constantKsuch that ρ(n, q,2(q−1)t−1/qt−1(t−1)!nt−1+Knt−2;Dt) =O(1), which disproves a conjecture posed in [1]. In contrast, for insertions, we show that there exists some constantK′ such that ρ(n, q,(q−1)t−1(t−1)!nt−1+K′nt−2;It) = log logn+O(1), which extends a key result from [2]. • Constructing (n, q, N; B)-reconstruction codes, whereB∈ {D2,I2}, forN∈ {2, 3, 4, 5} and establishing respective upper bounds of 3 logn+O(log logn), 3 logn+O(1), 2 logn+ O(log logn) and logn+ O(log logn) on the minimum redundancy ρ(n, q, N; B). This generalizes results previously established in [3].

Consider a length-n sequencexover aq-ary alphabet. The fixed-length Levenshtein ballLt(x) of radius t contains all length-nq-ary sequences that can be derived fromxby performingtdeletions followed bytinsertions. Recent studies have successfully characterized fixed-length Levenshtein balls in the context of radiust= 1. These works have derived explicit formulas for various quantities, including the exact size of the balls, extremal bounds (minimum and maximum sizes), as well as expected sizes and their concentration properties. However, the general case involving an arbitrary number oftdeletions andtinsertions (t> 1) remains largely uninvestigated. This work systematically examines fixed-length Levenshtein balls with multiple deletions and insertions, focusing specifically onfixed-length burst Levenshtein balls, where deletions occur consecutively, as do insertions. We provide solutions for explicit cardinality formulas, extremal bounds (minimum and maximum sizes), expected size, and concentration properties surrounding the expected value.

Codes correcting bursts of deletions and localized deletions have garnered significant research interest in recent years. One of the primary objectives is to construct codes with minimal redundancy. Currently, the best known constructions of q-ary codes correcting a burst of at most t deletions ((≤t)-burstdeletion correcting codes) achieve redundancy log n+8 log log n+ o(log log n) (for anyqandt) or log n +tlog log n + O(1) (for even q). For codes correcting singlet-localized-deletion, state-ofthe- art constructions attain redundancy log n+O 􀀀 t(log log n)2) (for any q and t) or log n + 2t log log n + O(1) (for even q). Here, n denotes the code-length, and q and t are fixed. These codes employ a position-estimation component to approximate error positions, augmented by additional constraints that enable error-correction given the information about error positions. In this work, we first generalize thet-localized-deletion model to a (t, T)-localized-deletion model and then explore code constructions for correcting such errors. We select codewords from the set of sequences whose differential sequences are strong-(ℓ, ϵ)- locally-balanced. By imposing a VT-type constraint and an L1- weight constraint on the differential sequences of codewords, we construct novel position-estimation codes. When q ≥ 2 and tqis even andtq-ary (≤t)- burst-deletion correcting code and a (t, T)-localized-deletion correcting code with redundancy log n+(t−1) log log n+O(1). In addition to improving previous redundancy, our technique is novel and leads to simpler position-estimation codes compared to earlier works. Finally, we present an efficient encoder that maps an arbitrary input sequence into a sequence whose differential sequence is strong-(ℓ, ϵ)-locally-balanced. To our knowledge, no prior algorithm for this specific task has been reported.

In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactlyb, whereb> 1. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most 7 logn+O(logn/ log logn) bits. In contrast, our work introduces a novel approach for constructing q-ary codes that attain a redundancy of at most 5 logn+O(log logn) bits for allb> 1 andq≥ 2. Additionally, for the case whereb= 1, we present a new construction of q-ary two-deletion correcting codes with a redundancy of 5 logn+ O(log logn) bits, for allq> 2.

Abstract. We study the supersaturation problems of oddtown and eventown. Given a family [Formula: see text] of subsets of an [Formula: see text]-element set, let [Formula: see text] denote the number of distinct pairs [Formula: see text] for which [Formula: see text] is odd. We show that if [Formula: see text] consists of [Formula: see text] odd-sized subsets, then [Formula: see text], which is tight when [Formula: see text]. This disproves a conjecture by O’Neill on the supersaturation problem of oddtown. For the supersaturation problem of eventown, we show that for large enough [Formula: see text], if [Formula: see text] consists of [Formula: see text] even-sized subsets, then [Formula: see text] for any positive integer [Formula: see text]. This partially proves a conjecture by O’Neill on the supersaturation problem of eventown. Previously, the correctness of this conjecture was only verified for [Formula: see text] and 2. We further provide a lower bound which is a factor of two away from the conjectured bound for eventown, that is, [Formula: see text] for general [Formula: see text] and [Formula: see text] by using discrete Fourier analysis. Finally, some asymptotic results for the lower bounds of [Formula: see text] are given when [Formula: see text] is large for both problems.

Motivated by applications in DNA-based data storage, constrained codes have attracted a considerable amount of attention from both academia and industry. We study the maximum cardinality of constrained codes for which the constraints can be characterized by a set of forbidden substrings, where by a substring we mean some consecutive coordinates in a string. The study of finite-type constrained codes, for which the set of forbidden substrings is finite, dated back to a pioneering and influential work of Shannon in the 1940s. To the best of our knowledge, for roughly 80 years, people have known essentially only one method, i.e., the “spectral method”, that computes the rate and the cardinality of finite-type constrained codes. We show that there is a surprisingly powerful method arising from enumerative combinatorics, which applies the Goulden-Jackson cluster theorem (previously not known to the coding community), that serves as an alternative method to compute the code rate and the exact cardinality of each fixed length, of these codes. Moreover, the computation can be done by solving a system of linear equations of size equal to the number of constraints, and the time complexity improves that of the spectral method when the number of constraints is relatively small. More interestingly, our new method has the flexibility that it also applies to constrained codes defined by an infinite number of forbidden substrings. As an example, variable-length non-overlapping codes have potential applications in DNA storage. Bilotta, also Wang and Wang asked for an explicit upper bound on the maximum cardinality of these codes. By applying the cluster method in concert with other tools in analytic combinatorics, we obtain such a bound, thereby giving an affirmative answer to their question. Moreover, our bound is tight when the code length divides the alphabet size, as shown by a construction of Blackburn. Lastly, we show that the spectral method and the cluster method are inherently related by establishing a direct connection between the spectral radius of the de Brujin graph used in the former and the convergence radius of the generating function used in the latter.

Bursts of errors are a class of errors that can be found in a variety of applications. A burst of t edits refers to a burst of t deletions, or a burst of t insertions, or a burst of t substitutions. This paper focuses on studying codes that can correct a burst of t edits. Our primary approach involves the use of the tool called weighted-summation VT sketch. The$(t,k)$-weighted-summation VT sketch of a length-n sequence is defined as the weighted summation of the VT sketch of each row of its$t\times \lceil n/t \rceil $array representation, with weights in the i-th row set as$k^{i-1}$for$i=1,2,\ldots,t$. By employing the weighted-summation VT sketch alongside multiple weight sketches, we introduce a construction for q-ary t-burst-substitution correcting codes with a redundancy of$\log n+O(1)$, where the logarithm base is 2. Subsequently, we improve the redundancy to address specific types of burst-substitution errors, such as inversion errors, adjacent-block-transposition errors, and absorption errors. Moreover, by utilizing the method developed in the construction of burst-substitution correcting codes and imposing additional run-length-limited constraints, locally-bounded constraints, and strong-locally-balanced constraints, respectively, we introduce three constructions of t-burst-deletion correcting codes, each requiring a redundancy of$\log n+O(\log \log n)$. Any t-burst-deletion-correcting code is also a t-burst-insertion correcting code, allowing us to intersect the t-burst-substitution-correcting codes and t-burst-deletion-correcting codes designed above to derive three constructions of q-ary t-burst-edit-correcting codes. The first two constructions have a redundancy of$\log n+(t\log q-1)\log \log n+O(1)$, while the third construction has a redundancy of$\log n+\log \log n+O(1)$. Most of the proposed codes demonstrate superior performance compared to previous results, with the exception of burst-deletion correcting codes. Furthermore, in cases of single-edit errors (t-burst-edit error with$t=1$), the redundancy of the first two constructions of quaternary single-edit correcting codes outperforms the results of Gabrys et al. (IEEE Trans. Inf. Theory 2023). We also provide efficient encoding and decoding algorithms for our codes to enhance their practical usability.

Nanopore sequencing is a promising technology for DNA sequencing. In this paper, we investigate a specific model of the nanopore sequencer, which takes aq-ary sequence of lengthnas input and outputs a vector of lengthn+ℓ−1 referred to as an ℓ-read vector where thei-th entry is a multi-set composed of the ℓ elements located between the (i−ℓ+1)-th andi-th positions of the input sequence. Considering the presence of substitution errors in the output vector, we study ℓ-read codes under the Hamming metric. An ℓ-read (n,d)q-code is a set ofq-ary sequences of lengthnin which the Hamming distance between ℓ-read vectors of any two distinct sequences is at leastd. Here, the Hamming distance between two ℓ-read vectors is defined as the number of positions at which the corresponding multi-sets differ. We first improve the result of Banerjeeet al., who studied ℓ-read (n,d)q-codes with the constraint ℓ ≥ 3 andd= 3. Then, we investigate the bounds and constructions of 2-read codes with a minimum distance of 3, 4, and 5, respectively. Our results indicate that whend∈ {3, 4}, the optimal redundancy of 2-read (n,d)q-codes iso(logqn), while ford= 5 it is logqn+o(logqn). Additionally, we establish an equivalence between 2-read (n, 3)q-codes and classicalq-ary single-insertion reconstruction codes using two distinct noisy reads. We improve the lower bound on the redundancy of classicalq-ary single-insertion reconstruction codes as well as the upper bound on the redundancy of classicalq-ary single-deletion reconstruction codes when using two distinct noisy reads.

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.

Function-correcting codes (FCCs), introduced by Lenz, Bitar, Wachter-Zeh, and Yaakobi, protect specific function values of a message rather than the entire message. A central challenge is determining the optimal redundancy—the minimum additional information required to recover function values amid errors. This redundancy depends on both the number of correctable errorstand the structure of message vectors yielding identical function values. While prior works established bounds, key questions remain, such as the optimal redundancy for functions like Hamming weight and Hamming weight distribution, along with efficient code constructions. In this paper, we make the following contributions: 1) For the Hamming weight function, we improve the lower bound on optimal redundancy from 10(t-1)/3 to 4t− 4/3√6t+ 2 + 2. On the other hand, we provide a systematical approach to constructing explicit FCCs via a novel connection with Gray codes, which also improve the previous upper bound from 4t-2/1−2√ln(2t)/(2t) to 4t− [logt]. Consequently, we almost determine the optimal redundancy for Hamming weight function. 2) The Hamming weight distribution function is defined by the value of Hamming weight divided by a given integerT∈ N. Previous work established that the optimal redundancy is 2twhenT> 2t, while the caseT≤ 2tremained unclear. We show that the optimal redundancy remains 2twhenT≥t+ 1. However, in the surprising regime whereT=o(t), we achieve near-optimal redundancy of 4t−o(t). Our results reveal a significant distinction in behavior of redundancy for distinct choices of T.

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.

This paper studies the construction of constant$L_{1}$-weight codes under$L_{\infty }$-metric, which could be used to design codes addressing 0-indels (i.e., the insertion/deletion of 0’s only). Based on the patterns of small codes, we determine the maximum size for codes with distance 2 and length 3 for any constant weight, and several constructions and algorithms for suboptimal codes with general length$w+1$are also provided. In general, for codes with distance D, length$w+1$, and weight$tD+r$, we derive the size of the largest code by using Hall’s theorem for integers$r=0$,$t\in [{0,3}]$and$w\geq t-1$. When$r=\frac {D}{2}$with D being even, codes with a cardinality that surpasses the known existing sizes by the additive term$\left \lceil{ \frac {1}{3}\binom {t+1}{2}}\right \rceil \left \lfloor{ \frac {w+1}{3}}\right \rfloor $are constructed based on the structure of group divisible designs in combinatorics.

An edit refers to a single insertion, deletion, or substitution. This paper aims to construct binary codes that can correct two edits. To do this, a necessary and sufficient condition for a code to be two-edit correctable is provided, showing that a code is a two-edit correcting code if and only if it can correct two deletions, up to two substitutions, and one deletion and up to one substitution, separately. This criterion allows for the construction of two-edit correcting codes leveraging these three types of error correcting codes. In the field of constructing codes for correcting two deletions, we present a construction with$4\log n+O(\log \log n)$redundant bits that can be viewed as a subcode proposed by Guruswami and Håstad, and provide an alternative proof. Moreover, our two-deletion correcting codes can also correct up to two substitutions after making a slight modification. In the field of constructing codes for correcting one deletion and up to one substitution, we present a construction with$4 \log n+O(\log \log n)$redundant bits, which outperforms the best previously known results$6 \log n+O(1)$. Leveraging these codes, we obtain a construction of two-edit correcting codes with$6 \log n+O(\log \log n)$redundant bits. This outperforms the best previously known result, which requires at least$8\log n$redundant bits. Moreover, we also consider the list-decoding problem under the two-edit channel and construct a two-edit list-decodable code with a list size of two employing$4 \log n+O(\log \log n)$redundant bits.

This paper studies the problem of encoding messages into sequences which can be uniquely recovered from some noisy observations about their substrings. The observed reads comprise consecutive substrings with some given minimum overlap. This coded reconstruction problem has applications in DNA storage. We consider both single-strand reconstruction codes and multi-strand reconstruction codes, where the message is encoded into a single strand or a set of multiple strands, respectively. Various parameter regimes are studied. New codes are constructed, some of whose rates asymptotically attain the upper bounds.

To prevent service time bottlenecks in distributed storage systems, the access balancing problem has been studied by designing almost supermagic edge labelings of certain graphs to balance the access requests to different servers. In this paper, we introduce the concept ofrobustnessof edge labelings under limited-magnitude swaps, which is important for studying thedynamicalaccess balancing problem with respect to changes in data popularity. We provide upper and lower bounds on the robustness ratio for complete graphs withnvertices, and constructO(n)-almost supermagic labelings that are asymptotically optimal in terms of the robustness ratio.

The centralized coded caching focuses on reducing the network burden in peak times in a wireless network system. In this paper, motivated by the study of the only rainbow 3-term arithmetic progressions set, we propose a combinatorial framework for constructing coded caching schemes. This framework builds bridges between coded caching schemes and lots of combinatorial objects due to the freedom of the choices of families and binary operations. We prove that any scheme based on a placement delivery array (PDA) can be represented by a rainbow scheme under this framework and lots of other known schemes can also be included in this framework. Moreover, we also present a new coded caching scheme with linear subpacketization and near constant rate using the only rainbow 3-term arithmetic progressions set. Finally, we modify the framework to be applicable to the coded caching problem in Device-to-Device (D2D) networks and the distributed computing problem.

In nonadaptive group testing, the main research objective is to design an efficient algorithm to identify a set of up to$t$positive elements among$n$samples with as few tests as possible. Disjunct matrices and separable matrices are two classical combinatorial structures while one provides a more efficient decoding algorithm and the other needs fewer tests, i.e., larger rate. Recently, a notion of strongly separable matrix has been introduced, which has the same identifying ability as a disjunct matrix, but has larger rate. In this paper, we use a modified probabilistic method to improve the lower bounds for the rate of strongly separable matrices. Using this method, we also improve the lower bounds for some well-known combinatorial structures, including locally thin set families and cancellative set families.

Grassmannian$\mathcal {G}_{q}(n,k)$is the set of all$k$-dimensional subspaces of the vector space$\mathbb {F}_{q}^{n}$. Recently, Etzion and Zhang introduced a new notion called covering Grassmannian code which can be used in network coding solutions for generalized combination networks. An$\alpha $-$(n,k,\delta)_{q}^{c}$covering Grassmannian code$\mathcal {C}$is a subset of$\mathcal {G}_{q}(n,k)$such that every set of$\alpha $codewords of$\mathcal {C}$spans a subspace of dimension at least$\delta +k$in$\mathbb {F}_{q}^{n}$. In this paper, we derive new upper and lower bounds on the size of covering Grassmannian codes. These bounds improve and extend the parameter range of known bounds.

Motivated by certain emerging storage media, such as DNA storage and racetrack memories, we study the problem of designing$(n,N;\mathcal {D}_{k})$-reconstruction codes, where the deletion ball function$\mathcal {D}_{k}$maps a sequence of length$n$to the set consisting of all its subsequences of length$n-k$, in which any two distinct sequences do not share$N$distinct subsequences of length$n-k$. Note that the problem of designing$(n,N;\mathcal {D}_{k})$-reconstruction codes can be seen not only as a relaxed coding problem of$k$-deletion correcting codes, but also as a dual problem of the sequence reconstruction problem. In this work, we focus on the case when$k=2$and$2 \leq N \leq 6$. Note that when$N=1$, the best known$(n,N;\mathcal {D}_{2})$-reconstruction codes (two-deletion correcting codes) have$4 \log n + o(\log n)$bits of redundancy. Firstly, we improve the redundancy to$3 \log n + o(\log n)$when$N \in \{2,3\}$and further improve it to$2 \log n +o(\log n)$when$N=4$. Then, for$N \in \{5,6\}$, we design reconstruction codes with$\log n + o(\log n)$bits of redundancy outperforming the previous best known result$2 \log n+ o(\log n)$.

Motivated by applications in modern storage devices such as DNA storage and racetrack memories, we study the sequence reconstruction problem which involves two important issues. One is determining the maximum intersection size between two error balls. The other is designing reconstruction codes in which each transmitted sequence can be reconstructed from a given number of noisy reads with redundancy as small as possible. In this paper, we focus on channels that introduce single-burst-insertion/deletion error. We fully determine the maximum intersection size between two burst-insertion/deletion balls for both fixed-length and variable-length models. Then we characterize a pair of sequences when their burst-insertion/deletion balls have intersection of a certain size. Using these characterizations, we design reconstruction codes for all values$N$of the number of noisy reads and analyze their lower bounds. In addition, we extend our results to the burst-edit channel.

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.

We consider the following robust computing problem in a directed acyclic network. A sink node is required to compute with zero error a target function of source messages which are generated at multiple source nodes, whereas the communication links might be corrupted by errors. The nodes in this network may perform network coding to combat the errors. Given an integer$\tau $, the robust computing rate of a network code against$\tau $errors is the average number of times that the target function can be computed with zero error for one use of the network with at most$\tau $links being corrupted by errors. We derive two cut-set bounds on the robust computing capacity and show that these bounds can be achieved in a multi-edge tree network for computing any target function. Furthermore, we consider linear network codes for computing linear target functions. Given a computing rate, we define a minimum distance to measure the error-tolerant capability of the linear network function computing codes. We propose a Singleton-like bound on this minimum distance and show that this bound is tight in two classes of networks for computing the sum of source messages.

Reconstruction codes are generalizations of error-correcting codes that can correct errors by a given number of noisy reads. The study of such codes was initiated by Levenshtein in 2001 and developed recently due to applications in modern storage devices such as racetrack memories and DNA storage. The central problem on this topic is to design codes with redundancy as small as possible for a given number$N$of noisy reads. In this paper, the minimum redundancy of such codes for binary channels with exactly two insertions is determined asymptotically for all values of$N\ge 5$. Previously, such codes were studied only for channels with single edit errors or two-deletion errors.

Motivated by emerging applications in coding for molecular data storage, much attention has been paid to the intersecting set discrepancy problem, which aims to design a large family of subsets of a common labeled ground set with bounded pairwise intersection and bounded set discrepancy. In this paper, we study the maximum size of such families of$k$-subsets with$v$elements ground set,$t$-bounded intersections, and zero or one discrepancy, called as balanced$(t,k,v)$set codes. By turning this problem into a graph edge-labeling problem, we are able to determine the maximum size of codes when$k=3,4$and$t=2,3$for a given ground set. The constructions are based on combinatorial designs, matching decompositions and edge coloring schemes. Furthermore, we improve the upper bound for balanced$(t,k,v)$set codes with all integers$2\leq t < k < v$. By the powerful probabilistic argument–Kahn’s Theorem, we show that the improved upper bound for any fixed integers$2 \leq t < k$is asymptotically tight when$v$goes to infinity.

Limited magnitude error model has applications in flash memory. In this model, a perfect code is equivalent to a tiling of$\mathbb {Z}^{n}$by limited magnitude error balls. In this paper, we give a complete classification of lattice tilings of$\mathbb {Z}^{n}$by limited magnitude error balls$\mathcal {B}(n,2,1,1)$.

Hopping cyclic codes (HCCs) are (non-linear) cyclic codes with the additional property that the$n$cyclic shifts of every given codeword are all distinct, where$n$is the code length. Optical orthogonal codes (OOCs) are constructed from constant weight binary HCCs by picking exactly one member from the$n$cyclic shifts of every codeword. HCCs and OOCs have various practical applications and have been studied extensively over the years. In this paper, we present improved Gilbert-Varshamov type lower bounds on the size of both codes, when the minimum distance is bounded below by a linear factor of the code length. For HCCs, we improve the previously best known lower bound of Niu, Xing, and Yuan by a multiplicative linear factor of the code length. For OOCs, we improve the previously best known lower bound of Chung, Salehi, and Wei, and Yang and Fuja also by a multiplicative linear factor of the code length. Our proofs are based on tools from probability theory and graph theory, in particular the McDiarmid’s inequality on the concentration of Lipschitz functions and the independence number of locally sparse graphs.

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.

For an $r$-graph $G$, the minimum $(r-1)$-degree $\delta(G)$ is the largest integer $t$ such that every $(r-1)$-subset of $V(G)$ is contained in at least $t$ edges of $G$. Given an $r$-graph $F$, the codegree density $\gamma(F)$ is the largest $\gamma>0$ such that there are $F$-free $r$-graphs $G$ on $n$ vertices with $\delta(G)\ge(\gamma-o(1))n$. In this paper, we consider the codegree density of projective geometries. Employing the moment identity of a subset of $PG_{m}(q)$, we prove (1) $\gamma(PG_{2}(q))=\frac{1}{2}$ for prime power $q\equiv2\pmod{3}$; and (2) $\gamma(PG_{3}(q))=\frac{2}{3}$ for prime power $q\equiv1\pmod{2}$ or $q\equiv2\pmod{3}$. Our results partially solve an open problem proposed by Keevash and Zhao [ J. Combin. Theory Ser. B, 97 (2007), pp. 919--928]. Previously, the codegree density problems for projective geometries were settled only for $PG_{2}(2)$, $PG_{3}(2)$, $PG_{3}(3),$ and $PG_{2}(q)$ with odd prime power $q$.

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.

This paper focuses on constructions of MDS self-dual codes from (extended) generalized Reed-Solomon (GRS) codes. Let$q = r^{2}$be an odd prime power. We show that, there exists a$q$-ary self-dual (extended) GRS code for each even length in the range$[{2r,3r-3}]$, and for each singly even length in the range$[3r-1,4r]$. This extends the only known consecutive range$[2,2r]$to$[{2,3r-3}]$for this case. Furthermore, our general constructions provide many MDS self-dual codes with new parameters which, to the best of our knowledge, were not reported before.

To solve the access-balancing problem in distributed storage systems, we introduce a new combinatorial model, called MinVar model for fractional repetition (FR) codes. Since FR codes are based on graphs or set systems, our MinVar model is characterized by the property that the variance among the sums of block-labels incident to a fixed vertex is minimized. This characterization is different from Dau and Milenkovic's MaxMinSum model, while the minimum sum of labels is maximized. We show that our MinVar model is meaningful by distinguishing labelings with different variances but with the same MaxMin value for some FR codes. By reformulating the MinVar model to an equivalent vertex-labeling problem of graphs, we find several families of optimal FR codes with balanced access frequency, and provide fundamental results for both problems. It is interesting that MinVar model is closely related to the concept of magic-labeling in graph theory.

In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn [ Repeated Patterns in Proper Colourings, preprint, https://arxiv.org/abs/2002.00921 (2020)]. Given a graph $H$ and an integer $k\geqslant 2$, let $f_{k}(n,H)$ be the smallest number of colors $c$ such that there exists a proper edge coloring of the complete graph $K_{n}$ with $c$ colors containing no $k$ vertex-disjoint color-isomorphic copies of $H$. Using algebraic properties of polynomials over finite fields, we give an explicit proper edge coloring of $K_{n}$ and show that $f_{k}(n, C_{4})=\Theta(n)$ when $k\geqslant 3$ and $n\rightarrow\infty$. The methods we used in the edge coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs $G$ and $H,$ let $r(G,H,q)$ be the minimum number of edge colors (not necessarily proper) of $G$, such that the edges of every copy of $H\subseteq G$ together receive at least $q$ distinct colors. Establishing the relation to the Turán number of specified bipartite graphs, we obtain some general lower bounds for $r(K_{n,n},K_{s,t},q)$ with a broad range of $q$.

For a subset $I\subseteq \mathbb{F}_{q}^{n}$, let $\Delta(I)$ be the set of distances determined by the elements of $I.$ The Erdös--Falconer distance problem in $\mathbb{F}_{q}^{n}$ asks for a threshold on the cardinality $|I|$ so that $\Delta(I)$ contains a positive proportion of the whole distance set. In this paper, we consider the analogous question under Hamming distance, which is the most important metric in coding theory. When $q\geqslant 4$ is a fixed prime power and $n$ goes to infinity, our main result shows that, for arbitrary positive proportion $\alpha,$ we can find $\alpha n$ distinct Hamming distances in $\Delta(I)$ if $|I|>q^{(1-\beta)\cdot n},$ where $\beta$ is a positive number depending on $\alpha.$ Unlike using Fourier analytical method as usual, our main tools include the celebrated dependent random choice and some results from additive number theory and coding theory. Hence our bound is much smaller than the previously known bound which was obtained by Fourier analytic machinery.

Splitter sets have been widely studied due to their applications in flash memories, and their close relations with lattice tilings and conflict avoiding codes. In this paper, we give necessary and sufficient conditions for the existence of nonsingular perfect splitter sets, B[-k1, k2](p) sets, where 0 ≤ k1≤ k2= 4. Meanwhile, constructions of nonsingular perfect splitter sets are given. When perfect splitter sets do not exist, we present four new constructions of quasi-perfect splitter sets. Finally, we give a connection between nonsingular splitter sets and Cayley graphs, and as a byproduct, a general lower bound on the maximum size of nonsingular splitter sets is given.

In recent years, several classes of codes have been introduced to provide some fault-tolerance and guarantee system reliability in distributed storage systems, among which locally repairable codes (LRCs for short) play an important role. However, most known constructions are over large fields with sizes close to the code length, which leads to the systems being computationally expensive. Due to this, binary LRCs are of interest in practice. In this paper, we focus on binary linear LRCs with disjoint repair groups. We first derive an explicit bound for the dimension $k$ of such codes, which can be viewed as a generalization of the bounds given in [S. Goparaju and R. Calderbank, Proceedings of the IEEE International Symposium on Information Theory, 2014, pp. 676--680; A. Wang, Z. Zhang, and D. Lin, Proceedings of the IEEE International Symposium on Information Theory, 2017, pp. 2033--2037; and A. Zeh and E. Yaakobi, Proceedings of the IEEE Information Theory Workshop, 2015, pp. 1--5]. We also give several new constructions of binary LRCs with minimum distance $d=6$ based on weakly independent sets and partial spreads, which are optimal with respect to our bound. In particular, for locality $r\in \{2,3\}$ and minimum distance $d=6$, we construct optimal binary linear LRCs with disjoint repair groups for almost all possible parameters. It should be emphasized that some subclasses of these newly constructed codes also attain a general bound of binary LRCs (without the assumption of disjoint repair groups).

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.

Optical orthogonal signature pattern codes (OOSPCs) have played an important role in a novel type of optical code-division multiple-access network for 2-D image transmission. In this paper, we give four direct constructions for OOSPCs based on polynomials and rational functions over finite fields. We also use r -simple matrices to present a recursive construction for OOSPCs. These constructions yield new families of asymptotically optimal OOSPCs.

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.

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict avoiding codes. In this paper, we prove some nonexistence results for nonsingular perfect splitter sets. We also give some necessary conditions for the existence of purely singular perfect splitter sets. Finally, we apply these results to purely singular perfect B[-1, k](m) and B[-2, k](m) sets for small k. In particular, we solve completely the problems left by Schwartz (European J. Combin., vol. 36, pp.130-142, Feb. 2014).

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over GF(q) with length n = (qm-1)/(q -1). Little is known about this class of BCH codes when q > 2. The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n = (3m- 1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated.

Frameproof codes are used to fingerprint digital data. They can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for$w$-frameproof codes of length$N$over an alphabet of size$q$. The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve one of the previous results when$q$is small compared with$w$, say$cq\leq w$for some constant$c\leq q$. Furthermore, we pay special attention to binary frameproof codes. We show a binary$w$-frameproof code of length$N$cannot have more than$N$codewords if$N<\binom {w+1}{2}$.

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.

A long-standing conjecture of Golomb and Welch, raised in 1970, states that there is no perfect r error correcting Lee code of length n for n ≥ 3 and r > 1. In this paper, we study perfect codes in Zn under the l p metric, where 11/p, 31/p. We also give an algebraic construction of quasi-perfect lpcodes for p = 1, r = 2, and 2 <; p <; ∞, r = 21/p.

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict-avoiding codes. The study of k-radius sequences was motivated by some problems occurring in large data transfer. It is observed that the existence of splitter sets yields k-radius sequences of short length. In this paper, we obtain several new results contributing to splitter sets and k-radius sequences. We give some new constructions of perfect splitter sets, as well as some nonexistence results on them. As a byproduct, we obtain some new results on optimal conflict-avoiding codes. Furthermore, we provide several explicit constructions of short k-radius sequences for certain values of n, by establishing the existence of k-additive sequences. In particular, we show that for any fixed k, there exist infinitely many values of n such that fk(n) = 2k/n2+ O(n), where fk(n) denotes the shortest length of an n-ary k-radius sequence. This result partially affirms a conjecture posed by Bondy, Lonc, and Rza̧żewski.

Separating hash families are useful combinatorial structures which are generalizations of many well-studied objects in combinatorics, cryptography, and coding theory. In this paper, using tools from graph theory and additive number theory, we solve several open problems and conjectures concerning bounds and constructions for separating hash families. Firstly, we discover that the cardinality of a separating hash family satisfies a Johnson-type inequality. As a result, we obtain a new upper bound, which is superior to all previous ones. Secondly, we present a construction for an infinite class of perfect hash families. It is based on the Hamming graphs in coding theory and generalizes many constructions that appeared before. It provides an affirmative answer to both Bazrafshan and Trung's open problem on separating hash families and Alon and Stav's conjecture on parent-identifying codes. Thirdly, let $p_t(N,q)$ denote the maximal cardinality of a $t$-perfect hash family of length $N$ over an alphabet of size $q$. Walker and Colbourn conjectured that $p_3(3,q)=o(q^2)$. We verify this conjecture by proving $q^{2-o(1)}

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes.

Given n items with at most d of which being positive, instead of testing these items individually, the theory of combinatorial group testing aims to identify all positive items using as few tests as possible. This paper is devoted to a fundamental and thirty-year-old problem in the nonadaptive group testing theory. A binary matrix is called d-disjunct if the Boolean sum of arbitrary d columns does not contain another column not in this collection. Let T(d) denote the minimal t, such that there exists a t × n d-disjunct matrix with n > t. T(d) can also be viewed as the minimal t such that there exists a nonadaptive group testing scheme, which is better than the trivial one that tests each item individually. It was known that T(d) ≥ (2d+2) and was conjectured that T(d) ≥ (d + 1)2. In this paper, we narrow the gap by proving T(d)/d2≥ (15 + √33)/24, a quantity in [6/7,7/8].

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Cheeet al.for some parameters. The asymptotic lower bound of MCWCs is also examined. Then, we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances$2\sum _{i=1}^{m}w_{i}-2$or$2mw-2w$are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely.

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of Yang et al. into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeros.

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

Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory. In this paper, we present a new construction of quasi-perfect codes for such errors, and we also study the perfect codes with symmetric errors. Moreover, we show some nonexistence results on perfect codes for correcting single error of limited magnitude.

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

One central theme in quantum error-correction is to construct quantum codes that have a relatively large minimum distance. In this paper, we first present a construction of classical linear codes based on certain classes of polynomials. Through these classical linear codes, we are able to obtain some new quantum codes. It turns out that some of the quantum codes exhibited here have better parameters than the ones available in the literature.

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes.

Quantum maximum-distance-separable (MDS) codes form an important family of quantum codes. In this paper, using Hermitian construction and classical constacyclic codes, we construct six classes of quantum MDS codes. Two of these six classes of quantum MDS codes have larger minimum distance than the ones available in the literature. Most of these quantum MDS codes are new in the sense that their parameters are not covered by the codes available in the literature.

The theory of cyclotomy dates back to Gauss and has a number of applications in combinatorics, coding theory, and cryptography. Cyclotomy over a residue class ring${\BBZ}_{v}$can be divided into classical cyclotomy or generalized cyclotomy, depending on$v$prime or composite. In this paper, we introduce a generalized cyclotomy of order$d$over${\BBZ}_{p_{1}^{e_{1}}p_{2}^{e_{2}},\ldots, p_{n}^{e_{n}}}$, which includes Whiteman's and Ding-Helleseth's generalized cyclotomy as special cases. Here,$p_{1},p_{2},\ldots,p_{n}$are pairwise distinct odd primes satisfying$d\vert (p_{i}-1)$for all$1\leq i\leq n$and$e_{1},e_{2},\ldots,e_{n}$are positive integers. We derive some basic properties of the corresponding cyclotomic numbers and obtain a general formula to compute them via classical cyclotomic numbers. As applications, we completely solve an open problem and a conjecture on Whiteman's generalized cyclotomy of order four over${\BBZ}_{p_{1}p_{2}}$. Besides, we also construct an infinite series of near-optimal codebooks over${\BBZ}_{p_{1}p_{2}}$, as well as some infinite series of asymptotically optimal difference systems of sets over${\BBZ}_{p_{1}^{e_{1}}p_{2}^{e_{2}},\ldots,p_{n}^{e_{n}}}$.

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia contents. Separable codes were introduced to detect colluders taking part in the averaging attack, which is the most feasible approach to perform a collusion attack. In this paper, we provide some improved bounds for the size of separable codes. Using a combinatorial technique named grouping coordinates, we have greatly reduced the upper bound. On the other hand, we also provide some lower bounds for the size of separable codes by both probabilistic and deterministic construction methods. In particular, 2̅-separable codes with asymptotically optimal rate are obtained by the deletion method.

Recently, there has been intensive research on the weight distributions of cyclic codes. In this paper, we compute the weight distributions of three classes of cyclic codes with Niho exponents. More specifically, we obtain two classes of binary three-weight and four-weight cyclic codes and a class of nonbinary four-weight cyclic codes. The weight distributions follow from the determination of value distributions of certain exponential sums. Several examples are presented to show that some of our codes are optimal and some have the best known parameters.

Compressed sensing is a novel sampling theory, which provides a fundamentally new approach to data acquisition. It asserts that a sparse or compressible signal can be reconstructed from much fewer measurements than traditional methods. A central problem in compressed sensing is the construction of the sensing matrix. While random sensing matrices have been studied intensively, only a few deterministic constructions are known. Among them, most constructions are based on coherence, which essentially generates matrices with low coherence. In this paper, we introduce the concept of near orthogonal systems to characterize the matrices with low coherence, which lie in the heart of many different applications. The constructions of these near orthogonal systems lead to deterministic constructions of sensing matrices. We obtain a series of m×n binary sensing matrices with sparsity level k=Θ(m(1/2)) or k=O((m/logm)(1/2)). In particular, some of our constructions are the best possible deterministic ones based on coherence. We conduct a lot of numerical experiments to show that our matrices arising from near orthogonal systems outperform several typical known sensing matrices.

The determination of the cross correlation between an m-sequence and its decimated sequence has been a longstanding research problem. Considering a ternary m-sequence of period 33r- 1, we determine the cross correlation distribution for decimations d = 3r+ 2 and d = 32r+ 2, where gcd(r, 3) = 1. Meanwhile, for a binary m-sequence of period 22lm- 1, we make an initial investigation for the decimation d = (22lm- 1)/(2m+ 1) + 2s, where l ≥ 2 is even and 0 <; s <; 2m - 1. It is shown that the cross correlation takes at least four values. Furthermore, we confirm the validity of two famous conjectures due to Sarwate et al. and Helleseth in this case.

Permutation codes have been shown to be useful in power line communications, block ciphers, and multilevel flash memory models. Construction of such codes is extremely difficult. In fact, the only general lower bound known is the Gilbert-Varshamov type bound. In this paper, we establish a connection between permutation codes and independent sets in certain graphs. Using the connection, we improve the Gilbert-Varshamov bound asymptotically by a factor log(n), when the code lengthngoes to infinity.

The determination of weight distribution of cyclic codes involves the evaluation of Gauss sums and exponential sums. Despite some cases where a neat expression is available, the computation is generally rather complicated. In this note, we determine the weight distribution of a class of reducible cyclic codes whose dual codes may have arbitrarily many zeros. This goal is achieved by building an unexpected connection between the corresponding exponential sums and the spectra of Hermitian forms graphs.

Constant-weight codes play an important role in coding theory. The problem of determining the sizes for optimal quaternary constant-weight codes with length$n$, weight 4, and minimum Hamming distance 5 ($(n,5,4)_{4}$codes) has been investigated in several papers. Although some constructions and several infinite families for such codes with length$n\equiv 0,1\pmod4$have been given, the problem is still far from complete. In this paper, we determine the size of an optimal$(n,5,4)_{4}$code for each integer$n\geq 4$leaving 55 lengths unsolved. Especially, for length$n\equiv 0,1\pmod 4$, the existence problem of the equivalent combinatorial object, namely the generalized Steiner system, is solved leaving only seven values undetermined.

Compressed sensing is a sampling technique which provides a fundamentally new approach to data acquisition. Comparing with traditional methods, compressed sensing makes full use of sparsity so that a sparse signal can be reconstructed from very few measurements. A central problem in compressed sensing is the construction of sensing matrices. While random sensing matrices have been studied intensively, only a few deterministic constructions are known. Inspired by algebraic geometry codes, we introduce a new deterministic construction via algebraic curves over finite fields, which is a natural generalization of DeVore's construction using polynomials over finite fields. The diversity of algebraic curves provides numerous choices for sensing matrices. By choosing appropriate curves, we are able to construct binary sensing matrices which are superior to Devore's ones. We hope this connection between algebraic geometry and compressed sensing will provide a new point of view and stimulate further research in both areas.

Constant-weight codes (CWCs) play an important role in coding theory. The problem of determining the sizes for optimal ternary CWCs with length$n$, weight 4, and minimum Hamming distance 5 ($(n,5,4)_{3}$code) has been settled for all positive integers$n\leq 10$or$n > 10$and$n\equiv 1\pmod {3}$with$n\in \{13,52,58\}$undetermined. In this paper, we investigate the problem of constructing optimal$(n,5,4)_{3}$codes for all lengths$n$with the tool of group divisible codes. We determine the size of an optimal$(n,5,4)_{3}$code for each integer$n\geq 4$leaving the lengths$n\in \{12,13,21,27,33,39,45,52\}$unsolved.

The sizes of optimal constant-composition codes (CCCs) of weight 3 have been determined by Chee, Ge, and Ling with four cases in doubt. Group divisible codes (GDCs) played an important role in their constructions. In this paper, we study the problem of constructing optimal quaternary CCCs with Hamming weight 4 and minimum distances 5 or 6 through GDCs and Room square approaches. The problem is solved leaving only five lengths undetermined. Previously, the results on the sizes of such quaternary CCCs were scarce.

Partially balanced incomplete block designs (PBIBDs) have a long history and have been extensively used in agriculture and industrial experiments. Since the book of Clatworthy on two-associate-class partially balanced designs was published in 1973, little progress has been made on the construction of these designs. Group divisible designs (GDDs) are an important type of PBIBD with two associate classes. The existence of a GDD with block size $k=3$ was completely settled by Fu, Rodger, and Sarvate. In their works, the most difficult case to solve was when the number of groups, m, is less than the block size k. The existence of GDDs when $m

Constant-composition codes (CCCs) are a generalization of constant weight codes and permutation codes. The concept of group divisible codes, an analog of group divisible designs in combinatorial design theory, was first introduced by Chee et al. This new class of codes has been shown to be useful in recursive constructions of constant-weight codes and constant-composition codes. In this paper, we consider the problem of determining the maximal sizes of ternary constant-composition codes of weight four and distance five using group divisible codes as the main tools. We determine the exact values for these parameters. The previously known results are those with code length no greater than 10.

One peculiarity with deletion-correcting codes is that perfect t-deletion-correcting codes of the same length over the same alphabet can have different numbers of codewords, because the balls of radius t with respect to the Levenshte[Formula: see text]n distance may be of different sizes. There is interest, therefore, in determining all possible sizes of a perfect t-deletion-correcting code, given the length n and the alphabet size q. In this paper, we determine completely the spectrum of possible sizes for perfect q-ary 1-deletion-correcting codes of length three for all q, and perfect q-ary 2-deletion-correcting codes of length four for almost all q, leaving only a small finite number of cases in doubt.

The notion of a monotonic directed design was introduced to construct difference triangle sets by Chu, Colbourn, and Golomb [SIAM J. Discrete Math., 18 (2005), pp. 741–748]. In this paper, we describe various constructions for monotonic directed designs and establish the necessary and sufficient conditions for the existence of a monotonic directed design with block size 3, and with block size 4 leaving two definite exceptions and six possible exceptions.

Recently, Chee and Ling (“Constructions for$q$-ary constant-weight codes”,IEEE Trans. Inf. Theory, vol. 53, no. 1, 135–146, Jan. 2007 ) introduced a new combinatorial construction for$q$-ary constant-weight codes which reveals a close connection between$q$-ary constant-weight codes and sets of pairwise disjoint combinatorial designs. In this paper, we study the problem of constructing optimal ternary constant-weight codes with Hamming weight four and minimum distance six using this approach. The construction here exploits completely reducible super simple designs and group divisible codes. The problem is solved leaving only two cases undetermined. Previously, the sizes of constant-weight codes of weight four and distance six were known only for those of length no greater than 10.

Motivated by applications in combinatorial group testing for consecutive positives, we investigate a block sequence of a maximum packing $MP (t,k,v)$ which contains the blocks exactly once such that the collection of all blocks together with all unions of two consecutive blocks of this sequence forms an error correcting code with minimum distance d. Such a sequence is usually called a block sequence with consecutive unions having minimum distance d, and denoted by $BSCU (t,k,v|d)$. In this paper, we show that the necessary conditions for the existence of $BSCU (3,4,v|4)$s of Steiner quadruple systems, namely, $v\equiv2,4$ (mod 6) and $v\geq4$, are also sufficient, excepting $v=8,10$.

For a v-set V, let $\mathcal{A}$ be a collection of $r\times c$ arrays with elements in V. A pair $(V,\mathcal{A})$ is called an $r\times c$ grid-block design if every two distinct elements i and j in V occur exactly once in the same row or in the same column of an array in $\mathcal{A}$. This design originated from the use of DNA library screening. In this paper, we show the existence of $r\times 4$ grid-block designs with $r=3,4$. We settle completely for the case of $r=4$ and almost completely for the case of $r=3$, leaving 15 orders undetermined.

Frequency hopping (FH) sequences play a key role in frequency hopping spread spectrum communication systems. In order to evaluate the performance of FH sequences, Lempel and Greenberger (1974) and Peng and Fan (2004) derived lower bounds on their Hamming auto- and cross-correlations. In this paper, we construct families of FH sequences with Hamming correlations meeting those bounds by combinatorial and algebraic techniques. We first construct optimal families consisting of a single FH sequence with maximum Hamming correlation equal to 2 from a combinatorial approach. Then we investigate families consisting of multiple FH sequences. We provide a combinatorial characterization for such families, and present a recursive method to construct them by means of this characterization. We also describe two algebraic constructions for such families of FH sequences, generalizing those of Ding, Moisio, and Yuan (2007). As a consequence, many new optimal families of FH sequences are obtained.

In order to reduce the number of add-drop multiplexers (ADMs) in SONET/WDM networks using wavelength add-drop multiplexing, certain graph decompositions can be used to form a “grooming” that specifies the assignment of traffic to wavelengths. When traffic among nodes is all-to-all and uniform, the drop cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The number of ADMs required is this drop cost. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{7}$ of the wavelength capacity, is determined within an additive constant. Indeed when the number n of sites satisfies $n \equiv 1$ (mod 3) and $n \neq 19$, the determination is exact; when $n \equiv 0$ (mod 3), $n \not\equiv 18$ (mod 24), and n is large enough, the determination is also exact; and when $n \equiv 2$ (mod 3) and n is large enough, the gap between the cost of the best construction and the cost of the lower bound is independent of n and does not exceed 4.

The concept of group divisible codes, a generalization of group divisible designs with constant block size, is introduced in this paper. This new class of codes is shown to be useful in recursive constructions for constant-weight and constant-composition codes. Large classes of group divisible codes are constructed which enabled the determination of the sizes of optimal constant-composition codes of weight three (and specified distance), leaving only four cases undetermined. Previously, the sizes of constant-composition codes of weight three were known only for those of sufficiently large length.

The radar array problem arises from the need to design frequency hopping sequences with small out-of-phase autocorrelations. It assumes the reflected signals have negligible Doppler shifts, so the correlations are calculated along the time axis only. In this correspondence, a systematic construction for radar arrays is provided by means of homogeneous uniform difference matrices. A systematic construction for properly centered permutation matrices, a special kind of homogeneous uniform difference matrices, is also provided, which partially solves the open problems posed by Zhang and Tu.

Motivated by the connection between graph decompositions and traffic grooming in optical networks, we continue the investigation of the existence problem for $(K_5 \setminus e)$-designs of order n. It is proved that the necessary conditions for the existence of such designs are also sufficient with 3 definite exceptions $(n=9,10,18)$ and 12 possible exceptions with $n=234$ being the largest. This gives a near solution for the long standing problem posed by Bermond et al. in [Ars Combin., 10 (1980), pp. 211–254]. As a consequence, we also give an optimal grooming on n nodes with $C=9$ when such a $(K_5 \setminus e)$-design of order n exists.

SONET/WDM networks using wavelength add-drop multiplexing can be constructed using certain graph decompositions used to form a grooming, consisting of unions of primitive rings. The cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{6}$ of the wavelength capacity, is determined with a finite number of possible exceptions. Indeed, when the number N of sites satisfies $N \equiv 1 \pmod{3}$, the determination is complete, and when $N \equiv 2 \pmod{3}$, the only value left undetermined is N = 17. When $N \equiv 0 \pmod{3}$, a finite number of values of N remain, the largest being N = 2580. The techniques developed rely heavily on tools from combinatorial design theory.

The notion of a splitting authentication code is very important in the context of an authentication code with arbitration. Ogata et al. [Discrete Math., 279 (2004), pp. 383--405] characterized an optimal splitting authentication code in terms of a splitting balanced incomplete block design (BIBD). A $(v,u \times c,1)$-splitting BIBD is a pair $({\cal V}, {\cal B})$, where ${\cal V}$ is a v-set of points and ${\cal B}$ is a collection of $u \times c$ arrays, called blocks, with entries from ${\cal V}$, such that any point of ${\cal V}$ can occur at most once in any block, and forany two distinct points x and y of ${\cal V}$, there is exactly one block of ${\cal B}$ in which x and y occur in different rows. In this paper, we describe various combinatorial constructions for splitting BIBDs (or, equivalently, optimal splitting authentication codes). We show that the necessary conditions for the existence of a $(v,u \times c,1)$-splitting BIBD (or, equivalently, an optimal c-splitting authentication code with u source states and v messages) are also sufficient for (u,c) = (2,2t) for any positive integer t,(u,c) = (2,3) with a definite exception of v = 10,(u,c) = (3,2) with a definite exception of v =9, and (u,c) = (4,2) with two possible exceptions of v = 49,385.

Four direct constructions, three of which are by way of skew starters, are given in this correspondence for optimal (/spl upsi/, 4, 1) optical orthogonal codes (OOC's). These improve the known existence results concerning optimal (/spl upsi/, 4, 1)-OOCs. In particular, it is shown that an optimal (/spl upsi/, 4, 1)-OOC exists for all positive integers /spl upsi//spl equiv/6 (mod 12) or /spl upsi//spl equiv/24 (mod 48). It is also shown that an optimal (12/spl upsi/, 4, 1)-OOC exists for any positive integer /spl upsi/ whose prime factors are all congruent to 1 modulo 4.