Коммуникационная сложность
Полугодовой спецкурс для студентов и аспирантов мехмата МГУ
2022 год, осенний семестр
Лектор: Н.К. Верещагин
Контакты: nikolay.vereshchagin@gmail.com, https://t.me/nikolay_vereshchagin
Телеграмм канал для вопросов https://t.me/+9G993a4ym640ZTVi
Лекции проходят по четвергам 18:30 — 20:05 онлайн. Первая лекция — 6 октября. Ссылка на Zoom: https://us06web.zoom.us/j/84630363941?pwd=VGVxUGMzUXBzUUJxZTdpWkFHQ0taZz09
Записи на доске | Записи лекций на YouTube
Новости
13 октября 2022 года лекции не будет. Следующая лекция состоится 20 октября 2022.
Посещавшие лекции и желающие сдать экзамен должны решить вот эти задачи в указанные сроки (скопируйте эту ссылку на Dropbox, поскольку сайт кафедры часто падает). Сдача задач после срока невозможна.
Оценки за решения домашних задач
Оценки за курс (при условии посещения не менее 7 лекций):
отлично — 80% от максимального количества баллов,
хорошо — 62%, удовлетворительно — 45%. Зачет — 50%.
Литература.
1. Anup Rao and Amir Yehudayoff, Communication Complexity: and Applications
2. Eyal Kushilevitz and Noam Nisan, Communication Complexity
Конспект теоремы о верхней оценке вероятностной безошибочной сложности предиката DISJnk
Конспект теоремы о нижней оценке вероятностной сложности предиката DISJ