Source author record

Nikita Polyanskii

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 Discrete Mathematics math.AG

Catalog footprint

Research overview

10works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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

Quadratic-Curve-Lifted Reed-Solomon Codes

Lifted codes are a class of evaluation codes attracting more attention due to good locality and intermediate availability. In this work we introduce and study quadratic-curve-lifted Reed-Solomon (QC-LRS) codes, where the codeword symbols whose coordinates are on a quadratic curve form a codeword of a Reed-Solomon code. We first develop a necessary and sufficient condition on the monomials which form a basis the code. Based on the condition, we give upper and lower bounds on the dimension and show that the asymptotic rate of a QC-LRS code over $\mathbb{F}_q$ with local redundancy $r$ is $1-Θ(q/r)^{-0.2284}$ . Moreover, we provide analytical results on the minimum distance of this class of codes and compare QC-LRS codes with lifted Reed-Solomon codes by simulations in terms of the local recovery capability against erasures. For short lengths, QC-LRS codes have better performance in local recovery for erasures than LRS codes of the same dimension.

preprint2022arXiv

Two-stage coding over the Z-channel

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 $τn$ , $0<τ<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 $τ=\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+ε$ of asymmetric errors, an error-correcting code contains at most $O(ε^{-3/2})$ codewords.

preprint2021arXiv

Coding with Noiseless Feedback over the Z-channel

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 $τ\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 $τ<1$ and $n\to\infty$ . Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting 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 Codes Correcting a Burst of Deletions of Variable Length

In this paper, we present an efficiently encodable and decodable code construction that is capable of correction a burst of deletions of length at most $k$ . The redundancy of this code is $\log n + k(k+1)/2\log \log n+c_k$ for some constant $c_k$ that 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 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.

preprint2020arXiv

Weight Distributions for Successive Cancellation Decoding of Polar Codes

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 the successive cancellation list decoding.

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.

Nikita Polyanskii

Research overview

Is this your work?

10 publications

Feedback Insertion-Deletion Codes

Quadratic-Curve-Lifted Reed-Solomon Codes

Two-stage coding over the Z-channel

Coding with Noiseless Feedback 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 Codes Correcting a Burst of Deletions of Variable Length

Weight Distributions for Successive Cancellation Decoding of Polar Codes

Almost Cover-Free Codes and Designs

Symmetric Disjunctive List-Decoding Codes

See the researcher in context

Building this map preview

Nikita Polyanskii

Research overview

Is this your work?

10 publications

Feedback Insertion-Deletion Codes

Quadratic-Curve-Lifted Reed-Solomon Codes

Two-stage coding over the Z-channel

Coding with Noiseless Feedback 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 Codes Correcting a Burst of Deletions of Variable Length

Weight Distributions for Successive Cancellation Decoding of Polar 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