Коммуникационная сложность

Общая информация
ЛекторН. К. Верещагин
Семестрвесна 2009
Дата начала28.02.2009
Количество пар10
Язык курсарусский
Видеоhttp://lektorium.tv/course/?id=22755
Аннотация Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений.

Дополнительные материалы
Содержание лекций: pdf.
Конспект лекций: pdf.
Вопросы к экзамену: pdf.
Доказательство верхней оценки безошибочной сложности предиката дизъюнктности: pdf.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1
(28.02.2009 - 12:00)

Определение детерминированного коммуникационного протокола. "Информационная'' нижняя оценка $ 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 $ с помощью разбиения матрицы функции на одноцветные прямоугольники. http://video.google.com/videoplay?docid=8357400918184006255
2. Лекция 2
(28.02.2009 - 12:00)

Нижние оценки $ 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 $. http://video.google.com/videoplay?docid=2664244475866452067
3. Лекция 3
(01.03.2009 - 12:00)

Связь между детерминированной сложностью и разбиениями матрицы функции на одноцветные прямоугольники: $ \log C^P(f) $ не превосходит $ D(f) $ и, обратно, $ D(f)=O(\log C^P(f)) $. Теорема о связи детерминированной и недетерминированной сложности: $ D(f) $ есть $ O(\log C^0(f) \log C^1(f)) $. Универсальность метода размера прямоугольников для оценки $ \log C^0(f) $ с точностью до $ \log n $: для всех $ f $ найдется распределение вероятностей $ \mu $ на нулях функции, для которого $ \log C^0(f) $ меньше $ -\log \mu(R)+ \log n $ для всех нуль-цветных прямоугольников $ R $. http://video.google.com/videoplay?docid=-2830072124894978808
4. Лекция 4
(01.03.2009 - 12:00)

Невозможность избавиться от $ \log n $ в последнем утверждении (функция $ EQ $). Для случайной функции метод размера прямоугольников значительно лучше метода трудного множества. Функция $ DISJ_k $ для $ k= \log n $. Верхние оценки $ \log C^0(DISJ_k)=O(\log n) $, $ \log C^1(DISJ_k)=O(\log n) $. Нижняя оценка $ D(DISJ_k)=\Omega(\log^2 n) $. http://video.google.com/videoplay?docid=7904640876502963386
5. Лекция 5
(01.03.2009 - 12:00)

Вероятностные коммуникационные протоколы с частными датчиками. Три способа определения вычисления функции (с двусторонней ошибкой, с односторонней ошибкой и безошибочное). Два способа определения коммуникационной сложности вероятностного протокола (как максимума по всех входам среднего количества переданных битов и как максимума по всех входам максимума по всем случайным битам количества переданных битов). Обозначения $ R_0(f), R^1_{\eps}(f), R_{\eps}(f) $ и соотношения между этими величинами. Уменьшение вероятности ошибки за счет повторения протокола.
6. Лекция 6
(07.03.2009 - 12:25)

Вероятностный тест для равенства, оценка $ R^1_{\epsilon}(NE)=O(\log (n/\epsilon)) $. Оценка $ R^1_{\epsilon}(f)>\log C^1(f) $ и как следствие $ R^1_{\epsilon}(NE)>\log n $. Оценка $ R_{\epsilon}(GT)=O(\log^2 n) $. Теорема о связи детерминированной и вероятностной сложности: $ R_{\epsilon}(f)=\Omega(\log C(f)) $. Вероятностные коммуникационные протоколы с общим источником случайности и обозначение $ R^{pub}_{\eps}(f) $. Оценка $ R^{pub,1}_{\epsilon}(NE)=O(-\log \epsilon) $. http://video.google.com/videoplay?docid=-8115708228237016134
7. Лекция 6
(07.03.2009 - 12:25)

Вероятностный тест для равенства, оценка $ R^1_{\epsilon}(NE)=O(\log (n/\epsilon)) $. Оценка $ R^1_{\epsilon}(f)>\log C^1(f) $ и как следствие $ R^1_{\epsilon}(NE)>\log n $. Оценка $ R_{\epsilon}(GT)=O(\log^2 n) $. Теорема о связи детерминированной и вероятностной сложности: $ R_{\epsilon}(f)=\Omega(\log C(f)) $. Вероятностные коммуникационные протоколы с общим источником случайности и обозначение $ R^{pub}_{\eps}(f) $. Оценка $ R^{pub,1}_{\epsilon}(NE)=O(-\log \epsilon) $. http://video.google.com/videoplay?docid=-8115708228237016134
8. Лекция 7
(07.03.2009 - 12:25)

Теорема о переделывании общего источника в частный с увеличением сложности на $ O(\log n): R_{\epsilon+\delta}(f) $ не превосходит $ R^{pub}_{\epsilon}(f)+O(\log n-\log \delta)) $. Нижняя оценка $ R^{pub}_{\epsilon}(f) $ методом трудных распределений вероятностей на входных парах. Неоднородность (discrepancy) функции для данного распределения и оценка трудности распределения через неоднородность. Линейная нижняя оценка для $ R^{pub}_{\epsilon}(IP) $. Нижняя оценка для неоднородности предиката DISJ: для любого распределения $ \mu $ выполнено $ disc_\mu(DISJ) n > 1 $. http://video.google.com/videoplay?docid=7183277349762900037
9. Лекция 8
(08.03.2009 - 12:25)

Вероятностная сложность предиката $ GT $: верхние оценки $ R^{pub}_{\epsilon}(GT)=O(\log n \log\log n) $ и $ R_{\epsilon}(GT)=O(\log n) $. Верхняя оценка безошибочной вероятностной сложности для функции $ DISJ_{\log n} $: $ R_{0}(DISJ_{\log n})=O(\log n) $. http://video.google.com/videoplay?docid=968480966769311673
10. Лекция 9
(08.03.2009 - 12:25)

Нижняя оценка на глубину дерева разрешения с линейными проверками, вычисляющего булеву данную функцию $ f $ в терминах коммуникационной сложности $ f $. Нижняя оценка количества элементов в схеме с пороговыми элементами ограниченного веса в терминах коммуникационной сложности. Экспоненциальная нижняя оценка весов пороговых элементов в схемах глубины $ 2 $, вычисляющих предикат $ IP $. http://video.google.com/videoplay?docid=968480966769311673
11. Лекция 10
(08.03.2009 - 12:25)

Нижняя оценка $ ST=\Omega(n^2) $ для зоны $ S $ и времени работы многоленточной машины Тьюринга, распознающей палиндромы. Квадратичная нижняя оценка на время распознавания палиндромов на одноленточной машине Тьюринга. Детерминированная сложность $ D^{best}(f) $ булевой функции $ f $ (минимальная из сложностей $ D(f) $ по всем разбиениям множества входных битов на две равных части). Оценка $ D^{best}(f) $ для функции циклического равенства. Нижняя оценка $ (\sqrt A)T>D^{best}(f) $ для площади $ А $ и времени работы $ T $ микросхемы, вычисляющей булеву функцию $ f $. http://video.google.com/videoplay?docid=-824485376318672917
Ваша оценка: Пусто Средняя: 5 (1 голос)
Share |
Лекция Николая Константиновича Верещагина
Николай Константинович Верещагин