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

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

Date:

Monday, May 21, 2018 - 12:00

Abstract:

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

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