IDIlya Dumer

Ilya Dumer

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Ilya Dumer has a total of 19 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Covering spheres with spheres

    by Ilya Dumer

    Given a sphere of any radius $r$ in an $n$-dimensional Euclidean space, we study the coverings of this sphere with solid spheres of radius one. Our goal is to design a covering of the lowest covering density, which defines the average number of solid spheres covering a point in a bigger sphere. For a growing dimension $n,$ we design a covering that has covering density of order $(n\ln n)/2$ for the full Euclidean space or for a sphere of any radius $r>1.$ This new upper bound reduces two times the asymptotic order of $n\ln n$ established in the classical Rogers bound.

  • Open Access

    Distance Verification for Classical and Quantum LDPC Codes

    by Ilya Dumer, Alexey A. Kovalev, Leonid P. Pryadko

    The techniques of distance verification known for general linear codes are first applied to the quantum stabilizer codes. Then, these techniques are considered for classical and quantum (stabilizer) low-density-parity-check (LDPC) codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both the classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of the quantum stabilizer LDPC codes.


  • Open Access

    On decoding algorithms for polar codes

    by Ilya Dumer

    We survey the known list decoding algorithms for polar codes and compare their complexity. Index terms: Polar codes; Reed-Muller codes; successive cancellation decoding.

  • Open Access

    Recursive Decoding and Its Performance for Low-Rate Reed-Muller Codes

    by Ilya Dumer

    Recursive decoding techniques are considered for Reed-Muller (RM) codes of growing length $n$ and fixed order $r.$ An algorithm is designed that has complexity of order $n\log n$ and corrects most error patterns of weight up to $n(1/2-\varepsilon)$ given that $\varepsilon$ exceeds $n^{-1/2^{r}}.$ This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity.

  • Open Access

    Soft decision decoding of Reed-Muller codes: recursive lists

    by Ilya Dumer, Kirill Shabunov

    Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes.

  • Open Access

    Recursive List Decoding for Reed-Muller Codes

    by Ilya Dumer, Kirill Shabunov

    We consider recursive decoding for Reed-Muller (RM) codes and their subcodes. Two new recursive techniques are described. We analyze asymptotic properties of these algorithms and show that they substantially outperform other decoding algorithms with nonexponential complexity known for RM codes. Decoding performance is further enhanced by using intermediate code lists and permutation procedures. For moderate lengths up to 512, near-optimum decoding with feasible complexity is obtained.

  • Open Access

    Recursive decoding of Reed-Muller codes

    by Ilya Dumer

    New soft- and hard decision decoding algorithms are presented for general Reed-Muller codes $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ of length $2^{m}$ and distance $2^{m-r}$. We use Plotkin $(u,u+v)$ construction and decompose code $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ onto subblocks $u\in\left\{\genfrac{}{}{0pt}{}{m-1}{r}\right\} $ and $v\in\left\{\genfrac{}{}{0pt}{}{m-1}{r-1}\right\} .$ In decoding, we first try to find a subblock $v$ from the better protected code and then proceed with the block $u$. The likelihoods of the received symbols are recalculated in a way similar to belief propagation. Thus, decoding is relegated to the two constituent codes. We repeat this recursion and execute decoding only at the end nodes $\left\{\genfrac{}{}{0pt}{}{j}{1}\right\} $ and $\left\{\genfrac{}{}{0pt}{}{j}{j-1}\right\} $. The overall complexity has low order of $n\log n.$ It is shown that this decoding substantially outperforms other algorithms of polynomial complexity known for RM codes. In particular, for medium and high code rates, the algorithm corrects most error patterns of weight $d\ln d/2.$

  • Spherically Punctured Reed-Muller Codes

    by Ilya Dumer, Olga Kapralova

    Consider a binary Reed-Muller code RM(r;m) defined on the m-dimensional hypercube Fm2. In this paper, we study punctured Reed-Muller codes Pr(m; b) whose positions are restricted to the m-tuples of a given Hamming weight b: In combinatorial terms, this study concerns m-variate Boolean polynomials of any degree r; which are evaluated on a Hamming sphere of some radius b in Fm2. Codes Pr(m; b) inherit some recursive properties of RM codes. In particular, they can be built from the shorter codes, by decomposing a spherical b-layer into sub-layers of smaller dimensions. However, these sub-layers have different sizes and do not form the classical Plotkin construction. We analyze recursive properties of the spherically punctured codes Pr(m; b) and find their distances for the arbitrary values of parameters r; m; and b: Finally, we describe recursive (successive cancellation) decoding of these codes.


  • Open Access

    Polar codes with a stepped boundary

    by Ilya Dumer

    We consider explicit polar constructions of blocklength $n\rightarrow\infty$ for the two extreme cases of code rates $R\rightarrow1$ and $R\rightarrow0.$ For code rates $R\rightarrow1,$ we design codes with complexity order of $n\log n$ in code construction, encoding, and decoding. These codes achieve the vanishing output bit error rates on the binary symmetric channels with any transition error probability $p\rightarrow 0$ and perform this task with a substantially smaller redundancy $(1-R)n$ than do other known high-rate codes, such as BCH codes or Reed-Muller (RM). We then extend our design to the low-rate codes that achieve the vanishing output error rates with the same complexity order of $n\log n$ and an asymptotically optimal code rate $R\rightarrow0$ for the case of $p\rightarrow1/2.$

  • Open Access

    Distance verification for classical and quantum LDPC codes

    by Ilya Dumer, Alexey A. Kovalev, Leonid P. Pryadko

    The techniques of distance verification known for general linear codes are re-applied to quantum stabilizer codes. Then distance verification is addressed for classical and quantum LDPC codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of quantum LDPC codes.