Булевы функции — это одни из наиболее важных и наиболее изученных объектов в теоретической информатике. Множество важнейших теоретических и прикладных вопросов можно переформулировать на языке булевых функций. На данном семинаре мы будем изучать сложность булевых функций — будем доказывать нижние оценки на размеры описания булевых функций в виде формул, схем и некоторых других представлений. Основные материалы, обсуждаемые на семинаре, будут из книги Boolean Function Complexity: Advances and Frontiers
, Stasys Jukna, 2012.
Семинар входит в магистерскую программу теоретическая информатика Академического университета.
| Date and time | Class|Name | Venue|short | Materials |
|---|---|---|---|
| 15 February 18:30–19:50 |
Введение в сложность булевых функций, Seminar | ПОМИ РАН | No |
| 22 February 18:30–19:50 |
Первые оценки на формульную сложность., Seminar | ПОМИ РАН | No |
| 01 March 18:30–19:50 |
Квадратичные оценки на размер формул, Seminar | ПОМИ РАН | No |
| 15 March 18:30–19:50 |
Метод случайных подстановок, Seminar | ПОМИ РАН | No |
| 22 March 18:30–19:50 |
Формулы и прямоугольники, Seminar | ПОМИ РАН | No |
| 29 March 18:30–19:50 |
Выпуклые меры и препятствия для доказательства нижних оценок, Seminar | ПОМИ РАН | No |
| 05 April 18:30–19:50 |
Графовая сложность, Seminar | ПОМИ РАН | No |
| 12 April 18:30–19:50 |
Деревья принятия решений, начало, Seminar | ПОМИ РАН | No |
| 19 April 18:30–19:50 |
Деревья принятия решений, Seminar | ПОМИ РАН | No |
| 26 April 18:30–19:50 |
Деревья принятия решений для задачи поиска, Seminar | ПОМИ РАН | No |
| 03 May 18:30–19:50 |
Деревья принятия решений и многочлены, Seminar | ПОМИ РАН | No |
| 10 May 18:30–19:50 |
Линейные деревья принятия решений, Seminar | ПОМИ РАН | No |
