Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Суббота, 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 \) с помощью разбиения матрицы функции на одноцветные прямоугольники.

Видео