Нижняя оценка \Omega(n) глубины коммуникационного протокола для отношения PAIR-DISJOINTNESS (с помощью сведения к вероятностной сложности функции DISJ).
Нижняя оценка \Omega(\sqrt n) глубины монотонных формул для функции MATCHING.
Теорема Храпченко. Логарифмические нижние оценки глубины формул для функции четности и функции голосования методом Храпченко (через глубину коммуникационного протокола).
Отношение FORK и нижняя оценка \Omega(\log l \log w) глубины коммуникационного протокола для него. Сверх-логарифмическая нижняя оценка глубины монотонных формул для булевой функции s-t-СВЯЗНОСТЬ с помощью отношения FORK.
Коммуникационная сложность отношений. Связь между формулами в базисе И, ИЛИ, НЕ и коммуникационной сложностью.
Верхняя оценка O(log n) глубины формул для функции голосования с помощью коммуникационной сложности.
Нижняя оценка T\sqrt S =\Omega(D^{best} f) для времени и площади вычисления схемы вычисления функции f. Оценка D^{best}(f)=\Omega(n) для функции циклического равенства.
Оценка T=\Omega(n^2) для одноленточных машин Тьюринга, распознающих палиндромы.
Оценка TS=\Omega(n^2) для многоленточных машин Тьюринга, распознающих палиндромы. Следствие: S=\Omega(log n).
Экспоненциальная нижняя оценка веса пороговых элементов для схем глубины 2, вычисляющих IP.
Применение коммуникационной сложности для оценки размера схем из пороговых схем: С_w(f) > D^worst(f)/(log w+1) Применение для предиката GT: верхняя и нижняя оценки.
Применение коммуникационной сложности для оценки высоты деревьев разрешения: T_w(f) > D^worst(f)/(log w+1), RT_\eps(f) > R^worst_\eps(f)/polylog n
Линейная нижняя оценка вероятностной сложности предиката IP с помощью неоднородности. Упражнение. Доказать, что для любого распределения на входах выполнено disc=Omega(1/n).
Лемма Яо об использовании нижних оценок для среднего количества битов, переданных для случайного входа по данному распределению.
Discrepancy (неоднородность) и ее использование для оценок вероятностной сложности предикатов.
Безошибочная вероятностная сложность предиката DISJ_{mk}.
Сравнение вероятностных сложностей между собой и сравнение их с детерминированной и недетерминированной сложностями.
Вероятностные сложности предикатов NE, EQ, GT. Сравнение вероятностных сложностей с общими и приватными битами. Безошибочная вероятностная сложность предиката DISJ_{mk}.
Функция DISJ_{m,k}. Верхняя оценка недетерминированной сложности и нижняя оценка детерминированной сложности для этой функции.
Вероятностные протоколы. Общие и приватные случайные биты. Двусторонняя и односторонняя ошибка. Среднее время и время в худшем случае.
Оптимальность метода размера прямоугольника для оценки C^0,C^1 (с точностью до полиномиального множителя). Неравество D(f) < C^1(f) + 1. Задача. Неустранимость этого множителя (EQ). Задача. Доказать, что для случайной функции нет больших трудных множеств и нет больших одноцветных прямоугольников.
Неравенство D(f) = O(\log C^0(f) \log C^1(f)).
Задачи: (1) D(f) > log количества различных функций вида f(x,.) (2) D(f) < rk M(f) +1
Количество листьев в протоколе и неравенство D(f) < 2 log_{3/2} C^P(f)+O(1). Задача: улучшить константу в этом неравенстве: D(f) < 3 log_{2} C^P(f)+O(1).
Недетерминированные сложности N^0,N^1 предикатов. Покрытия нулей и единиц матрицы M(f) предиката f, величины C^0,C_1. Неравенства log C^0 < N^0 < log C^0 + 2
Неравество log C^0(f) < D(f) и пример предиката (EQ) с экспоненциальным разрывом между log C^0 и D.
Количество листьев в протоколе. Величина C^P(f) и неравенство C^P(f)<2^{D(f)}.
Нижняя оценка C^R(f) с помощью трудных множеств (fooling sets). Нижняя оценка C^R(f) для предикатов GT, DISJ.
Метод размера прямоугольников и нижняя оценка C^R(IP).
Метод ранга матрицы и нижняя оценка C^R(f) для функций IP, EQ, GT. Верхняя оценка D(f) < rk(f)+1
Определение коммуникационного протокола с фиксированной длиной каждого сообщения. Верхние оценки на коммуникационную сложность D(f) для произвольной функции f:X*Y->Z. Лографифмические верхние оценки коммуникационной сложности функций MED и CIS.
Определение коммуникационного протокола с нефиксированной длиной сообщений. Информационная нижняя оценка на коммуникационную сложность функции сложения.
Разбиение матрицы функции на одноцветные прямоугольники. Величина C^R(f) и ее связь с D(f). Нижняя оценка коммуникационной сложности предиката равенства.