Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English
Что: Лекция
Когда: Воскресенье, 26 марта 2017, 13:00–14:30
Где: ПОМИ РАН
Слайды: 2017_03_26_communicationcomplexity_2017_sprin_fT1JxiT.pdf

Описание

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

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

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

Видео