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

Лекция 4
Communication Complexity

What: Lecture
When: Sunday, 01 March 2009, 12:00–13:30
Where: ПОМИ РАН

Description

Невозможность избавиться от \( \log n \) в последнем утверждении (функция \( EQ \)). Для случайной функции метод размера прямоугольников значительно лучше метода трудного множества. Функция \( DISJ_k \) для \( k= \log n \). Верхние оценки \( \log C^0(DISJ_k)=O(\log n) \), \( \log C^1(DISJ_k)=O(\log n) \). Нижняя оценка \( D(DISJ_k)=\Omega(\log^2 n) \).

Video