Семинар по сложности булевых функций
Весна 2017, посмотреть все семестры

Булевы функции — это одни из наиболее важных и наиболее изученных объектов в теоретической информатике. Множество важнейших теоретических и прикладных вопросов можно переформулировать на языке булевых функций. На данном семинаре мы будем изучать сложность булевых функций — будем доказывать нижние оценки на размеры описания булевых функций в виде формул, схем и некоторых других представлений. Основные материалы, обсуждаемые на семинаре, будут из книги Boolean Function Complexity: Advances and Frontiers, Stasys Jukna, 2012.

Семинар входит в магистерскую программу теоретическая информатика Академического университета.

Дата и время Название Место Материалы
15 февраля
18:30–19:50
Введение в сложность булевых функций, семинар ПОМИ РАН Нет
22 февраля
18:30–19:50
Первые оценки на формульную сложность., семинар ПОМИ РАН Нет
01 марта
18:30–19:50
Квадратичные оценки на размер формул, семинар ПОМИ РАН Нет
15 марта
18:30–19:50
Метод случайных подстановок, семинар ПОМИ РАН Нет
22 марта
18:30–19:50
Формулы и прямоугольники, семинар ПОМИ РАН Нет