Problemy Peredachi Informatsii
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

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

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
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
\Bibitem{DyaVorPol14} \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 \mathnet{http://mi.mathnet.ru/ppi2131} \transl \jour Problems Inform. Transmission \yr 2014 \vol 50 \issue 1 \pages 27--56 \crossref{https://doi.org/10.1134/S0032946014010037} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000334517000003} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84899519079} 

• http://mi.mathnet.ru/eng/ppi2131
• http://mi.mathnet.ru/eng/ppi/v50/i1/p31

 SHARE:

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

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
2. N. A. Polyansky, “Almost cover-free codes”, Problems Inform. Transmission, 52:2 (2016), 142–155
3. V. Yu. Shchukin, “List decoding for a multiple access hyperchannel”, Problems Inform. Transmission, 52:4 (2016), 329–343
4. I. V. Vorob'ev, “Bounds on the rate of separating codes”, Problems Inform. Transmission, 53:1 (2017), 30–41
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
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
7. M. Aldridge, L. Baldassini, K. Gunderson, “Almost Separable Matrices”, J. Comb. Optim., 33:1 (2017), 215–236
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
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
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
11. N. H. Bshouty, “Exact learning from an honest teacher that answers membership queries”, Theor. Comput. Sci., 733:SI (2018), 4–43
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
13. A. D'yachkov, N. Polyanskii, V. Shchukin, I. Vorobyev, “Separable codes for the symmetric multiple-access channel”, IEEE Trans. Inf. Theory, 65:6 (2019), 3738–3750
14. I. Vorobyev, “A new algorithm for two-stage group testing”, 2019 IEEE International Symposium on Information Theory (Isit), IEEE International Symposium on Information Theory, IEEE, 2019, 101–105
•  Number of views: This page: 407 Full text: 65 References: 35 First page: 24