What: | Lecture |
When: | Saturday, 28 February 2009, 12:00–13:30 |
Where: | ПОМИ РАН |
Нижние оценки $ C^R(f) $ методом трудных множеств для функций $ EQ, GT, DISJ $. Нижняя оценка $ C^R(f)>2^n $ методом размера прямоугольников для функции $ IP $ (Inner Product). Нижние оценки для $ C^R(f) $ методом ранга для функций IP, EQ, GT. Оценка $ D(f)< rk(f)+1 $. Покрытия нулей и единиц матрицы функции одноцветными прямоугольниками. Величины $ C^0(f),C^1(f) $ и интерпретация их логарифмов как недетерминированной коммуникационной сложности. Неравенство: $ D(f) $ меньше $ C^1(f)+1 $ и $ C^0(f)+1 $. Верхняя и нижняя оценки $ C^0(f) $ и $ C^1(f) $ для функций $ EQ,GT $.