The study of group testing aims to develop strategies to identify a small set of defective items among a large population using a few pooled tests. The established techniques have been highly beneficial in a broad spectrum of applications ranging from channel communication to identifying COVID-19-infected individuals efficiently. Despite significant research on group testing and its variants since the 1940s, testing strategies robust to deletion noise have not been explored. Deletion errors, common in practical systems like wireless communication and data storage, cause asynchrony in tests, rendering current group testing methods ineffective. In this work, we introduce non-adaptive group testing strategies resilient to deletion noise. We establish the necessary and sufficient conditions for successfully identifying defective items despite adversarial deletions of test outcomes. The study also presents constructions of testing matrices with a nearoptimal number of tests and develops efficient and super-efficient recovery algorithms.

This paper introduces a Byzantine Fault Tolerance consensus mechanism tailored for distributed networks with synchronized clocks. The system is designed to manage fByzantine nodes by dividing time into slots, each comprising $f+2$ instants. At each instant nodes are tasked with proposing blocks of transactions to be added to a directed acyclic graph (DAG). At the end of each slot, they generate commitments to the ordering of blocks created in previous slots. Unlike traditional protocols that rely on threshold clocks, our protocol allows nodes to continue constructing their DAGs and committing to past slots even during network partitions. Upon recovery, slot commitment synchronization is facilitated through a random coin, leading to the merging of DAGs. This process enables the finalization of the common slot commitment chain and the sequencing of all blocks committed to that chain. Our protocol tolerates up to 33% of Byzantine nodes in an eventually lock-step synchronous model and supports fast two-instant UTXO-transaction confirmation during periods of synchrony. Furthermore, we demonstrate that by applying the same protocol and optimistically sequencing committed blocks, it is possible to tolerate up to 50% of Byzantine nodes in a slot-sleepy model, wherein nodes may be either awake or asleep for each slot.

This paper is a Systematization of Knowledge (SoK) that focuses on Directed Acyclic Graph (DAG)-based consensus protocols in Distributed Ledger Technologies (DLTs). Our study evaluates their impact on performance and their tradeoffs concerning consistency, availability, and partition tolerance, as postulated by the CAP theorem. We delineate the key functionalities and tradeoffs of DAGbased consensus protocols, highlighting iterative improvements and deviations from foundational models. Additionally, we identify research gaps and suggest directions for future work to refine DAG-based consensus mechanisms.

We consider the problem of constructing a code capable of correcting a single long tandem duplication error of variable length. As the main contribution of this paper, we present an efficiently encodable code of length n + 1 and redundancy 1 that can correct a single duplication of length at least K = 4•⌈logn⌉+1. We also show that in the class of codes correcting a single long duplication with redundancy 1, the value K in our construction is order-optimal.

The Unspent Transaction Output (UTXO) model is commonly used in the field of Distributed Ledger Technology (DLT) to transfer value between participants. One of its advantages is that it allows parallel processing of transactions, as independent transactions can be added in any order. This property of order invariance and parallelisability has potential benefits in terms of scalability. However, since the UTXO Ledger is an append-only data structure, this advantage is compromised through the presence of conflicting transactions. We propose an extended UTXO Ledger model that optimistically updates the ledger and keeps track of the dependencies of the possible conflicts. In the presence of a conflict resolution mechanism, we propose a method to reduce the extended ledger back to a consistent UTXO Ledger.

This paper is a collection of results on combinatorial properties of codes for the Z-channel. A Z-channel with error fraction$\tau $takes as input a length-$n$binary codeword and injects in an adversarial manner up to$n\tau $asymmetric errors, i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that the largest$(L-1)$-list-decodable code for the Z-channel with error fraction$\tau $has exponential size (in$n$) if$\tau $is less than a critical value that we call the$(L-1)$-list-decoding Plotkin point and has constant size if$\tau $is larger than the threshold. The$(L-1)$-list-decoding Plotkin point is known to be$L^{-({1}/{L-1})} - L^{-({L}/{L-1})} $, which equals 1/4 for unique-decoding with$L-1=1 $. In this paper, we derive various results for the size of the largest codes above and below the list-decoding Plotkin point. In particular, we show that the largest$(L-1)$-list-decodable code$\varepsilon $-above the Plotkin point, for any given sufficiently small positive constant$\varepsilon >0 $, has size$\Theta _{L}(\varepsilon ^{-3/2})$for any$L-1\ge 1$. We also devise upper and lower bounds on the exponential size of codes below the list-decoding Plotkin point.

