Спецкурс Коммуникационная сложность

1 view

Skip to first unread message

Nikolay Vereshchagin

unread,

Feb 10, 2026, 2:25:34 AM (10 days ago) Feb 10

to Kolmogorov seminar on complexity

Полугодовой спецкурс для студентов 2–5 курсов и аспирантов
Коммуникационная сложность
будет читаться проф. Н.К. Верещагиным по вторникам в 18:30-20:05 в ауд.
407 второго уч. корпуса. Первая лекция — 17 февраля.

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

Предварительные знания: знакомство с линейной алгеброй в объеме одного семестра и с началами теории вероятностей.

Телеграмм канал: https://t.me/+9G993a4ym640ZTVi (там есть ссылка на подробную программу)

Nikolay Vereshchagin

unread,

Feb 10, 2026, 2:37:09 AM (10 days ago) Feb 10

to Kolmogorov seminar on complexity

Исправление: спецкурс предназначен для 3-6 курсов, магистрантов и аспирантов.

--
Вы получили это сообщение, поскольку подписаны на группу "Kolmogorov seminar on complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес kolmogorov-seminar-on-...@googlegroups.com.
Чтобы посмотреть обсуждение, перейдите по ссылке https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/83b0d8bd-7ddd-413e-8cc1-08cf188983d3n%40googlegroups.com.