Many communication applications incorporate eventtriggered behavior, where the conventional Shannon capacity may not effectively gauge performance. Consequently, we advocate for the concept of identification capacity as a more suitable metric for assessing these systems. We consider deterministic identification codes for the Gaussian AWGN, the slow fading, and the fast fading channels with power constraints. We prove lower bounds on capacities for the slow and the fast fading channels with side information for a wide range of fading distributions. Additionally, we present the code construction with efficient encoding which achieves the lower bound on capacity both for the slow and the fast fading channels. At last, we prove the same lower bound on the capacity of the fast fading channel without side information, i.e., the same lower bound holds even when the receiver does not know the fading coefficients. As a result we show that compared with Shannon's message transmission paradigm we achieved completely different capacity scaling for deterministic identification codes for all relevant fading channels.

Many communication applications incorporate event-triggered behavior, where the conventional Shannon capacity may not effectively gauge performance. Consequently, we advocate for the concept of identification capacity as a more suitable metric for assessing these systems. We consider deterministic identification codes for the Gaussian AWGN, the slow fading, and the fast fading channels with power constraints. We prove lower bounds on capacities for the slow and the fast fading channels with side information for a wide range of fading distributions. Additionally, we present the code construction with efficient encoding which achieves the lower bound on capacity both for the slow and the fast fading channels. At last, we prove the same lower bound on the capacity of the slow and fast fading channel without side information, i.e., the same lower bound holds even when the receiver does not know the fading coefficients. As a result we show that compared with Shannon’s message transmission paradigm we achieved completely different message set scaling for deterministic identification codes for all relevant fading channels.

Many communication applications are event-triggered, but current applications still use the Shannon communication model to transmit and decode messages. Due to the ever-growing number of users in communication networks, this leads to a weakening of performance. To counteract this, it makes sense to use post-Shannon methods such as deterministic identification (DI) codes. The information theory analysis carried out so far has shown how performance can be increased through DI codes. In this paper we provide a new constructive proof of the capacity of deterministic identification codes for discrete memoryless channels (DMC), while so far only existence proofs exist. Based on this idea, we implement DI codes of finite length and analyze their performance both analytically and experimentally. For the latter, we build a prototype using software-defined radios and a noise generator.

In this paper we consider combinatorial secure codes in traitor tracing for protecting copyright of multimedia content. First, we introduce a new notion of secure codes with list decoding (SCLDs) for collusion-resistant multimedia fingerprinting, which includes many existing types of fingerprinting codes as special cases. Next, we build efficient identifying algorithms for SCLDs with complete traceability and establish bounds on its largest possible code rate. In comparison with the existing fingerprinting codes, it is shown that SCLDs have not only much more efficient traceability than separable codes but also a much larger code rate than frameproof codes. As a byproduct, new bounds on the largest code rate of binary separable codes are established as well. Furthermore, a two-stage dynamic traitor tracing framework is proposed for multimedia fingerprinting in the dynamic scenario, which could not only efficiently achieve the complete traceability but also provide a much larger capacity than the static scenario.

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.

In this paper, the problem of correction of a single error in q-ary symmetric channel with noiseless feedback is considered. We propose an algorithm to construct codes with feedback inductively. For all prime power q we prove that two instances of feedback are sufficient to transmit over the q-ary symmetric channel the same number of messages as in the case of complete feedback. Our other contribution is the construction of codes with one-time feedback with the same parameters as Hamming codes for q that is not a prime power. We also construct single-error-correcting codes with one-time feedback of size qn−2for arbitrary q and n ≤ q + 1, which can be seen as an analog for Reed-Solomon codes.

Abstract In this paper we consider complete traceability multimedia fingerprinting codes resistant to averaging attacks and adversarial noise. Recently it was shown that there are no such codes for the case of an arbitrary linear attack. However, for the case of averaging attacks complete traceability multimedia fingerprinting codes of exponential cardinality resistant to constant adversarial noise were constructed in Egorova et al. (Probl Inf Transm 56(4):388–398, 2020). We continue this work and provide an improved lower bound on the rate of these codes.

Traitor tracing is a mathematical approach of protecting copyright of multimedia content. In this paper we propose a new concept of secure codes with list decoding (SCLD) for collusion-resistant multimedia fingerprinting, which could include many existing classes of fingerprinting codes as special cases. Furthermore, we build an efficient identifying algorithm for SCLD and establish bounds on its largest asymptotic code rate. In comparison with the existing fingerprinting codes, it is shown that SCLD has not only much more efficient traceability than separable codes but also a much larger code rate than frameproof codes.

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

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.

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.

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.

Group testing is a well-known search problem that consists in detecting of s defective members of a set of t samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, a multistage group testing problem is considered. Our goal is to construct a multistage search procedure, having asymptotically the same number of tests as the optimal adaptive algorithm. We propose a new approach to designing multistage algorithms, which allows us to construct a 5-stage algorithm for finding 3 defectives with the optimal number 3log2t(1 + o(1)) of tests.A full version of this paper is accessible at [1]

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.

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.

Group testing is a well-known search problem that consists in detecting of s defective members of a set of t samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, two-stage group testing is considered. Using the hypergraph approach we design a new search algorithm, which allows improving the known results for fixed s and t→ ∞. For the case s = 2 this algorithm achieves information-theoretic lower bound 2 log2t(1+o(1)) on the number of tests in the worst case. Also, the problem of finding m out of s defectives is considered.

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.