Сложность вычислений ФПМИ

Внимание, есть возможность поехать на летнюю школу по сложности вычислений в Сириусе, с очень сильными преподавателями из Санкт-Петербурга. Все расходы оплачивают. Основной минус - дедлайн по подаче уже в воскресенье, 4 июля, и нужно решить несколько задач. Ещё там нужна рекомендация, скорее всего я смогу её написать, но сообщите как можно быстрее, если она нужна.

Список курсов:

Схемная сложность булевых функций (Александр Куликов)
Высокоточные оценки сложности (Иван Михайлин)
Сложность доказательств (Дмитрий Соколов)
Формульная сложность и гипотеза KRW (Александр Смаль)

Подача заявок тут: https://siriusmathcenter.ru/program/005s

От себя добавлю, что в своё время подобная школа от тех же организаторов сильно помогла моему развитию как преподавателя и исследователя.

Кто хочет писать контрольную по допглавам, заходите в ближайшее время сюда: https://us02web.zoom.us/j/85031883772?pwd=OERNZU10c2NXekZuYmcwNW12M2lmQT09 Она с 17 часов на 2.5 часа.

Большинство участников опроса высказались за "Псевдослучайность и дерандомизацию". Так и сделаем. По этому курсу уже есть чат, так что присоединяйтесь, кто хочет ходить: https://t.me/joinchat/TFWCy-HlhfwGqZSe Скорее всего, занятия будут в четверг вечером, но в любом случае согласованы с расписанием базовых предметов на кафедре ДМ.

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

С 28 июня по 4 июля в Сириусе пройдёт очень интересная летняя школа "Современные задачи прикладной комбинаторики". Требования на входе:
* знакомство с основами машинного обучения, теорией оптимизации, математической статистикой и теорией графов
* владение навыками программирования на языках высокого уровня
Сама программа включает в себя такие разделы, как:
* теория случайных графов;
* геометрические графы;
* задачи комбинаторной оптимизации;
* методы оценки хроматических чисел графов;
* теоретико-числовые алгоритмы и оптимизированные меры частотности в языке.
Школа бесплатная, но отбор по конкурсу. Конкурсные задачи и другие подробности тут: https://sochisirius.ru/obuchenie/graduates/smena936/4522

https://drive.google.com/file/d/1N2vO4G0EzkfefxyK1Obctwi-1QF10lyQ/view?usp=sharing - видеозапись последней лекции

Презентация с последней лекции с заметками

Презентация к сегодняшней лекции

Готова вторая домашка. Сроком давайте пока считать 24 мая - понедельник после зачётной недели. Вариантов в этот раз 9, отмечайте в том же файле: https://docs.google.com/spreadsheets/d/1YK97-menJKBBg5L0u_gZ296DrQAMvlv5a7sdsQbtcqE/edit?usp=sharing - путём комментария, я буду переносить. Каждый вариант выбирайте не больше 6 раз. Также я выработал гарантированные пороги на разные оценки, они написаны в файле с домашкой и внесены в табличку.

6 мая я прочесть лекцию не смогу, так что останется одна лекция 13 мая. Учитывая близкие результаты в опросе, она будет про задачи поиска. Также я постараюсь в ближайшие дни подготовить вторую домашку. Первая постепенно проверяется.

https://drive.google.com/file/d/1cWiObqctia5O4k1GGd7KUbPmeyd52Cdi/view?usp=sharing - видеозапись лекции про рациональные доказательства

Доска с лекции про рациональные доказательства

https://drive.google.com/file/d/170MVAZiWBci2HuJ_r2EgnnhqlFgduOjt/view?usp=sharing - видеозапись с лекции 22 апреля

Доска со всех лекций про PCP

Пожалуй, можно закрыть опрос. Сделаем 2 лекции по рациональным доказательствам (если только 6 мая не отменят) и 1 про задачи поиска.

https://drive.google.com/file/d/1Q4k5pIybDUGR892XWi4_pSmQ0i4jpNEv/view?usp=sharing - видеозапись лекции 15 апреля

Доска с последних трёх лекций

Доска с последних двух лекций

https://drive.google.com/file/d/19bnKnTam73KBpe0rtqO5y9J_T745T7qx/view?usp=sharing - видеозапись последней лекции