This paper studies combinatorial properties of codes for the Z-channel. A Z-channel with error fraction τ takes as input a length-n binary codeword and injects in an adversarial manner up to nτ asymmetric errors, i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that the largest (L − 1)-list-decodable code for the Z-channel with error fraction τ has exponential (in n) size if τ is less than a critical value that we call the Plotkin point and has constant size if τ is larger than the threshold. The (L−1)-list-decoding Plotkin point is known to be ${L^{ - \frac{1}{{L - 1}}}} - {L^{ - \frac{L}{{L - 1}}}}$. In this paper, we show that the largest (L−1)-list-decodable code ε-above the Plotkin point has size ΘL(ε−3/2) for any L − 1 ≥ 1.

In this work, we consider q-ary signature codes of length k and size n for a noisy adder multiple access channel. A signature code in this model has the property that any subset of codewords can be uniquely reconstructed based on any vector that is obtained from the sum (over integers) of these codewords. We show that there exists an algorithm to construct a signature code of length $k = \frac{{2n\log 3}}{{(1 - 2\tau )\left( {\log n + (q - 1)\log \frac{\pi }{2}} \right)}} + \mathcal{O}\left( {\frac{n}{{\log n(q + \log n)}}} \right)$ capable of correcting τk errors at the channel output, where $0 \leq \tau < \frac{{q - 1}}{{2q}}$. Furthermore, we present an explicit construction of signature codewords with polynomial complexity being able to correct up to $\left( {\frac{{q - 1}}{{8q}} - \varepsilon } \right)k$ errors for a codeword length $k = \mathcal{O}\left( {\frac{n}{{\log \log n}}} \right)$, where ε is a small non-negative number. Moreover, we prove several non-existence results (converse bounds) for q-ary signature codes enabling error correction.

In this paper, we discuss two-stage encoding algorithms capable of correcting a fraction of asymmetric errors. Suppose that the encoder transmits$n$binary symbols$(x_{1},\ldots,x_{n})$one-by-one over the Z-channel, in which a 1 is received only if a 1 is transmitted. At some designated moment, say$n_{1}$, the encoder uses noiseless feedback and adjusts further encoding strategy based on the partial output of the channel$(y_{1},\ldots,y_{n_{1}})$. The goal is to transmit error-free as much information as possible under the assumption that the total number of errors inflicted by the Z-channel is limited by$\tau n$,$0 < \tau < 1$. We propose an encoding strategy that uses a list-decodable code at the first stage and a high-error low-rate code at the second stage. This strategy and our converse result yield that there is a sharp transition at$\tau =\max \limits _{0 < w < 1}\frac {w + w^{3}}{1+4w^{3}}\approx 0.44$from positive rate to zero rate for two-stage encoding strategies. As side results, we derive bounds on the size of list-decodable codes for the Z-channel and prove that for a fraction$1/4+ \varepsilon $of asymmetric errors, an error-correcting code contains at most$O(\varepsilon ^{-3/2})$codewords.

We consider construction of deletion and substitution correcting codes with low redundancy and efficient encoding/ decoding. First, by simplifying the method of Simaet al. (ISIT 2020), we construct a family of binary single-deletion$s$-substitution correcting codes with redundancy$(s+1) (2s+1)\log _{2} n+o(\log _{2} n)$and encoding complexity$O(n^{2})$, where$n$is the blocklength of the code and$s\geq 1$. The construction can be viewed as a generalization of Smagloyet al.’s construction (ISIT 2020), and for the special case of$s=1$, our construction is a slight improvement in redundancy of the existing works. Further, we modify the syndrome compression technique by combining a precoding process and construct a family of systematic$t$-deletion$s$-substitution correcting codes with polynomial time encoding/decoding algorithms for both binary and nonbinary alphabets, where$t\geq 1$and$s\geq 1$. Specifically, our binary$t$-deletion$s$-substitution correcting codes of length$n$have redundancy$(4t+3s)\log _{2}n+o(\log _{2}n)$, whereas, for$q$being a prime power, the redundancy of$q$-ary$t$-deletion$s$-substitution codes is asymptotically$\left({4t+4s-1-\lfloor \frac {2s-1}{q}\rfloor }\right)\vphantom {{\lfloor \frac {2s-1}{q}\rfloor }_{j}}\log _{q} n + o(\log _{q}n)$as$n\to \infty $. We also construct a family of binary systematic$t$-deletion correcting codes (i.e.,$s=0$) with redundancy$(4t-1)\log _{2} n+o(\log _{2} n)$. The proposed constructions improve upon the redundancy of the state-of-the-art constructions.

