Город: Санкт-Петербург Казань Язык: Русский English

Сложность булевых функций
Санкт-Петербург / осень 2014, посмотреть все семестры

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

В рамках курса планируется рассказать об одном из основных направлений теории сложности вычислений — схемной сложности булевых функций.

Формальное изучение этой области началось еще в первой половине двадцатого века, то есть очень давно по меркам Computer Science. Бум развития схемной сложности пришелся на 80-е годы и был связан с идеей использования нижних оценок размера булевых схем, как подхода к проблеме о сложностных классах P и NP. Этот этап развития области привел к ряду прорывных результатов, новых методов и идей. Однако, оказалось, что получить решение проблемы о P и NP на этом пути (как и на всех других) не так просто. Более того, было доказано, что для решения этой проблемы посредством булевых схем нужны кардинально новые методы, и текущих методов принципиально не достаточно. В настоящее время работа в области схемной сложности продолжается, в последние годы был получен ряд интересных результатов.

В курсе будет дано введение в теорию схемной сложности булевых функций, рассказано о некоторых ключевых результатах в области, а также о связях с другими моделями вычислений. Основной акцент планируется сделать на методах доказательства нижних оценок в схемной сложности. Также мы попробуем показать, как результаты теории схемной сложности, могут применяться к другим областям Computer Science, на примере вопросов о сложности обработки запросов к онтологическим базам данных.

Задачи и критерии получения оценки за курс можно найти на странице курса на сайте CS клуба. Решения задач можно слать Владимиру Подольскому до конца семестра.

Дата и время Название Место Материалы
25 октября
17:20–18:55
Булевы схемы и формулы, лекция ПОМИ РАН видео
25 октября
19:00–20:35
Булевы формулы и коммуникационная сложность, лекция ПОМИ РАН видео
26 октября
11:15–12:50
Монотонные формулы для задачи «Достижимость», сведение к коммуникационным играм, лекция ПОМИ РАН видео
26 октября
13:00–14:35
Монотонные формулы для задачи «Достижимость», нижняя оценка, лекция ПОМИ РАН видео
26 октября
15:35–17:10
Монотонные формулы для функций «Паросочетание» и «Клика», лекция ПОМИ РАН видео
01 ноября
17:20–18:50
Нижняя оценка для монотонных схем, начало, лекция ПОМИ РАН видео
01 ноября
19:00–20:30
Нижняя оценка для монотонных схем, окончание, лекция ПОМИ РАН видео
02 ноября
11:15–12:50
Приложение: онтологические базы данных, лекция ПОМИ РАН видео
02 ноября
13:00–14:35
Схемы ограниченной глубины: приближение многочленами, лекция ПОМИ РАН видео
02 ноября
15:35–17:10
Пороговые схемы, лекция ПОМИ РАН видео