Город: Санкт-Петербург Казань Язык: Русский English
Что: Лекция
Когда: Суббота, 25 марта 2017, 17:20–18:50
Где: ПОМИ РАН
Слайды: 2017_03_25_communicationcomplexity_2017_sprin_SF9q0Sk.pdf

Описание

Понятие детерминированного коммуникационного протокола (неформально). Тривиальные верхние оценки на коммуникационную сложность \(D(f)\) для произвольной функции \(f:X\times Y\rightarrow Z\). Логарифмические верхние оценки коммуникационной сложности функций MED и CIS(G).

Вероятностные коммуникационные протоколы. Общие и частные случайные биты. Двусторонняя и односторонняя ошибка. Коммуникация в среднем и в худшем случае. Предикаты EQ и GT. Логарифмическая верхняя оценка односторонней сложности предиката равенства для протоколов с частными случайными битами.

Видео