Курс знакомит со сложностью вероятностных вычислений и теоретическими основами криптографии. Мы изучим вероятностные классы сложности и основные приемы, которые используются для анализа и построения вероятностных алгоритмов, узнаем, что такое интерактивные протоколы, игры Артура и Мерлина, докажем знаменитую теорему Шамира IP=PSPACE, обсудим классы задач подсчета, поговорим о вероятностно проверяемых доказательства и PCP-теореме. В криптографической части курса мы поговорим об односторонних функциях, генераторах псевдослучайных чисел, протоколах с открытым и публичным ключом, привязке к биту и о доказательствах с нулевым разглашением.
Формально курс является продолжением курса Основы вычислимости и теории сложности, но на лекции приглашаются все желающие. Рекомендуется иметь представление о следующих понятиях: машины Тьюринга (детерминированные и недетерминированные), классы P, NP, PSPACE, NP-полнота, полиномиальная иерархия, булевы схемы. Все определения будут напоминаться по просьбе слушателей.
Литература:
Дата и время | Занятие | Место | Материалы |
---|---|---|---|
21 февраля 18:30–19:50 |
Вероятностные классы сложности, Лекция | ПОМИ РАН | видео |
28 февраля 18:30–19:50 |
Интерактивные протоколы, Лекция | ПОМИ РАН | видео |
07 марта 18:30–19:50 |
Игры Артура и Мерлина, Лекция | ПОМИ РАН | видео |
14 марта 18:30–19:50 |
Подсчет числа подсказок. Лемма Вэлианта-Вазирани, Лекция | ПОМИ РАН | видео |
21 марта 18:30–19:50 |
Теорема Тода. Схемная сложность класс PP, Лекция | ПОМИ РАН | видео |
28 марта 18:30–19:50 |
Вероятностно проверяемые доказательства, Лекция | ПОМИ РАН | видео |
04 апреля 18:30–19:50 |
Экспоненциальная PCP-теорема, Лекция | ПОМИ РАН | видео |
11 апреля 18:30–19:50 |
Односторонние функции, Лекция | ПОМИ РАН | видео |
18 апреля 18:30–19:50 |
Генератор псевдослучайных чисел, Лекция | ПОМИ РАН | видео |
25 апреля 18:30–19:50 |
Трудный бит. Псевдослучайные функции., Лекция | ПОМИ РАН | видео |
16 мая 18:30–19:50 |
Протоколы с секретным и открытым ключом, Лекция | ПОМИ РАН | видео |
16 мая 20:00–21:45 |
Привязка к биту. Доказательства с нулевым разглашением., Лекция | ПОМИ РАН | видео |