Source author record

Ilya Vorobyev

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT math.CO Discrete Mathematics math.PR

Catalog footprint

Research overview

11works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Correcting one error in channels with feedback

We address the problem of correcting a single error in an arbitrary discrete memoryless channel with error-free instantaneous feedback. For the case of a one-time feedback, we propose a method for constructing optimal transmission strategies. The obtained result allows us to prove that for a binary channel, two feedbacks are sufficient to transmit the same number of messages as in the case of complete feedback. We also apply the developed techniques to a binary asymmetric channel to construct transmission strategies for small lengths.

preprint2022arXiv

Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate

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 2020 by Egorova et al. We continue this work and provide an improved lower bound on the rate of these codes.

preprint2022arXiv

Fast Decoding of Union-free Codes

Union-free codes and disjunctive codes are two combinatorial structures, which are used in nonadaptive group testing to find a set of $d$ defective elements among $n$ samples by carrying out the minimal number of tests $t$ . It is known that union-free codes have a larger rate, whereas disjunctive codes provide a more efficient decoding algorithm. In this paper we introduce a new family of codes for nonadaptive group testing with fast decoding. The rate of these codes is larger than the rate of disjunctive codes, while the decoding algorithm has the same complexity. In addition, we derive a lower bound on the rate of new codes for the case of $d=2$ defectives, which is significantly better than the bound for disjunctive codes and almost as good as the bound for union-free codes.

preprint2022arXiv

Feedback Insertion-Deletion Codes

In this paper, a new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Suppose 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 the 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 $τn$ , $0<τ<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 finished 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.

preprint2022arXiv

Non-adaptive and two-stage coding over the Z-channel

In this paper, we developed new coding strategies for the Z-channel. In particular, we look at the case with two-stage encoding. In this case, the encoder uses noiseless feedback once and adjusts the further encoding strategy based on the previous partial output of the channel. Nevertheless, the developed codes improve the known results with full feedback for small length and 1 error. A tool for the two-stage strategy is the development of a new optimality condition for non-adaptive codes.

preprint2020arXiv

Duplication with transposition distance to the root for $q$ -ary strings

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) \to 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/\log n$ . 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/\log n$ to $\log n$ 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.

preprint2020arXiv

Lifted Reed-Solomon Codes with Application to Batch 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\ge 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.

preprint2020arXiv

Optimal Multistage Group Testing Algorithm for 3 Defectives

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 $3\log_2t(1+o(1))$ of tests.

preprint2016arXiv

Bounds on the rate of superimposed codes

A binary code is called a superimposed cover-free $(s,\ell)$ -code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others. A binary code is called a superimposed list-decoding $s_L$ -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=\ell=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 given codes. The most interesting result is a lower bound on the rate of superimposed cover-free $(s,\ell)$ -code based on the ensemble of constant-weight binary codes. If parameter $\ell\ge1$ is fixed and $s\to\infty$ , 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 $\ell=1$ and $s\ge2$ , the given Statement means that our recurrent upper bound on the rate of superimposed $s$ -codes obtained in 1982 is attained to within a constant factor $a$ , $0,271\le a\le1$

preprint2015arXiv

Almost Cover-Free Codes and Designs

An $s$ -subset of codewords of a binary code $X$ is said to be an {\em $(s,\ell)$ -bad} in $X$ if the code $X$ contains a subset of other $\ell$ codewords such that the conjunction of the $\ell$ codewords is covered by the disjunctive sum of the $s$ codewords. Otherwise, the $s$ -subset of codewords of $X$ is said to be an {\em $(s,\ell)$ -good} in~ $X$ .mA binary code $X$ is said to be a cover-free $(s,\ell)$ -code if the code $X$ does not contain $(s,\ell)$ -bad subsets. In this paper, we introduce a natural {\em probabilistic} generalization of cover-free $(s,\ell)$ -codes, namely: a binary code is said to be an almost cover-free $(s,\ell)$ -code if {\em almost all} $s$ -subsets of its codewords are $(s,\ell)$ -good. We discuss the concept of almost cover-free $(s,\ell)$ -codes arising in combinatorial group testing problems connected with the nonadaptive search of defective supersets (complexes). 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.

preprint2015arXiv

Symmetric Disjunctive List-Decoding Codes

A binary code is said to be a disjunctive list-decoding $s_L$ -code (LD $s_L$ -code), $s \ge 2$ , $L \ge 1$ , if the code is identified by the incidence matrix of a family of finite sets in which the union (or disjunctive sum) of any $s$ sets can cover not more than $L-1$ other sets of the family. In this paper, we consider a similar class of binary codes which are based on a {\em symmetric disjunctive sum} (SDS) of binary symbols. By definition, the symmetric disjunctive sum (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~ $*$ . List decoding codes for symmetric disjunctive sum are said to be {\em symmetric disjunctive list-decoding $s_L$ -codes} (SLD $s_L$ -codes). In the given paper, we remind some applications of SLD $s_L$ -codes which motivate the concept of symmetric disjunctive sum. We refine the known relations between parameters of LD $s_L$ -codes and SLD $s_L$ -codes. For the ensemble of binary constant-weight codes we develop a random coding method to obtain lower bounds on the rate of these codes. Our lower bounds improve the known random coding bounds obtained up to now using the ensemble with independent symbols of codewords.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ilya Vorobyev

Research overview

Is this your work?

11 publications

Correcting one error in channels with feedback

Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate

Fast Decoding of Union-free Codes

Feedback Insertion-Deletion Codes

Non-adaptive and two-stage coding over the Z-channel

Duplication with transposition distance to the root for $q$ -ary strings

Lifted Reed-Solomon Codes with Application to Batch Codes

Optimal Multistage Group Testing Algorithm for 3 Defectives

Bounds on the rate of superimposed codes

Almost Cover-Free Codes and Designs

Symmetric Disjunctive List-Decoding Codes

See the researcher in context

Building this map preview

Ilya Vorobyev

Research overview

Is this your work?

11 publications

Correcting one error in channels with feedback

Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate

Fast Decoding of Union-free Codes

Feedback Insertion-Deletion Codes

Non-adaptive and two-stage coding over the Z-channel

Duplication with transposition distance to the root for qqq-ary strings

Lifted Reed-Solomon Codes with Application to Batch Codes

Optimal Multistage Group Testing Algorithm for 3 Defectives

Bounds on the rate of superimposed codes

Almost Cover-Free Codes and Designs

Symmetric Disjunctive List-Decoding Codes

See the researcher in context

Building this map preview

Duplication with transposition distance to the root for $q$ -ary strings