📊 Традиционно осенью я читаю продвинутый спецкурс для узкой аудитории по тематике, связанной со сложностью вычислений. На что вам было бы интересно ходить? (Можно выбрать несколько вариантов).

Вероятностно проверяемые доказательства (PCP-теорема с полным доказательством, unique game conjecture, приближения для конкретных задач) [2]
‎├ Nikita Sveshnikov
‎└ Yan Slabodich

Псевдослучайность и дерандомизация (экспандеры, экстракторы, генераторы псевдослучайных чисел и связи между ними. Почему мы думаем, что BPP=P) [4]
‎├ Yan Slabodich
‎├ Ruslan Ishmukhametov
‎├ Илья Курузов
‎└ Andrei Asanau

Тотальные задачи поиска и теоремы о неподвижных точках (подробно про класс PPAD и прочие, связи с теорией игр, экономическими равновесиями и топологией) [1]
‎└ Matvey Bezlepkin

Рациональные интерактивные доказательства (обзор моделей, в том числе с несколькими Мерлинами и различными способами взаимодействия между ними) [2]
‎├ Yan Slabodich
‎└ Matvey Bezlepkin

👥 6 людей проголосовали