Дневник лекций 2009 года

14-Dec-2009

Нижняя оценка \Omega(n) глубины коммуникационного протокола
для отношения PAIR-DISJOINTNESS (с помощью сведения
к вероятностной сложности функции DISJ).

Нижняя оценка \Omega(\sqrt n) глубины монотонных формул для
функции MATCHING.

7-Dec-2009

Теорема Храпченко. Логарифмические нижние оценки глубины формул для
функции четности и функции голосования методом Храпченко (через
глубину коммуникационного протокола).

Отношение FORK и нижняя оценка \Omega(\log l \log w) глубины коммуникационного
протокола для него. Сверх-логарифмическая
нижняя оценка глубины монотонных формул для булевой функции
s-t-СВЯЗНОСТЬ с помощью отношения FORK.

30-Nov-2009

Коммуникационная сложность отношений. Связь между формулами в базисе
И, ИЛИ, НЕ и коммуникационной сложностью.

Верхняя оценка O(log n) глубины формул для функции голосования с помощью
коммуникационной сложности.

23-Nov-2009

Нижняя оценка T\sqrt S =\Omega(D^{best} f) для времени и площади вычисления
схемы вычисления функции f. Оценка
D^{best}(f)=\Omega(n) для функции циклического равенства.

16-Nov-2009

Оценка T=\Omega(n^2) для одноленточных машин Тьюринга,
распознающих палиндромы.

Оценка TS=\Omega(n^2) для многоленточных машин Тьюринга,
распознающих палиндромы. Следствие: S=\Omega(log n).

Экспоненциальная нижняя оценка веса пороговых элементов для схем
глубины 2, вычисляющих IP.

9-Nov-2009

Применение коммуникационной сложности для оценки размера схем
из пороговых схем: С_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).

2-Nov-2009

Лемма Яо об использовании нижних оценок для среднего
количества битов, переданных для случайного входа по
данному распределению.

Discrepancy (неоднородность) и ее использование
для оценок вероятностной сложности предикатов.

26-Oct-2009

Безошибочная вероятностная сложность предиката DISJ_{mk}.

19-Oct-2009

Сравнение вероятностных сложностей между собой и сравнение их
с детерминированной и недетерминированной сложностями.

Вероятностные сложности предикатов NE, EQ, GT.
Сравнение вероятностных сложностей с общими и приватными битами.
Безошибочная вероятностная сложность предиката DISJ_{mk}.

12-Oct-2009

Функция DISJ_{m,k}. Верхняя оценка недетерминированной сложности
и нижняя оценка детерминированной сложности для этой функции.

Вероятностные протоколы. Общие и приватные случайные биты.
Двусторонняя и односторонняя ошибка. Среднее время и время в худшем
случае.

5-Oct-2009

Оптимальность метода размера прямоугольника для оценки
C^0,C^1 (с точностью до полиномиального множителя).
Неравество D(f) < C^1(f) + 1. Задача. Неустранимость этого множителя (EQ). Задача. Доказать, что для случайной функции нет больших трудных множеств и нет больших одноцветных прямоугольников.

Неравенство D(f) = O(\log C^0(f) \log C^1(f)).

28-Sep-2009

Задачи:
(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.

21-Sep-2009

Количество листьев в протоколе.
Величина 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

14-Sep-2009

Определение коммуникационного протокола с фиксированной длиной
каждого сообщения. Верхние оценки на коммуникационную сложность
D(f) для произвольной функции f:X*Y->Z.
Лографифмические верхние оценки
коммуникационной сложности функций MED и CIS.

Определение коммуникационного протокола с нефиксированной длиной
сообщений. Информационная нижняя оценка на коммуникационную сложность
функции сложения.

Разбиение матрицы функции на одноцветные прямоугольники.
Величина C^R(f) и ее связь с D(f).
Нижняя оценка коммуникационной сложности предиката равенства.