We consider the problem of constructing codes that can correct deletions that are localized within a certain part of the codeword that is unknown a priori. Namely, the model that we study is when at most$k$deletions occur in a window of size$k$, where the positions of the deletions within this window are not necessarily consecutive. Localized deletions are thus a generalization of burst deletions that occur in consecutive positions. We present novel explicit codes that are efficiently encodable and decodable and can correct up to$k$localized deletions. Furthermore, these codes have$\log n+\mathcal{O}(k\log^{2}(k\log n))$redundancy, where$n$is the length of the information message, which is asymptotically optimal in$n$for$k=o(\log n/(\log\log n)^{2})$.

A new Z-channel coding problem is addressed in this paper. Suppose that the encoder transmits$n$binary symbols ($x_{1}, \ldots, x_{n}$) one-by-one over the Z-channel, in which a 1 is received if and only if a 1 is transmitted. At some designated moment, say$n_{1}$, the encoder uses noiseless feedback and adjusts further encoding strategy based on the partial output of the channel ($y_{1}, \ldots, y_{n_{1}}$). The goal is to transmit error-free as much information as possible under the assumption that the total number of errors inflicted by the Z-channel is limited by$\tau n, 0 < \tau < 1$. As the main contribution, we precisely characterize when exponential-sized (or positive-rate) codes exist for this model. Our proof relies on the concepts of list-decodable codes and high-error low-rate codes.

In this paper, by applying the precoding technique in conjunction with the syndrome compression approach, we construct systematic$t$-deletion$s$-substitution correcting codes, where$t$and$s$are fixed positive integers. The redundancy of our construction is$(4t+3s)\log n+o(\log n)$for the binary case and$(4t+4s-1- \mathrm{L}\frac{2s-1}{q}\rfloor)\bar{\mathrm{l}}\text{og}_{q}n+o(\bar{\mathrm{l}}\text{og}_{q}n)$for the$q$-ary case, where$n$is the length of the codes and$q> 2$is a fixed prime power.11If$x$is a positive real number, then$\log_{q}\alpha$is the logarithm of$x$with base$q$; if$q=2$, we simply denote$\log x=\text{lo}\bar{\mathrm{g}}_{q}x$. We also construct binary t-deletion correcting codes (i.e.,$s=0$) with redundancy$(4t-1)\log n+o(\log n)$. The encoding/decoding complexities of all constructions are polynomial in$n$.

We consider the problem of coding for the substring channel, in which information strings are observed only through their (multisets of) substrings. Because of applications to DNA-based data storage, due to DNA sequencing techniques, interest in this channel has renewed in recent years. In contrast to existing literature, we consider a noisy channel model, where information is subject to noise before its substrings are sampled, motivated by in-vivo storage. We study two separate noise models, substitutions or deletions. In both cases, we examine families of codes which may be utilized for error-correction and present combinatorial bounds. Through a generalization of the concept of repeat-free strings, we show that the added required redundancy due to this imperfect observation assumption is sublinear, either when the fraction of errors in the observed substring length is sufficiently small, or when that length is sufficiently long. This suggests that no asymptotic cost in rate is incurred by this channel model in these cases.

In this paper, we address two learning problems. Suppose a family of $\ell$ unknown sparse vectors is fixed, where each vector has at most $k$ non-zero elements. In the first problem, we concentrate on robust learning the supports of all vectors from the family using a sequence of noisy responses. Each response to a query vector shows the sign of the inner product between a randomly chosen vector from the family and the query vector. In the second problem, we aim at designing queries such that all sparse vectors from the family can be approximately reconstructed based on the error-free responses. This learning model was introduced in the work of Gandikota et al., 2020, and these problems can be seen as generalizations of support recovery and approximate recovery problems, well-studied under the framework of 1-bit compressed sensing. As the main contribution of the paper, we prove the existence of learning algorithms for the first problem which work without any assumptions. Under a mild structural assumption on the unknown vectors, we also show the existence of learning algorithms for the second problem and rigorously analyze their query complexity.

