Laboratory of Mathematical Logic at PDMI

Пятница, 10 октября, комната 106. Начало в 19:00.

Докладчик: Ю. М. Лифшиц.

Тема: Коммуникационная сложность неравенства многоугольника.

Abstract

В докладе будет разобрана следующая задача: берем k натуральных чисел от 1 до n и раздаем их k участникам (i-ому участнику достаются все числа кроме i-ого). Участники хотят выяснить, удовлетворяет ли этот набор чисел неравенству многоугольника. Коммуникационной сложностью этой задачи назовем минимальное количество информации, которым им придется обменяться для выяснения ответа. Основной результат доклада: коммуникационная сложность неравенства многоугольника неограниченно растет с ростом n. Ключевым шагом в доказательстве является использование обобщения теоремы ван дер Вардена.