20.10.2015 Игры на пути доказательства Sensitivity Conjecture (Николай Карпов)

Начало семинара будет посвящено сложности булевых функций и различных её мерах, мы сформулируем Sensitivity Conjecture и обсудим её связь с некой коммуникационной игрой.
В ней Алиса и Боб пытаются не быть обманутыми Евой или заплатить за обман маленькую цену. Оценки на цену препятствия обману будут тесно (с некоторой стороны) связаны с чувствительностью широкого класса функций. Мы обсудим нетривиальные стратегии в игре и её вариациях, нижние оценки на протоколы особого вида и рассмотрим некоторые эквивалентные переформулировки игры, поддающиеся (с натяжкой) анализу на компьютерах.