Математический сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Математический сборник, 2025, том 216, номер 6, страницы 3–45
DOI: https://doi.org/10.4213/sm10159 (Mi sm10159) 		 
Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности

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

a Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова
b Факультет компьютерных наук,Национальный исследовательский университет «Высшая школа экономики», г. Москва
PDF полного текста (929 kB) Первая страница PDF английской версии (773 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/sm10159
Аннотация: Полудуплексная коммуникационная сложность с противником определена в работе [2]. Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [11]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В настоящей работе дается ответ на этот вопрос: приведен пример функции, для которой полудуплексная коммуникационная сложность с противником строго меньше классической коммуникационной сложности.
Библиография: 11 названий.
Ключевые слова: коммуникационная сложность, трудные множества, полудуплексная коммуникационная сложность.
Финансовая поддержка Номер гранта
Программа фундаментальных исследований НИУ ВШЭ
Исследование выполнено в рамках Программы фундаментальных исследований НИУ ВШЭ.
Поступила в редакцию: 13.07.2024 и 17.12.2024
Дата публикации: 04.06.2025
Англоязычная версия:
Sbornik: Mathematics, 2025, Volume 216, Issue 6, Pages 742–779
DOI: https://doi.org/10.4213/sm10159e
Реферативные базы данных:
Тип публикации: Статья
MSC: 68Q11, 68R10
Образец цитирования: Н. К. Верещагин, М. В. Дектярев, “Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности”, Матем. сб., 216:6 (2025), 3–45; N. K. Vereshchagin, M. V. Dektiarev, “Half-duplex communication complexity with adversary can be less than the classical communication complexity”, Sb. Math., 216:6 (2025), 742–779
Цитирование в формате AMSBIB
\RBibitem{VerDek25}
\by Н.~К.~Верещагин, М.~В.~Дектярев
\paper Полудуплексная коммуникационная сложность с~противником может быть меньше классической коммуникационной сложности
\jour Матем. сб.
\yr 2025
\vol 216
\issue 6
\pages 3--45
\mathnet{http://mi.mathnet.ru/sm10159}
\crossref{https://doi.org/10.4213/sm10159}
\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=4946965}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2025SbMat.216..742V}
\transl
\by N.~K.~Vereshchagin, M.~V.~Dektiarev
\paper Half-duplex communication complexity with adversary can be less than the classical communication complexity
\jour Sb. Math.
\yr 2025
\vol 216
\issue 6
\pages 742--779
\crossref{https://doi.org/10.4213/sm10159e}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001554261800001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-105014637261}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sm10159
  • https://doi.org/10.4213/sm10159
  • https://www.mathnet.ru/rus/sm/v216/i6/p3
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Математический сборник Sbornik: Mathematics
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025