Объявление о спецкурсе (для уже прошедших курс сложности).

В этом семестре я читаю спецкурс "Рациональные интерактивные доказательства". В нём подробно рассматривается новый раздел на стыке теории сложности вычислений и теории игр – рациональные интерактивные доказательства. Они могут служить для моделирования коммерческих вычислений, когда у заказчика вычислений нет способа проверить истинность результата, но он может выстроить стимулы так, чтобы исполнителю было выгодно выполнить вычисления правильно. Курс будет заточен на теоретические аспекты: мы определим несколько сложностных классов, основанных на этой идее, и докажем соотношения между ними и классическими классами. В частности, выяснится, что за константное число раундов можно решить гораздо больше задач, чем в классических интерактивных доказательствах.

Курс проходит по четвергам в 15:30, 535 ГК. Первое занятие - 11 сентября. Чат курса - https://t.me/+V8LdajB3dUjKbhjM