City: Saint Petersburg Novosibirsk Kazan Language: Русский English

The computational complexity and foundations of cryptography
Saint Petersburg / spring 2012, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Учёным всегда было присуще стремление разрабатывать эффективные методы решения как можно более широких классов задач. Однако чем более общей является задача, тем менее эффективны алгоритмы для неё. Поэтому важно понимать, какую цену мы платим за усложнение решаемой задачи. Иначе говоря, важно уметь анализировать сложность вычислительных задач. Этим занимается теория сложности алгоритмов, современная быстро развивающаяся область, знание которой совершенно необходимо тем, кто интересуется теоретической информатикой.

Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область на стыке математики и информатики содержит как великие нерешенные задачи (например, P=?=NP, за решение которой, кстати, объявлен приз в $1,000,000), так и красивые теоремы и понятия (например, интерактивные протоколы). Первая часть курса будет посвящена базовым понятиям, конструкциям, фактам в этой области: вероятностные алгоритмы, вычисления с оракулами, полиномиальная иерархия, булевы схемы, интерактивные протоколы.

Сложность вычислительной задачи препятствует её эффективному решению. Однако зачастую именно это требуется, когда речь идёт о невозможности взлома криптографических протоколов. Вторая часть курса будет посвящена рассказу о криптографических понятиях (односторонних функциях, криптосистемах и т.д.) на языке теории сложности (на котором они, собственно, и определяются).

Материалы:

Условия сдачи курса и вопросы к экзамену.

Date and time Class|Name Venue|short Materials
14 February
18:30–19:50
Лекция, Lecture ПОМИ РАН video
21 February
18:30–20:05
Лекция, Lecture ПОМИ РАН video
28 February
18:30–20:05
Лекция, Lecture ПОМИ РАН video
06 March
18:30–20:05
Лекция, Lecture ПОМИ РАН video
13 March
18:30–20:05
Лекция, Lecture ПОМИ РАН video
20 March
18:30–20:05
Лекция, Lecture ПОМИ РАН video
27 March
18:30–20:05
Лекция, Lecture ПОМИ РАН video
03 April
18:30–20:05
Лекция, Lecture ПОМИ РАН video
10 April
18:30–20:05
Лекция, Lecture ПОМИ РАН video
17 April
18:30–20:05
Лекция, Lecture ПОМИ РАН video
24 April
18:30–20:05
Лекция, Lecture ПОМИ РАН video