"Записки научных семинаров ПОМИ"
Том 552, стр. 100-133
Новые результаты о полудуплексной коммуникационной сло╦ности
Ю. И. Дементьев, А. А. Игнатьев, В. А. Сидельник,
А. В. Смаль, М. С. Ушаков
Saint Petersburg State University,
St. Petersburg Department of Steklov
Mathematical Institute of Russian Academy of Sciences
yuru.dementiev@gmail.com
artur.ignatev@csspace.io
slava.sidelnik@gmail.com
avsmal@gmail.com
mikushakov@gmail.com
- Аннотация:
В данной работе продол╦ается линия исследований, начатая в работе
K. Hoover, R. Impagliazzo, I. Mihajlin и A. Smal (2018), где была введена
модель полудуплексной коммуникационной сло╦ности. В отличие от классической
модели коммуникационной сло╦ности, предло╦енной в работе A. Yao (1979),
полудуплексная модель ограничивает участников так, что в ка╦дый момент
времени ка╦дый из них мо╦ет либо передавать, либо принимать,
но не одновременно, как при общении по рации. Эта модель мотивирована
вопросами, возникающими при изучении гипотезы KRW. Решая открытые задачи,
поставленные в работе Hoover и др., мы доказываем ни╦ние оценки для
функции дизъюнктности во всех рассматриваемых вариантах полудуплексной
модели, а так╦е доказываем верхнюю оценку в полудуплексной модели с нулём.
Кроме того, мы устанавливаем ни╦ние и верхние оценки полудуплексной
сло╦ности игр Карчмера--Вигдерсона для функций подсчёта и для рекурсивной
функции большинства, адаптируя и развивая методы классической
коммуникационной сло╦ности. Помимо этого, мы вводим понятие
недетерминированной полудуплексной коммуникационной сло╦ности и доказываем
оценки, связывающие её с недетерминированной коммуникационной сло╦ностью
в классической модели. Предварительная версия данной работы была
опубликована в трудах конференции SOFSEM 2021, а часть результатов
впоследствии была уточнена в электронном препринте ECCC (2020).
Настоящая ╦урнальная версия существенно расширяет конференционную
версию и включает новый раздел об играх Карчмера--Вигдерсона для
пороговой функции и функции большинства.
Библ. --- 19 назв.
- Ключевые слова: коммуникационная сло╦ность,
полудуплексная коммуникация, игры Карчмера--Вигдерсона
[communication complexity, half-duplex communication,
Karchmer-Wigderson games]
Полный текст(.pdf)