Город: Санкт-Петербург Казань Язык: Русский English
Что: Лекция
Когда: Суббота, 25 марта 2017, 19:10–20:40
Где: ПОМИ РАН
Слайды: 2017_03_25_communicationcomplexity_2017_sprin_Qo6PweW.pdf

Описание

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

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

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

Видео

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