Lifted Reed-Solomon and multiplicity codes are classes of codes, constructed from specific sets of$m$-variate polynomials. These codes allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined for the bi-variate case to construct lifted multiplicity codes, a generalization of lifted codes that can offer further rate improvements. We continue the study of these codes by first establishing new lower bounds on the rate of lifted Reed-Solomon codes for any number of variables$m$, which improve upon the known bounds for any$m\ge 4$. Next, we use these results to provide lower bounds on the rate and distance of lifted multiplicity codes obtained from polynomials in an arbitrary number of variables, which improve upon the known results for any$m\ge 3$. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of$m$-variate monomials whose restriction to an arbitrary line in${\mathbb {F}}_{q}^{m}$is equivalent to a low-degree univariate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables$m$is fixed and the alphabet size$q=2^\ell $is large. Using these results, we give a new explicit construction of batch codes utilizing lifted Reed-Solomon codes. For some parameter regimes, these codes have a better trade-off between parameters than previously known batch codes. Further, we show that lifted multiplicity codes have a better trade-off between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions, thereby providing the best known PIR codes for some parameter regimes. Additionally, we present a new local self-correction algorithm for lifted multiplicity codes.

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction$\tau \ge 1/4$vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with$n$transmissions that achieves a positive rate for any fraction of errors$\tau < 1$and$n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes.

Guo, Kopparty and Sudan have initiated the study of error-correcting codes derived by lifting of affine-invariant codes. Lifted Reed-Solomon (RS) codes are defined as the evaluation of polynomials in a vector space over a field by requiring their restriction to every line in the space to be a codeword of the RS code. In this paper, we investigate lifted RS codes and discuss their application to batch codes, a notion introduced in the context of private information retrieval and load-balancing in distributed storage systems. First, we improve the estimate of the code rate of lifted RS codes for lifting parameter m ≥ 3 and large field size. Second, a new explicit construction of batch codes utilizing lifted RS codes is proposed. For some parameter regimes, our codes have a better trade-off between parameters than previously known batch codes.

In this paper, we present an efficiently encodable and decodable code construction that is capable of correcting a burst of deletions of length at most k. The redundancy of this code is log n + k(k + 1)/2 log log n + ckfor some constant ckthat only depends on k and thus is scaling-optimal. The code can be split into two main components. First, we impose a constraint that allows us to locate the burst of deletions up to an interval of size roughly log n. Then, with the knowledge of the approximate location of the burst, we use several shifted Varshamov-Tenengolts codes to correct the burst of deletions, which only requires a small amount of redundancy since the location is already known up to an interval of small size. Finally, we show how to efficiently encode and decode the code.

We study the duplication with transposition distance between strings of length n over a q-ary alphabet and their roots. In other words, we investigate the number of duplication operations of the form x = (abcd) →y = (abcbd), where x and y are strings and a, b, c and d are their substrings, needed to get a q-ary string of length n starting from the set of strings without duplications. For exact duplication, we prove that the maximal distance between a string of length at most n and its root has the asymptotic order n/logn. For approximate duplication, where a β-fraction of symbols may be duplicated incorrectly, we show that the maximal distance has a sharp transition from the order n/logn to logn at β = (q - 1)/q. The motivation for this problem comes from genomics, where such duplications represent a special kind of mutation and the distance between a given biological sequence and its root is the smallest number of transposition mutations required to generate the sequence.

Lifted Reed-Solomon codes, a subclass of lifted affine-invariant codes, have been shown to be of high rate while preserving locality properties similar to generalized Reed-Muller codes, which they contain as subcodes. This work introduces a simple bounded distance decoder for (subcodes of) lifted affine-invariant codes that is guaranteed to decode up to half of an asymptotically tight bound on their minimum distance. Further, long q-ary lifted affine-invariant codes are shown to correct almost all error patterns of relative weight $\frac{{q - 1}}{q} - \varepsilon $ for ε > 0.

Lifted Reed-Solomon codes and multiplicity codes are two classes of evaluation codes that allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined to construct lifted bi-variate multiplicity codes, that can further improve on the rate. We continue the study of these codes by providing lower bounds on the rate and distance for lifted multiplicity codes obtained from polynomials in an arbitrary number of variables. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of m-variate monomials whose restriction to an arbitrary line in Fqmis equivalent to a low-degree uni-variate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables m is fixed and the alphabet sizeq=2ℓis large. For some parameter regimes, lifted multiplicity codes are then shown to have a better tradeoff between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions.

