Что: Лекция
Когда: Воскресенье, 26 марта 2017, 13:00–14:30
Где: ПОМИ РАН
Слайды: communicationcomplexity_lecture_260317.pdf

Описание

Связь вероятностной и детерминированной сложностей. Нижняя оценка вероятностной сложности предиката EQ.

Нижние оценки двусторонней вероятностной сложности с помощью распределений вероятностей на входах. Теорема Фон-Ноймана и универсальность этого метода.

Пестрота. Нижняя оценка двусторонней вероятностной сложности предиката скалярного произведения с помощью пестроты.

Видео