NEW LOWER BOUNDS ON THE RATES OF LOCALLY THIN FAMILIES AND WEAK DISJUNCTIVE CODES

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅或者付费存取

详细

Locally thin families of sets and weak disjunctive codes are studied. The main result is obtaining new lower bounds on the rates of the studied constructions using probabilistic methods. Additionally, new lower bounds on the rates of multimedia codes that determine the coalition under averaging and noise attacks are presented, which follow from the obtained estimates for the rates of weak disjunctive codes.

作者简介

D. Goshkoder

Skolkovo Institute of Science and Technology (Skoltech)

Email: danilgoshkoder@mail.ru
Moscow

参考

  1. Kautz W., Singleton R. Nonrandom Binary Superimposed Codes // IEEE Trans. Inform. Theory. 1964. V. 10. № 4. P. 363–377. https://doi.org/10.1109/TIT.1964.1053689
  2. Friedman A.D., Graham R.L., Ullman J.D. Universal Single Transition Time Asynchronous State Assignments // IEEE Trans. Comput. 1969. V. 18. № 6. P. 541–547. https://doi.org/10.1109/T-C.1969.222707
  3. Сагалович Ю.Л. Метод повышения надежности конечного автомата // Пробл. передачи информ. 1965. Т. 1. № 2. С. 27–35. http://mi.mathnet.ru/ppi734
  4. Erd˝os P., Rado R. Intersection Theorems for Systems of Sets // J. London Math. Soc. 1960. V. 35. № 2. P. 85–90. https://doi.org/10.1112/jlms/s1-35.1.85
  5. Alon N., K¨orner J., Monti A. String Quartets in Binary // Combin. Probab. Comput. 2000. V. 9. № 5. P. 381–390. https://doi.org/10.1017/S0963548300004375
  6. Егорова Е.Е., Фернандес М., Кабатянский Г.А., Мяо И. Существование и конструкции мультимедийных кодов, способных находить полную коалицию при атаке усреднения и шуме // Пробл. передачи информ. 2020. Т. 56. № 4. С. 97–108. https://doi.org/10.31857/S0555292320040087
  7. Fachini E., K¨orner J., Monti A. A Better Bound for Locally Thin Set Families // J. Combin. Theory Ser. A. 2001. V. 95. № 2. P. 209–218. https://doi.org/10.1006/jcta.2000.3162
  8. Alon N., Fachini E., K¨orner J. Locally Thin Set Families // Combin. Probab. Comput. 2000. V. 9. № 6. P. 481–488. https://doi.org/10.1017/S0963548300004521
  9. F¨uredi Z. 2-Cancellative Hypergraphs and Codes // Combin. Probab. Comput. 2012. V. 21. № 1–2. P. 159–177. https://doi.org/10.1017/S0963548311000563
  10. Fachini E., K¨orner J., Monti A. Self-Similarity Bounds for Locally Thin Set Families // Combin. Probab. Comput. 2001. V. 10. № 4. P. 309–315. https://doi.org/10.1017/S0963548301004667
  11. Qian B., Wang X., Ge G. Improved Lower Bounds for Strongly Separable Matrices and Related Combinatorial Structures // IEEE Trans. Inform. Theory. 2023. V. 69. № 5. P. 2801–2807. https://doi.org/10.1109/TIT.2022.3233395
  12. Tsunoda Y., Fujiwara Y. Weak Superimposed Codes of Improved Asymptotic Rate and Their Randomized Construction // Proc. 2022 IEEE Int. Symp. on Information Theory (ISIT’2022). Espoo, Finland. June 26, 2022 – July 1, 2022. P. 784–789. https://doi.org/10.1109/ISIT50566.2022.9834680
  13. Vorobyev I. Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate // Des. Codes Cryptogr. 2023. V. 4. № 4. P. 1183–1191. https://doi.org/10.1007/s10623-022-01144-x
  14. De Bonis A. Generalized Selectors and Locally Thin Families with Applications to Conflict Resolution in Multiple Access Channels Supporting Simultaneous Successful Transmissions // Proc. 20th Int. Conf. on Principles of Distributed Systems (OPODIS 2016).
  15. Leibniz Int. Proc. in Informatics (LIPIcs). V. 70. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik, 2017. P. 22:1–22:16. https://doi.org/10.4230/LIPIcs.OPODIS.2016.22
  16. De Bonis A. New Selectors and Locally Thin Families with Applications to Multi-Access Channels Supporting Simultaneous Transmissions // Theoret. Comput. Sci. 2019. V. 796. P. 34–50. https://doi.org/10.1016/j.tcs.2019.08.020
  17. D’yachkov A.G., Rykov V.V., Rashad A.M. Superimposed Distance Codes // Probl. Control Inform. Theory. 1989. V. 18. № 4. P. 237–250.
  18. Goshkoder D.Yu. Probabilistic Methods for Deriving New Lower Bounds on the Rates of Locally Thin Families and Weak Disjunctive Codes // Probl. Inf. Transm. 2025. V. 61. № 2 (to appear).
  19. Deuber W.A., Erd˝os P., Gunderson D.S., Kostochka A.V., Meyer A.G. Intersection Statements for Systems of Sets // J. Combin. Theory Ser. A. 1997. V. 79. № 1. P. 118–132. https://doi.org/10.1006/jcta.1997.2778

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Russian Academy of Sciences, 2025