Информация по курсу

Коммуникационная сложность изучает коммуникацию, как вычислительный ресурс. Базовая модель коммуникационной сложности рассматривает двух участников: Алису и Боба. Их задача посчитать значение известной функции на некотором входе, распределенном между ними. Для этого участники общаются по заранее обговоренному протоколу, а мы измеряем число переданных бит между участниками во время подсчета функции. Эта задача, как и ее вариации часто встречается как на практике, так и на разных уровнях математической абстракции вычислений — в сетевых протоколах, алгоритмах для NP-трудных задач, нижних оценках на булевы схемы.

В этом курсе мы обсудим классические результаты коммуникационной сложности, а также затронем часть последних исследований и открытых вопросов. Мы исследуем различные коммуникационные модели — детерминированную, недетерминированную, вероятностную и протоколы с несколькими участниками. Основной нашей задачей будет изучение техник для доказательства нижних оценок, но мы
также рассмотрим и некоторые применения.

Список литературы:
[Juk10] Stasys Jukna. Extremal Combinatorics: With Applications in Computer Science.
1st. Springer Publishing Company, Incorporated, 2010. isbn: 3642085598,
9783642085598.

[AB09] Sanjeev Arora и Boaz Barak. Computational Complexity: A Modern Approach.
1st. New York, NY, USA: Cambridge University Press, 2009. isbn: 0521424267,
9780521424264.

[HLW06] Shlomo Hoory, Nathan Linial и Avi Wigderson. “Expander graphs and their
applications”. в: BULL. AMER. MATH. SOC. 43.4 (2006), с. 439—561.

[AS00] Noga Alon и Joel H. Spencer. The probabilistic method. 2000.

Лекторы