Дневник лекций 2013 года
16-Sep-2013
Определение коммуникационного протокола.
Верхние оценки на коммуникационную сложность
D(f) для произвольной функции f:X*Y->Z.
Лографифмические верхние оценки
коммуникационной сложности функций MED и CIS.
Информационные нижние оценки на коммуникационную сложность
этих функций.
Разбиение матрицы функции на одноцветные прямоугольники.
Величина C^R(f) и ее связь с D(f).
Нижняя оценка коммуникационной сложности предиката равенства.
23-Sep-2013
Количество листьев в протоколе.
Величина C^P(f) и неравенство C^P(f)<2^{D(f)}.
Количество листьев в протоколе и неравенство
D(f) < 2 log_{3/2} C^P(f)+O(1).
Нижняя оценка
C^R(f) с помощью
трудных множеств (fooling sets).
Нижняя оценка
C^R(f) для предикатов GT, DISJ.
Метод размера прямоугольников и нижняя оценка
C^R(IP).
Метод ранга матрицы и нижняя оценка
C^R(f) для функций IP, EQ, GT. Задача: доказать, что D(f) < rk(f)+1
Недетерминированные сложности N^0,N^1 предикатов.
Покрытия нулей и единиц матрицы M(f) предиката f, величины
C^0,C_1.
Неравество log C^0(f) < D(f) и
пример предиката (EQ) с экспоненциальным разрывом между log C^0 и D.
30-Sep-2013
Неравенство D(f) < (\log C^0(f)+2)(\log C^1(f)+1).
Функция DISJ_{m,k}. Верхняя оценка недетерминированной сложности
и нижняя оценка детерминированной сложности для этой функции.
7-Oct-2013
Вероятностные протоколы. Общие и приватные случайные биты.
Двусторонняя и односторонняя ошибка. Среднее время и время в худшем
случае.
Логарифмическая верхняя оценка односторонней сложности предиката
равенства. Оценка O(log^2 n) двусторонней сложности предиката GT.
Оценка нульсторонней сложности через сумму односторонних слжностей и
сложности с нулевой ошибкой через нульстороннюю сложность.
Amplification для односторонней сложности.
14-Oct-2013
Amplification для двусторонней сложности.
Связь односторонней и недетерминированной сложностей.
Связь двусторонней и детерминированной сложностей.
Переход от общих к частным случайным битам (теорема Ньюмана).
21-Oct-2013
Вероятностный безошибочный протокол для DISJ_nk.
Нижние оценки двусторонное вероятностной сложности
с помощью распределений вероятностей на входах.
Теорема Фон-Ноймана и универсальность этого метода.
28-Oct-2013
Пестрота. Нижняя оценка двусторонней вероятностной сложности
предиката
скалярного произведения с помощью пестроты.
Логарифмическая верхняя оценка для вероятностной сложности предиката
GT
4-Nov-2013
Выходной — лекции не было.
11-Nov-2013
Примеры сведения задач в коммуникационной сложности. Сложность
двух вариантов функции голосования.
Сложности D^worst и D^best. Линейная нижняя оценка сложности
D^best для предиката SEQ
18-Nov-2013
Нижняя оценка D^best для предиката умножения.
Нижняя оценка D^best для предиката MATCH.
Нижняя оценка ST^2 для микросхем.
Нижняя оценка для разрешающих деревьев и схем из функциональных элементов.
25-Nov-2013
Пороговые элементы для функции GT. Достаточность и необходимость
эскпоненциальных весов.
Нижняя оценка для схем глубины 2 из пороговых элементов для предикатов
высокой вероятностной сложности
Квадратичная нижняя оцентка ST для многолентночных машин Тьюринга, распознающих
палиндромы.
Квадратичная нижняя времени для однолентночных машин Тьюринга, распознающих
палиндромы.
2-Dec-2013
Связь глубины и размера формул с глубиной и размером коммуникационных
протоколов
Коммуникационная сложность универсального отношения и универсального
монотонного отношения.
Коммуникационная сложность функции четности и размер формул для нее (верхняя оценка)
Коммуникационная сложность функции голосования и размер формул для нее (верхняя оценка)
9-Dec-2013
Теорема Храпченко.
Нижняя оценка размера формул для функции четности
и функции голосования
Отношение FORK и сведение к нему монотонного отношения для
st-связности
16-Dec-2013
Нижняя оценка сложности отношения FORK
Прямое построение схемы логарифмической глубины для функции голосования.