Внезапно от меня попросили названия спецкурсов на следующий год. Традиционно осенью я читаю продвинутый спецкурс по сложности вычислений. Есть несколько возможных тем. В чате я сейчас сделаю неанонимный опрос, а тут подробно напишу о содержании в разных вариантах.
* Вероятностно проверяемые доказательства - основы теории экспандеров, полное доказательство PCP-теоремы и рассмотрение сложности приближения в конкретных задачах, роль Unique Game Conjecture
* Псевдослучайность и дерандомизация - тоже основы теории экспандеров, генераторы псевдослучайных чисел, методы дерандомизации, теорема Рейнгольда (детерминированная проверка достижимости в графе на лог. памяти), почему мы верим, что P=BPP, и почему пока что не получилось этого доказать.
* Сложность задач поиска - подробное рассмотрение классов PPA, PPAD и других, доказательство полноты задач о неподвижных точках в PPAD, классификация некоторых других задач
* Рациональные интерактивные доказательства - доказательство теорем о классификации разных классов интерактивных доказательств. Такой курс был в прошлом году, так что будет повторён, только если к нему будет повышенный интерес