Коммуникационные игры

Майская проектная программа по математике и теоретической информатике. Сириус,
29 апреля-22 мая 2024.
Преподаватели: Артур Игнатьев, Юрий Дементьев, Татьяна Белова, Тимофей Москаленко, Анастасия Мозголина, Вячеслав Сидельник.

Результаты участников

• Презентация результатов.
• Таблица с результатами.
• Чернышов Игнат. Полудуплексная коммуникационная сложность игры \(\text{KW}_{\text{RecMaj}_k}\).
• Пименов Марк. Оценки на коммуникационную сложность функции связности графа.
• Дидоренко Михаил. Разделение полудуплексной модели с честным противником и классической коммуникационной модели.
• Мекешкин Глеб. Нижняя оценка на функцию расстояние Хэмминга \(k\) с оракулом равенства.

Материал

• Презентация с открытия смены.
• Конспект смены.
• Задачи.
• Курс на stepik.

Дополнительный материал

• Обзор коммуникационной сложности. А. А. Разборов.
• Информация, кодирование и предсказание.
• Half-duplex communication complexity.
• New bounds on the half-duplex communication complexity.
• Communication Complexity. Eyal Kushilevitz, Noam Nisan.
• Communication Complexity. Anup Rao, Amir Yehudayoff.