A new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Assume that the encoder transmits $$n$$ binary symbols one by one over a channel in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about insertions or deletions that have occurred within the previous transmission, and the encoding strategy can be adapted accordingly. The goal is to design an encoder that is able to transmit error-free as much information as possible under the assumption that the total number of deletions and insertions is limited by $$\tau n$$ , $$0<\tau<1$$ . We show how this problem can be reduced to the problem of transmitting messages over the substitution channel. Thereby, the maximal asymptotic rate of feedback insertion-deletion codes is completely established. The maximal asymptotic rate for the adversarial substitution channel has been partially determined by Berlekamp and later completed by Zigangirov. However, the analysis of the lower bound by Zigangirov is quite complicated. We revisit Zigangirov's result and present a more elaborate version of his proof.

In this paper, we derive the exact weight distributions that emerge during each stage of successive cancellation decoding of polar codes. Though we do not compute the distance spectrum of polar codes, the results allow us to get an estimate of the decoding error probability and to show a link between the first nonzero components of the weight distribution and the partial order between the synthetic channels. Also, we establish the minimal distance between two cosets associated with two paths that differ in two positions. This can be regarded as a first step toward analyzing the weight distributions for successive cancellation list decoding.

A primitive k-batch code encodes a string x of length n into a stringy of length N, such that each multiset of k symbols from x has k mutually disjoint recovering sets from y. In this paper, we discuss new constructions of binary primitive batch codes. First, we develop novel explicit and random coding constructions of linear primitive batch codes based on finite geometries. Second, a new explicit coding construction of binary primitive batch codes based on bivariate lifted multiplicity codes is provided. For any k = nεwith ε ∈ (0, 0.47) \ {1/5, 1/4}, our proposed codes have a better trade-off between the redundancy and the parameters k, n than previously known batch codes.

A primitive k-batch code encodes a string x of length n into string y of length N, such that each multiset of k symbols from x has k mutually disjoint recovering sets from y. We develop new explicit and random coding constructions of linear primitive batch codes based on finite geometry. In some parameter regimes, our proposed codes have lower redundancy than previously known batch codes.

In a deductive game for two players, SF and PGOM, SF conceals an n-digit number x = x1, …, xn in base q, and PGOM, who knows n and q, tries to identify x by asking a number of questions, which are answered by SF. Each question is an n-digit number y = y1, …, yn in base q; each answer is the number of subscripts i such that xi = yi. Moreover, we require PGOM send all the questions at once. We show that the minimum number of questions required to determine x is (2+oq(1))n/ logq n. Our result closes the gap between the lower bound attributed to Erdős and Rényi and the upper bounds developed subsequently by Lindström, Chvátal, Kabatianski, Lebedev and Thorpe. A more general problem is to determine the asymptotic formula of the metric dimension of Cartesian powers of a graph. We state the class of graphs for which the formula can be determined, and the smallest graphs for which we did not manage to settle.

A binary matrix is called an${s}$-separable codefor thedisjunctive multiple-access channel(disj-MAC) if Boolean sums of sets of${s}$columns are all distinct. The well-known issue of the combinatorial coding theory is to obtain upper and lower bounds on the rate of${s}$-separable codes for the${disj}$-MAC. In our paper, we generalize the problem and discuss upper and lower bounds on the rate of${q}$-ary${s}$-separable codes for the models of noiselesssymmetricMAC, i.e., at each time instant the output signal of MAC is a symmetric function of its${s}$input signals.

The exact values of the optimal symmetric rate point in the Cover--Leung capacity region of the two-user union channel with complete feedback were determined by Willems when the size of the input alphabet is 2, and by Vinck, Hoeks and Post when the size is at least 6. We complete this line of research when the size of the input alphabet is 3, 4 or 5. The proof hinges on the technical lemma that concerns the maximal joint entropy of two independent random variables in terms of their probability of equality. For the zero-error capacity region, using superposition coding, we provide a practical near-optimal communication scheme which improves all the previous explicit constructions.

A binary matrix is called an s-separable code for the disjunctive multiple-access channel (disj-MAC) if Boolean sums of sets of$s$columns are all distinct. The well-known issue of the combinatorial coding theory is to obtain upper and lower bounds on the rate of s-separable codes for the disj-MAC. In our paper, we generalize the problem and discuss upper and lower bounds on the rate of q-ary s-separable codes for models of noiseless symmetric MAC, i.e., at each time instant the output signal of MAC is a symmetric function of its$s$input signals.

