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

Сложность вычислений и основы криптографии
Весна 2013, посмотреть все семестры

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

Курс знакомит со сложностью вероятностных вычислений и теоретическими основами криптографии. Мы изучим вероятностные классы сложности и основные приемы, которые используются для анализа и построения вероятностных алгоритмов, узнаем, что такое интерактивные протоколы, игры Артура и Мерлина, докажем знаменитую теорему Шамира IP=PSPACE, обсудим классы задач подсчета, поговорим о вероятностно проверяемых доказательства и PCP-теореме. В криптографической части курса мы поговорим об односторонних функциях, генераторах псевдослучайных чисел, протоколах с открытым и публичным ключом, привязке к биту и о доказательствах с нулевым разглашением.

Формально курс является продолжением курса Основы вычислимости и теории сложности, но на лекции приглашаются все желающие. Рекомендуется иметь представление о следующих понятиях: машины Тьюринга (детерминированные и недетерминированные), классы P, NP, PSPACE, NP-полнота, полиномиальная иерархия, булевы схемы. Все определения будут напоминаться по просьбе слушателей.

Литература:

  • S. Arora, B. Barak, Computational Complexity: A modern approach.
  • Ch. Papadimitriou, Computational Complexity.
  • O. Goldreich, Foundations of cryptography.
  • Н.К. Верещагин, Конспект лекций по теоретико-сложностным проблемам криптографии. [pdf]
Дата и время Название Место Материалы
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
Привязка к биту. Доказательства с нулевым разглашением., лекция ПОМИ РАН видео