Отправить статью по E-mail Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности
- Авторы: Верещагин Н.К.1,2, Дектярёв М.В.1
-
Учреждения:
- Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова
- Факультет компьютерных наук,Национальный исследовательский университет «Высшая школа экономики», г. Москва
- Выпуск: Том 216, № 6 (2025)
- Страницы: 3-45
- Раздел: Статьи
- URL: https://journal-vniispk.ru/0368-8666/article/view/306711
- DOI: https://doi.org/10.4213/sm10159
- ID: 306711
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Полудуплексная коммуникационная сложность с противником определена в работе [2]. Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [11]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В настоящей работе дается ответ на этот вопрос: приведен пример функции, для которой полудуплексная коммуникационная сложность с противником строго меньше классической коммуникационной сложности. Библиография: 11 названий.
Об авторах
Николай Константинович Верещагин
Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова; Факультет компьютерных наук,Национальный исследовательский университет «Высшая школа экономики», г. Москва
Email: nikolay.vereshchagin@math.msu.ru; nikolay.vereshchagin@gmail.com
Михаил Владимирович Дектярёв
Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова
Email: mikhail.dektiarev@gmail.com
Список литературы
- Y. Dementiev, A. Ignatiev, V. Sidelnik, A. Smal, M. Ushakov, “New bounds on the half-duplex communication complexity”, SOFSEM 2021: theory and practice of computer science, Lecture Notes in Comput. Sci., 12607, Springer, Cham, 2021, 233–248
- K. Hoover, R. Impagliazzo, I. Mihajlin, A. V. Smal, “Half-duplex communication complexity”, 29th international symposium on algorithms and computation (ISAAC 2018), LIPIcs. Leibniz Int. Proc. Inform., 123, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2018, 10, 12 pp.
- M. Karchmer, A. Wigderson, “Monotone circuits for connectivity require super-logarithmic depth”, STOC {'}88: Proceedings of the 20th annual ACM symposium on theory of computing (Chicago, IL, 1988), ACM, New York, 1988, 539–550
- A. Ignatiev, I. Mihajlin, A. Smal, “Super-cubic lower bound for generalized Karchmer–Wigderson games”, 33rd international symposium on algorithms and computation (ISAAC 2022), LIPIcs. Leibniz Int. Proc. Inform., 248, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2022, 66, 18 pp.
- Hao Wu, An improved composition theorem of a universal relation and most functions via effective restriction
- O. Meir, “Toward better depth lower bounds: two results on the multiplexor relation”, Comput. Complex., 29:1 (2020), 4, 25 pp.
- O. Meir, Toward better depth lower bounds: a KRW-like theorem for strong composition
- A. Nolin, Communication complexity: large output functions, partition bounds, and quantum nonlocality, Ph.D. thesis, Univ. Paris, 2020, 140 pp.
- E. Kushilevitz, N. Nisan, Communication complexity, Reprint of 1997 original, Cambridge Univ. Press, Cambridge, 2006, xiv+189 pp.
- А. В. Смаль, Доказательство нижних оценок на размер формул для булевых функций методами коммуникационной сложности, Дисс. … канд. физ.-матем. наук, ПОМИ РАН, СПб., 2022, 114 с.
- A. C.-C. Yao, “Some complexity questions related to distributive computing (Preliminary report)”, STOC{'}79: Proceedings of the eleventh annual ACM symposium on theory of computing (Atlanta, GA, 1979), ACM, New York, 1979, 209–213
Дополнительные файлы
