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

📊 Традиционно осенью я читаю продвинутый спецкурс для узкой аудитории по тематике, связанной со сложностью вычислений. На что вам было бы интересно ходить? (Можно выбрать несколько вариантов). Вероятностно проверяемые доказательства (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 людей проголосовали

Поскольку 3 желающих так и не набралось, занятия 2 мая не будет. Остаётся одно занятие 16-го, принимаются пожелания по его теме и сроку к/р.

Голосование давайте закончим 30 апреля в 19 часов. Если к тому времени не наберётся трёх желающих, то занятия не будет.

📊 Придёте ли вы на занятие 2 мая, если оно будет? (Занятие состоится, если будет хотя бы трое желающих, тема не войдёт в к/р, но войдёт в домашку). Да [2] ‎├ Darya Lapa ‎└ Yan Slabodich Нет [7] ‎├ Artem Sapozhnikov ‎├ Viacheslav Ivanov ‎├ Aleksandr Grishutin ‎├ Илья Курузов ‎├ Дмитрий Невструев ‎├ Ruslan Ishmukhametov ‎└ Victoria Anisimova Не знаю [3] ‎├ Egor ‎├ Максим ‎└ Nikita Mikhaylov 👥 10-15 людей проголосовали

Сегодня топологии всё ещё не будет, сложность будет примерно до 3 часов. В следующий раз, 25 апреля, не будет сложности и, вероятно, будет две топологии.

А Глеб Гусев заболел, так что топологии, наоборот, не будет. Возможно, моя лекция будет подольше - обсудим, как я подойду.

Сегодня занятия по допглавам начнутся с опозданием, ориентировочно в 12:30. Продолжим изучать рациональные интерактивные доказательства.

Этим летом в Новосибирске проходит интересная летняя школа по компьютерным наукам, в частности, будет много курсов про применения логических методов в программировании. На сайте http://cssr.nsu.ru/school/ru подробно написано, что за курсы и преподаватели. Часть курсов на английском, часть на русском. Большая часть материала будет понятна студентам, окончившим первый курс. Организаторы обещают тревел-гранты на поездку. Если пересечётся с экзаменами, договоримся о более поздней, либо досрочной сдаче (при достаточных академических успехах). После школы ещё будет научная конференция CSR, уже полностью на английском и в целом сложнее. Но зато будут учёные с мировым именем. В общем, кому интересно - подавайтесь и держите нас в курсе.

Спецкурса по топологии сегодня не будет в связи с болезнью преподавателя, но допглав будет только одна пара, т.к. у меня ещё одна замена.

https://t.me/joinchat/DZlFTUmeY2z_4jOgSymv0g - чат по спецкурсу по теории игр

Уточнение: курс дополнительных глав будет обязательным для кафедры ДМ, факультативным для всех остальных. Пропуска в Яндекс своим чередом получат студенты кафедр ДМ и АД.

Спасибо всем, кто ходил на курс! Продолжение будет проходить по четвергам с 12 до 14 в ШАДе (м. Парк Культуры) Начало 7 февраля, будет сразу 2 пары (до 16). Если кто хочет ходить, но не имеет пропуска в Яндекс, сообщите. Вопрос о пересдачах решим в частном порядке, благо их немного. Канал и чат переориентируются на новый курс.

Завтра экзамен с 10 часов в 123 ГК. В табличке появилось рекомендованное время прихода завтра. Если останутся непроверенные задачи из дорешки, приходите к началу (10 часов) и досдавайте.