Search
Семинар 12 декабря 2008 года
Пятница, 12 декабря, комната 106. Начало в 17:55.
Докладчик: Г. Ярославцев.
Тема: Коммуникационная сложность и глубина схем для булевых функций.
Abstract
Существует связь между понятием коммуникационной сложности функции и минимальной глубиной булевой схемы, её вычисляющей. Эта связь была сформулирована в виде игр Карчмера-Вигдерсона, о различных видах которых будет рассказано. Игры Карчмера-Вигдерсона позволили получить неизвестные ранее оценки на глубину схем многих булевых функций. В качестве примера будут продемонстрированы наиболее эффективные из известных коммуникационных протоколов для игр Карчмера-Вигдерсона для произвольных симметрических функций и для функции 
. Игры Карчмера-Вигдерсона также были обобщены на случай монотонных функций. Будет рассказано о том, каким образом это может быть сделано, а также будут приведены результаты оценок глубины монотоннных схем для булевых функций, полученные с помощью монотонных игр Карчмера-Вигдерсона.