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