Коммуникационная сложность (2017). Лекция 2
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
25.03.17
Дата публикации:
20.04.17
Код для блога:
Верхняя оценка O(1) для односторонней вероятностной сложности предиката GT для протоколов с общими случайными битами. Оценка O(log2n) вероятностной двусторонней сложности предиката GT. Оценка O(logn) для односторонней сложности предиката GT для протоколов с общими случайными битами.
Амплификация.
Теорема Ньюмана об уменьшении количества случайных битов и замене общих битов на приватные.
Страница лекции на CSClub
Другие лекции курса
8