Что: | Лекция |
Когда: | Суббота, 28 февраля 2009, 10:25–11:55 |
Где: | ПОМИ РАН |
Определение детерминированного коммуникационного протокола. "Информационная'' нижняя оценка \( D(f)>n \) сложности функции \( f(x,y)=x+y \) сложения \( n \)-битовых чисел. Оценка \( D(f)=c \log n \) для коммуникационной сложности медианы мультимножества. Верхняя оценка \( D(f)=O(\log^2 n) \) для коммуникационной сложности функции \( CIS \). Одноцветные прямоугольники. Минимальное количества \( C^R(f) \) одноцветных прямоугольников в разбиении матрицы функции \( f \). Нижняя оценкка для детерминированной сложности предиката \( EQ \) с помощью разбиения матрицы функции на одноцветные прямоугольники.