City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 5
Communication Complexity

What: Lecture
When: Sunday, 26 March 2017, 15:30–17:00
Where: ПОМИ РАН
Slides: communicationcomplexity_lecture_260317.pdf

Description

Покрытия нулей и единиц матрицы \(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)\).

Video