Коммуникационная сложность (2017). Лекция 3
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
26.03.17
Дата публикации:
20.04.17
Код для блога:
Формальное определение детерминированных и вероятностных коммуникационных протоколов. Дерево протокола. Прямоугольники, соответствующие листьям дерева протокола.
Матрица функции, ее разбиение на одноцветные прямоугльники, неравенство logCR(f)<D(f).
Методы оценки CR(f): (1) трудные множества и размеры одноцветных прямоугольников и (2) ранг матрицы.
Нижние оценки детерминированной сложности предикатов EQ, GT, DISJ, IP этими методами.
Страница лекции на CSClub
Другие лекции курса
8