General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Probl. Peredachi Inf.:

Personal entry:
Save password
Forgotten password?

Probl. Peredachi Inf., 2014, Volume 50, Issue 1, Pages 31–63 (Mi ppi2131)  

This article is cited in 12 scientific papers (total in 12 papers)

Coding Theory

Bounds on the rate of disjunctive codes

A. G. D'yachkov, I. V. Vorob'ev, N. A. Polyansky, V. Yu. Shchukin

Probability Theory Chair, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia

Abstract: A binary code is said to be a disjunctive $(s,\ell)$ cover-free code if it is an incidence matrix of a family of sets where the intersection of any $\ell$ sets is not covered by the union of any other $s$ sets of this family. A binary code is said to be a list-decoding disjunctive of strength $s$ with list size $L$ if it is an incidence matrix of a family of sets where the union of any $s$ sets can cover no more that $L-1$ other sets of this family. For $L=\ell=1$, both definitions coincide, and the corresponding binary code is called a disjunctive $s$-code. This paper is aimed at improving previously known and obtaining new bounds on the rate of these codes. The most interesting of the new results is a lower bound on the rate of disjunctive $(s,\ell)$ cover-free codes obtained by random coding over the ensemble of binary constant-weight codes; its ratio to the best known upper bound converges as $s\to\infty$, with an arbitrary fixed $\ell\ge1$, to the limit $2e^{-2}=0{,}271…$ In the classical case of $\ell=1$, this means that the upper bound on the rate of disjunctive $s$-codes constructed in 1982 by D'yachkov and Rykov is asymptotically attained up to a constant factor $a$, $2e^{-2}\le a\le1$.

Full text: PDF file (393 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2014, 50:1, 27–56

Bibliographic databases:

UDC: 621.391.15
Received: 15.04.2013
Revised: 09.01.2014

Citation: A. G. D'yachkov, I. V. Vorob'ev, N. A. Polyansky, V. Yu. Shchukin, “Bounds on the rate of disjunctive codes”, Probl. Peredachi Inf., 50:1 (2014), 31–63; Problems Inform. Transmission, 50:1 (2014), 27–56

Citation in format AMSBIB
\by A.~G.~D'yachkov, I.~V.~Vorob'ev, N.~A.~Polyansky, V.~Yu.~Shchukin
\paper Bounds on the rate of disjunctive codes
\jour Probl. Peredachi Inf.
\yr 2014
\vol 50
\issue 1
\pages 31--63
\jour Problems Inform. Transmission
\yr 2014
\vol 50
\issue 1
\pages 27--56

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. G. D'yachkov, I. V. Vorob'ev, N. A. Polyansky, V. Yu. Shchukin, “Almost disjunctive list-decoding codes”, Problems Inform. Transmission, 51:2 (2015), 110–131  mathnet  crossref  isi  elib
    2. N. A. Polyansky, “Almost cover-free codes”, Problems Inform. Transmission, 52:2 (2016), 142–155  mathnet  crossref  mathscinet  isi  elib  elib
    3. V. Yu. Shchukin, “List decoding for a multiple access hyperchannel”, Problems Inform. Transmission, 52:4 (2016), 329–343  mathnet  crossref  isi  elib
    4. I. V. Vorob'ev, “Bounds on the rate of separating codes”, Problems Inform. Transmission, 53:1 (2017), 30–41  mathnet  crossref  isi  elib
    5. N. H. Bshouty, A. Gabizon, “Almost Optimal Cover-Free Families”, Algorithms and Complexity, CIAC 2017, Lecture Notes in Computer Science, 10236, eds. D. Fotakis, A. Pagourtzis, V. Paschos, Springer International Publishing Ag, 2017, 140–151  crossref  mathscinet  zmath  isi  scopus
    6. A. De Bonis, U. Vaccaro, “A New Kind of Selectors and Their Applications to Conflict Resolution in Wireless Multichannels Networks”, Algorithms For Sensor Systems, ALGOSENSORS 2016, Lecture Notes in Computer Science, 10050, eds. M. Chrobak, A. Anta, L. Gasieniec, R. Klasing, Springer International Publishing Ag, 2017, 45–61  crossref  isi  scopus
    7. M. Aldridge, L. Baldassini, K. Gunderson, “Almost Separable Matrices”, J. Comb. Optim., 33:1 (2017), 215–236  crossref  mathscinet  zmath  isi  scopus
    8. A. G. D'yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin, “Cover-Free Codes and Separating System Codes”, Designs Codes Cryptogr., 82:1-2, SI (2017), 197–209  crossref  mathscinet  zmath  isi  scopus
    9. A. G. D'yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin, “Symmetric Disjunctive List-Decoding Codes”, Designs Codes Cryptogr., 82:1-2, SI (2017), 211–229  crossref  mathscinet  zmath  isi  scopus
    10. A. G. D'yachkov, I. V. Vorobyev, N. A. Polyanskii, V. Yu. Shchukin, “Almost Cover-Free Codes and Designs”, Designs Codes Cryptogr., 82:1-2, SI (2017), 231–247  crossref  mathscinet  zmath  isi  scopus
    11. N. H. Bshouty, “Exact learning from an honest teacher that answers membership queries”, Theor. Comput. Sci., 733:SI (2018), 4–43  crossref  mathscinet  zmath  isi  scopus
    12. A. D'yachkov, N. Polyanskii, V. Shchukin, I. Vorobyev, “Separable codes for the symmetric multiple-access channel”, 2018 IEEE International Symposium on Information Theory (ISIT), IEEE, 2018, 291–295  crossref  isi
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:379
    Full text:53
    First page:24

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020