Булевы функции — это одни из наиболее важных и наиболее изученных объектов в теоретической информатике. Множество важнейших теоретических и прикладных вопросов можно переформулировать на языке булевых функций. На данном семинаре мы будем изучать сложность булевых функций — будем доказывать нижние оценки на размеры описания булевых функций в виде формул, схем и некоторых других представлений. Основные материалы, обсуждаемые на семинаре, будут из книги 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 |
Формулы и прямоугольники, Семинар | ПОМИ РАН | Нет |
| 29 марта 18:30–19:50 |
Выпуклые меры и препятствия для доказательства нижних оценок, Семинар | ПОМИ РАН | Нет |
| 05 апреля 18:30–19:50 |
Графовая сложность, Семинар | ПОМИ РАН | Нет |
| 12 апреля 18:30–19:50 |
Деревья принятия решений, начало, Семинар | ПОМИ РАН | Нет |
| 19 апреля 18:30–19:50 |
Деревья принятия решений, Семинар | ПОМИ РАН | Нет |
| 26 апреля 18:30–19:50 |
Деревья принятия решений для задачи поиска, Семинар | ПОМИ РАН | Нет |
| 03 мая 18:30–19:50 |
Деревья принятия решений и многочлены, Семинар | ПОМИ РАН | Нет |
| 10 мая 18:30–19:50 |
Линейные деревья принятия решений, Семинар | ПОМИ РАН | Нет |
