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

Описание

Покрытия нулей и единиц матрицы \(M(f)\) предиката \(f\). Применение метода размера прямоугольников для оценки этого покрытия. Недетерминированная сложность предикатов. Неравенство \(D(f) < 2^{N(f)}+1\). Пример предиката (EQ) с экспоненциальным разрывом между \(N(f)\) и \(D(f)\).

Неравенство \(D(f) < (N(f)+2)(N(\lnot f)+1)\).

Пример (\(DISJ_{nk}\)) функции с квадратичным разрывом между \(D(f)\) и \(N(f),N(\lnot f)\).

Видео