Пока домашки постепенно проверяются, предлагаю обсудить следующий семестр. Традиционно осенью я читаю продвинутый спецкурс по сложности вычислений для небольшой аудитории. Предлагаю по ссылке https://doodle.com/poll/duvk22hfs36e3xke записаться желающим ходить и выбрать тему. Можно выбирать несколько тем или отмечать вариант "наполовину", кликнув на него два раза. Варианты курсов (если нужны подробности, пишите в чате):
1) Вероятностно проверяемые доказательства. Полное доказательство PCP-теоремы (для этого нужно будет изучить теорию экспандеров), связь с аппроксимацией различных задач оптимизации, в том числе Unique Game Conjecture.
2) Псевдослучайность и дерандомизация. Различные псевдослучайные объекты (в том числе те же экспандеры), обоснование гипотезы BPP=P (генератор Нисана-Вигдерсона, Hardness vs Randomness). Этот курс я читал последние 2 года, так что он будет выбран только при большом перевесе.
3) Вычислительные задачи поиска. Подробно про классы задач поиска (PPAD и другие), связь с теорией игр и экономическими моделями.
4) Рациональные интерактивные доказательства. Подробно про системы доказательств с прувером или пруверами, максимизирующими награду. Доказательство теорем о равенстве соответствующих классов.