You are currently at the new webpage of the Club. The list of all courses of the Club is available at the old page: old.compsciclub.ru
City: Saint-Petersburg Kazan Language: Русский English

Communication Complexity
Spring 2017, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений.

Примерная программа

  • Логарифмические верхние оценки коммуникационной сложности функций MED и CIS.

  • Вероятностные протоколы с логарифмической и константной коммуникацией для предиката равенства.

  • Связь детерминированной сложности с разбиением на одноцветные прямоугольники.

  • Методы доказательства нижних оценок для разбиений и покрытий прямоугольниками.

  • Теорема (Aho-Ullman-Yannakakis, Halstenberg-Reischuk) о квадратичной верхней оценке детерминированной сложности через недетерминированную

  • Теорема Разборова о квадратичном разрыве между недетерминированной и детерминированной сложностями.

  • Вероятностный протокол логарифмической сложности для GT (U. Feige, D. Peleg, P. Raghavan, and E. Upfal)

  • Сравнение вероятностных сложностей с общими и приватными битами (теорема Ньюмана).

  • Безошибочная вероятностная сложность предиката \(DISJ_{mk}\) (теорема Хостада-Вигдерсона).

  • Пестрота. Линейная нижняя оценка вероятностной сложности предиката IP (Chor--Goldreich).

  • Линейная нижняя оценка вероятностной сложности предиката DISJ (Kalyanasundaram--Schnitger, 1992; Razborov, 1992; Bar-Yossef--Jayram--Kumar, 2004; Braverman--Moitra, 2013)

  • Информационная сложность протоколов, теорема о прямой сумме (Барак--Браверман--Чен--Рао).

  • Сжатие протоколов (Барак--Браверман--Чен--Рао).

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

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

Литература

Kushilevitz, E. and N. Nisan. Communication complexity. Cambridge University Press, 1997.

Rao A., Yehudayoff A. Communication complexity. A draft of a textbook https://www.dropbox.com/s/ni8j3mmq98cr4ur/book.pdf?dl=0

Date and time Class|Name Venue|short Materials
25 March
17:20–18:50
Лекция 1, lecture ПОМИ РАН slidesvideo
25 March
19:10–20:40
Лекция 2, lecture ПОМИ РАН slidesvideo, files
26 March
11:15–12:45
Лекция 3, lecture ПОМИ РАН slidesvideo
26 March
13:00–14:30
Лекция 4, lecture ПОМИ РАН slidesvideo
26 March
15:30–17:00
Лекция 5, lecture ПОМИ РАН slidesvideo
01 April
17:20–18:50
Лекция 6, lecture ПОМИ РАН slidesvideo
01 April
19:10–20:40
Лекция 7, lecture ПОМИ РАН videofiles
02 April
11:15–12:45
Лекция 8, lecture ПОМИ РАН video
02 April
13:00–14:30
Лекция 9, lecture ПОМИ РАН videofiles
02 April
15:30–17:00
Лекция 10, lecture ПОМИ РАН videofiles
21 April 2017

Ошибка в задачи №11

Обнаружилась ошибка в формулировке задачи 11. Задание обновлено.

Если вы решите задачу в новой формулировке, то решение можно дослать Николаю Константиновичу по почте nikolay.vereshchagin@gmail.com.

14 April 2017

Ошибка в формулировке одной из задач экзамена

Обнаружилась ошибка в формулировке одной из задач экзамена. Условия обновлены.

20 March 2017

План лекций.

Выложено примерное содержание лекций и конспекты доказательств наиболее сложных теорем.

20 March 2017

Экзаменационное задание.

Выложено экзаменационное задание. Это - предварительная версия, задание будет уточняться, окончательная версия появится на следующий день после последней лекции, то есть, 3-его апреля.