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

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

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

Список литературы:

• [RY20] Anup Rao и Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. doi: 10.1017/9781108671644.
• [Cha+19] Arkadev Chattopadhyay, Michal Kouck´y, Bruno Loff и Sagnik Mukhopadhyay. “Simulation Theorems via Pseudo-random Properties”. в: BULL. AMER. MATH. SOC. 28 (4 2019). issn: 1420-8954. doi: https : / / doi . org / 10.1007/s00037-019-00190-7.
• [GP14] Mika G¨o¨os и Toniann Pitassi. “Communication lower bounds via critical block sensitivity”. в: Symposium on Theory of  Computing, STOC 2014, New York, NY, USA, May 31 — June 03, 2014. под ред. David B. Shmoys. ACM, 2014, с. 847—856. doi: 10.1145/2591796.2591838. url: https://doi.org/10.1145/2591796.2591838.
• [KN96] Eyal Kushilevitz и Noam Nisan. Communication Complexity. Cambridge University Press, 1996. doi: 10.1017/CBO9780511574948.

Программа курса

Лекторы