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