Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности

Н. К. Верещагин; Дектярев М. В.

doi:10.4213/sm10159

Публикации

?

Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности

Математический сборник. 2025. Т. 216. № 6. С. 3–45.

Верещагин Н. К., Дектярев М. В.

Полудуплексная коммуникационная сложность с противником определена в работе [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В настоящей работе дается ответ на этот вопрос: приведен пример функции, для которой полудуплексная коммуникационная сложность с противником строго меньше классической коммуникационной сложности.

Научное направление: Компьютерные науки

Язык: русский

Полный текст

DOI

Текст на другом сайте

Ключевые слова: communication complexity коммуникационная сложность Half-duplex communication complexity полудуплексная коммуникационная сложность

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Новые методы в исследовании формальных моделей вычислений, компьютерных систем и смежных задач теоретической информатики (2025)

Exploring New Frontiers in Vertical Federated Learning: the Role of Saddle Point Reformulation

Beznosikov A., Kormakov G., Grigorievskiy A. и др., Journal of Optimization Theory and Applications 2026 Vol. 209 Article 18

Добавлено: 17 июня 2026 г.

Supervised Learning in Critical Phenomena—Statistical and Systematic Accuracy

Chertenkov V. I., Щур Л. Н., Lobachevskii Journal of Mathematics 2026 Vol. 47 No. 2 P. 720–727

Добавлено: 16 июня 2026 г.

Enhancing Emotion Recognition in Speech Based on Self-Supervised Learning: Cross-Attention Fusion of Acoustic and Semantic Features

Deeb B., Andrey V. Savchenko, Макаров И. А., IEEE Access 2026 Vol. 13 P. 56283–56295

Добавлено: 16 июня 2026 г.

Automated detection of wolf howls using audio spectrogram transformers

Makarov N., Савченко А. В., Zemtsova I. и др., Scientific Reports 2025 Vol. 15 Article 26641

Добавлено: 16 июня 2026 г.

Artificial intelligence framework for multi-pathology risk assessment from retinal fundus images: deep learning approach to 15-disease screening

Vasilev R., Савченко А. В., Blinov P. и др., Frontiers in Medicine 2026 Vol. 13

Добавлено: 16 июня 2026 г.

From Data to Signs: A Foundation Model for Multilingual Sign Language Recognition

Novopoltsev M., Tulenkov A., Murtazin R. и др., IEEE Access 2025 Vol. 13 P. 188170–188181

Добавлено: 16 июня 2026 г.

B3Emo: Quantifying Affect as a Double-Edged Sword in Strategic LLM Interactions

Stepin A., Mozikov M., Kabanov A. и др., IEEE Access 2026 Vol. 14 P. 48127–48144

Добавлено: 16 июня 2026 г.

ESQA: Event Sequences Question Answering

Abdullaeva I., Karpukhin I., Filatov A. и др., IEEE Access 2026 Vol. 14 P. 59390–59408

Добавлено: 16 июня 2026 г.

Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)

Association for Computational Linguistics, 2026.

Добавлено: 14 июня 2026 г.

Proceedings of the 6th Workshop on Computational Approaches to Discourse, Context and Document-Level Inferences (CODI 2025)

Strube M., Braud C., Hardmeier C. и др., Suzhou: Association for Computational Linguistics, 2025.

Добавлено: 11 июня 2026 г.

TreeDQN: Sample-efficient off-policy reinforcement learning for combinatorial optimization

Sorokin D., Kostin A., Савченко Л. В. и др., Knowledge-Based Systems 2026 Vol. 348 Article 116258

Добавлено: 10 июня 2026 г.

Microbial diversity and production of milk spirit using traditional Buryat fermentation and distillation technologies

Namsaraev Z., Nanzatov B., Козлова А. Д. и др., Scientific Reports 2026 Vol. 16 No. 1 Article 17769

Дистиллированные кисломолочные напитки встречаются в пищевой промышленности редко, несмотря на повсеместное распространение растительных спиртных напитков. В настоящее время производство крепких дистиллированных алкогольных напитков из кисломолочных продуктов с использованием традиционных технологий известно лишь среди монголоязычных народов и их сибирских соседей. Данное исследование представляет собой первый междисциплинарный анализ дарасуна, традиционного бурятского спиртного напитка, изготавливаемого из кисломолочного напитка ...

Добавлено: 10 июня 2026 г.

Artificial intelligence and digital twins for failure prediction in data center cooling systems: a comprehensive literature review (2018–2026)

Butorova A., Bobakov V., Sergeev A. и др., European Physical Journal: Special Topics 2026 P. 1–19

Добавлено: 10 июня 2026 г.

Innovations in Information and Decision Sciences. Proceedings of the 13th International Conference on Frontiers in Intelligent Computing: Theory and Applications (FICTA 2025), Volume 4

Springer, 2026.

Добавлено: 8 июня 2026 г.

Half-duplex communication complexity with adversary can be less than the classical communication complexity

Верещагин Н. К., Dektiarev M., / Series arXiv "math". 2024.

Добавлено: 19 августа 2024 г.

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games

Игнатьев А. А., Mihajlin I., Smal A., , in: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248.: Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. Ch. 66.

Добавлено: 9 ноября 2023 г.

Counting the Number of Perfect Matchings, and Generalized Decision Trees

Вялый М. Н., Problems of Information Transmission 2021 Vol. 57 No. 2 P. 143–160

Добавлено: 20 августа 2021 г.

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

Подольский В. В., Sherstov A., ACM Transactions on Computation Theory 2020 Vol. 12 No. 4 P. 26

Добавлено: 23 декабря 2020 г.

One-Sided Error Communication Complexity of Gap Hamming Distance

Klenin E., Козачинский А. Н., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–15.

Добавлено: 28 августа 2018 г.

Euclidean Distance Matrices and Separations in Communication Complexity Theory

Шитов Я. Н., Discrete and Computational Geometry 2019 Vol. 61 No. 3 P. 653–660

Добавлено: 15 марта 2018 г.

On Slepian–Wolf Theorem with Interaction

Козачинский А. Н., Theory of Computing Systems 2018 Vol. 62 No. 3 P. 583–599

In this paper we study interactive “one-shot” analogues of the classical Slepian–Wolf theorem. Alice receives a value of a random variable X, Bob receives a value of another random variable Y that is jointly distributed with X. Alice’s goal is to transmit X to Bob (with some error probability ε). Instead of one-way transmission we allow them to interact. They may also ...

Добавлено: 9 февраля 2017 г.

On Slepian–Wolf Theorem with Interaction

Козачинский А. Н., , in: Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, ProceedingsVol. 9691: Lecture Notes in Computer Science.: Switzerland: Springer, 2016. P. 207–222.

Добавлено: 16 сентября 2016 г.

Towards a Reverse Newman’s Theorem in Interactive Information Complexity

Brody J., Buhrman H., Koucký M. и др., Algorithmica 2016 Vol. 76 No. 3 P. 749–781

Добавлено: 2 марта 2016 г.

Making Randomness Public in Unbounded-Round Information Complexity

Козачинский А. Н., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 9139.: Springer, 2015. P. 296–309.

Добавлено: 29 февраля 2016 г.