Let 1 ≤ s0: the circuit is s-active} versus the alternative hypothesis {H1: the circuit is s-defective}. Along with the conventional decoding algorithm based on the known random set of positive responses and disjunctive s-codes, we consider a T-weight decision rule which is based on the simple comparison of a fixed threshold T, 1 ≤ T <; N, with the known random number of positive responses p, 0 ≤ p ≤ N.

Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph Hun= H(V, E) by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family F(t, s, ℓ) of localized hypergraphs for which the total number of vertices |V| = t, the number of edges |E| ≤ s, s ≪ t, and the cardinality of any edge |e| ≤ ℓ, ℓ ≪ t. Our goal is to identify all edges of Hun∈ F(t, s, ℓ) by using the minimal number of tests. We develop an adaptive algorithm that matches the information theory bound, i.e., the total number of tests of the algorithm in the worst case is at most sℓ log2t(1+o(1)). We also discuss a probabilistic generalization of the problem.

Group testing is a well known search problem that consists in detecting up to s, s ≪ t, defective elements of the set [t] = {1, . . . , t} by carrying out tests on properly chosen subsets of [t]. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a hypergraph approach to searching defective elements. For the case s = 2 and t → ∞, we design an explicit construction, which makes use of 2 log2t(1 + o(1)) tests in the worst case and consists of 4 stages. For the general case of fixed s > 2 and t → ∞, we provide an explicit construction, which uses (2s - 1) log2t(1+o(1)) tests and consists of 2s - 1 rounds.

In this paper, we consider symmetric disjunctive list-decoding (SLD) codes, which are a class of binary codes based on a symmetric disjunctive sum (SDS) of binary symbols. By definition, the SDS takes values from the ternary alphabet {0; 1; *}, where the symbol * denotes “erasure”. Namely: SDS is equal to 0 (1) if all its binary symbols are equal to 0 (1), otherwise SDS is equal to *. The main purpose of this work is to obtain bounds on the rate of these codes.

We discover some important properties of cover-free (CF) codes, separating system (SS) codes and completely separating system (CSS) codes connected with the concept of constant weight CF codes. New upper and lower bounds on the rate of CF and SS codes based on the known results for CF and CSS codes are obtained. Tables of numerical values for the improved upper and lower bounds are presented.

An s-subset of codewords of a binary code X is said to be (s, ℓ)-bad in X if the code X contains a subset of other ℓ codewords such that the conjunction of the ℓ codewords is covered by the disjunctive sum of the s codewords. Otherwise, the s-subset of codewords of X is called (s, ℓ)-good in X. A binary code X is said to be a cover-free (CF) (s, ℓ)-code if the code X does not contain (s, ℓ)-bad subsets. In this paper, we introduce a natural probabilistic generalization of CF (s, ℓ)-codes, namely: a binary code X is said to be an almost CF (s, ℓ)-code if the relative number of its (s, ℓ)-good s-subsets is close to 1. We develop a random coding method based on the ensemble of binary constant weight codes to obtain lower bounds on the capacity of such codes. Our main result shows that the capacity for almost CF (s, ℓ)-codes is essentially greater than the rate for ordinary CF (s, ℓ)-codes.

A binary code is called a superimposed cover-free (s, ℓ)-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of ℓ sets is covered by the union of s others. A binary code is called a superimposed list-decoding sL-code if the code is identified by the incidence matrix of a family of finite sets in which the union of any s sets can cover not more than L - 1 other sets of the family. For L = ℓ = 1, both of the definitions coincide and the corresponding binary code is called a superimposed s-code. Our aim is to obtain new lower and upper bounds on the rate of the given codes. The most interesting result is a lower bound on the rate of superimposed cover-free (s, ℓ)-codes based on the ensemble of constant weight binary codes. If the parameter ℓ ≥ 1 is fixed and s → ∞, then the ratio of this lower bound to the best known upper bound converges to the limit 2 e-2= 0.271. For the classical case ℓ = 1 and s ≥ 2, the given statement means that the upper bound on the rate of superimposed s-codes obtained by A.G. Dyachkov and V.V. Rykov (1982) is asymptotically attained to within a constant factor a, 2 e-2≤ a ≤ 1.

The concept of a generalized stem similarity function and the corresponding DNA codes are introduced. We give parameters for some optimal constructions called maximum distance separable DNA codes and obtain bounds on the maximum size of DNA codes.