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