City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Boolean Functions Complexity
Saint Petersburg / autumn 2011, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Семинар посвящен одному из самых известных и сложных направлений theoretical computer science — схемной сложности булевых функций. Схема является очень естественной моделью вычисления булевых функций. Из мощностных соображений легко следует, что для почти любой булевой функции \( f \colon \{0,1\}^n \rightarrow \{0,1\} \) размер минимальной вычисляющей её схемы экспоненциален. Несмотря на это, до сих пор не известно ни одной явно заданной функции, требующей схем более чем линейного размера. По этой причине интенсивно изучаются ограниченные модели вычислений (такие как монотонные схемы, схемы ограниченной глубины, формулы, ветвящиеся программы). На семинаре будут рассмотрены различные методы доказательства нижних оценок для таких моделей. Семинар будет основан на новой книге Стасиса Юкны Boolean Function Complexity: Advances and Frontiers.

Заинтересованным студентам будут выданы темы для доклада на семинаре. Подготовка к докладу подразумевает тщательное изучение выданной темы и подготовку слайдов. В конце семинара будет проведён экзамен.

Курсы по схемной сложности (с lecture notes!)

Дополнительная литература

Date and time Class|Name Venue|short Materials
25 September
13:00–14:35
Введение (А. Куликов), Lecture ПОМИ РАН slides,  files
02 October
11:15–12:50
Линейные нижние оценки на схемы без ограничений и метод элиминации гейтов (А. Куликов), Lecture ПОМИ РАН slides,  files
02 October
13:00–14:35
Линейные нижние оценки на схемы без ограничений и метод элиминации гейтов, продолжение (А. Куликов), Lecture ПОМИ РАН slides,  files
23 October
13:00–14:35
Связь нижних оценок на графовую сложность с задачей P vs NP (И. Михайлин), Lecture ПОМИ РАН slides,  files
30 October
13:00–14:35
Нижние оценки для формул (И. Близнец), Lecture ПОМИ РАН slides,  files
06 November
13:00–14:35
Коммуникационная сложность и глубина схем (А. Головнёв), Lecture ПОМИ РАН slides,  files
06 November
15:35–17:10
Монотонные формулы (Е. Деменков), Lecture ПОМИ РАН slides,  files
20 November
11:15–12:50
Монотонные схемы (А. Кноп), Lecture ПОМИ РАН slides,  files
20 November
13:00–14:35
Отрицания в схемах (В. Алексеенко), Lecture ПОМИ РАН slides,  files
27 November
13:00–14:35
Схемы глубины 3 (В. Рассохин), Lecture ПОМИ РАН No
11 December
15:35–17:10
Схемы ограниченной глубины (Р. Колганов), Lecture ПОМИ РАН slides,  files