Laboratory of Mathematical Logic at PDMI

Понедельник, 21 мая, 402. Начало в 17:00.

Докладчик: А. Смаль.

Тема: Полудуплексная коммуникационная сложность.

Abstract

В классической модели коммуникационной сложности на каждом раунде коммуникации один из игроков говорит (посылает бит), а другой его слушает. Мы предлагаем рассмотреть обобщение этой модели, в которой Алиса и Боб могут также говорить одновременно (и тогда они не слышат друг друга) или слушать одновременно. Естественный аналог такой модели — это общение по полудуплексному каналу, например при помощи рации. Мы рассматриваем три варианта такой обобщённой модели и доказываем верхние и нижние оценки на коммуникационную сложность булевых функций в них.

По совместной работе с Иваном Михайлиным, Кеном Хувером и Расселом Импальяццо.