Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Семинар по сложности булевых функций
Весна 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
Квадратичные оценки на размер формул, семинар ПОМИ РАН Нет