Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English
Что: Лекция
Когда: Воскресенье, 26 марта 2017, 11:15–12:45
Где: ПОМИ РАН
Слайды: 2017_03_26_communicationcomplexity_2017_sprin_fsW4AKI.pdf

Описание

Формальное определение детерминированных и вероятностных коммуникационных протоколов. Дерево протокола. Прямоугольники, соответствующие листьям дерева протокола.

Матрица функции, ее разбиение на одноцветные прямоугльники, неравенство \(\log C^R(f) < D(f)\).

Методы оценки \(C^R(f)\): (1) трудные множества и размеры одноцветных прямоугольников и (2) ранг матрицы.

Нижние оценки детерминированной сложности предикатов EQ, GT, DISJ, IP этими методами.

Видео