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

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

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

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

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

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

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

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