Вы здесь

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

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

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

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

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

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

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