Вы здесь

Коммуникационная сложность (2017). Лекция 1

Лекция
Предмет:
Дата записи:
25.03.17
Дата публикации:
20.04.17
Код для блога:

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

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

Страница лекции на CSClub