Что: Лекция
Когда: Суббота, 25 марта 2017, 19:10–20:40
Где:
Слайды: communicationcomplexity_lecture_250317.pdf

Описание

Верхняя оценка \(O(1)\) для односторонней вероятностной сложности предиката GT для протоколов с общими случайными битами. Оценка \(O(\log^2 n)\) вероятностной двусторонней сложности предиката GT. Оценка \(O(\log n)\) для односторонней сложности предиката GT для протоколов с общими случайными битами.

Амплификация.

Теорема Ньюмана об уменьшении количества случайных битов и замене общих битов на приватные.

Видео

Приложенные файлы