Лекции Н. К. Верещагина по коммуникационной сложности

38 подписчиков

С 28-го февраля по 8-е марта в рамках Computer Science клуба при ПОМИ РАН Николай Константинович Верещагин (МГУ) прочтёт курс лекций по коммуникационной сложности. Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для решения задачи, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений.