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

Поздравляю с днём знаний! В этом семестре канал будет использоваться для очередного курса сложности вычислений у третьего курса ПМИ (кроме потока информатики). При желании можно остаться в канале и чате и помогать новым студентам. А для тех, кто закончил курс и продолжит изучать различные сложностные курсы, вот ссылки на соответствующие чаты: - Криптография (обязательна в бакалавриате ДМ): канал https://t.me/fpmi_crypto (новый) и чат https://t.me/+RGQjj4R4Y4VcuJor Лекции по вторникам с 5 сентября в 10:45, семинары по понедельникам в 13:55, дата начала уточняется - мой спецкурс "Псевдослучайность и дерандомизация" (описание см. выше) - чат https://t.me/+TFWCy-HlhfwGqZSe занятия по четвергам в 15:30 с 7 сентября - спецкурс Данилы Дёмина при моём участии "Изоморфизм графов" - чат https://t.me/+GiURflv_rt1lZGM6 На нём постараемся разобраться в алгоритме Бабаи, решающем задачу об изоморфизме графов за квазиполиномиальное время. Занятия по четвергам в 17:05, дата начала уточняется - спецсеминар под моим руководством "Игры и алгоритмы" - чат https://t.me/+VmejbREAJeE1YTRi Там в основном мои ученики рассказывают про свои исследования, иногда я тоже что-то рассказываю. Занятия по четвергам в 13:55, дата начала уточняется

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

Давайте начало на 15:30 перенесём, предыдущий экзамен затягивается - не будет свободных мест в аудитории.

К/р для тех, кто не писал 14-го, будет 22 июня в 15:00, аудитория 123 ГК. Возможно начало с опозданием, если затянется экзамен по логике, но вроде бы должны уложиться.

Сегодня, 4 мая, лекции тоже не будет - я в отъезде, провести онлайн нет возможности. 11 мая сделаем последнюю лекцию - думаю, доразберёмся с MIP=NEXP. Про рациональные доказательства можно сделать дополнительную лекцию 18-го, если будет запрос. В к/р этой темы не будет, но в домашку одну задачу включу.

Завтра, 27 апреля, лекции не будет - я уеду на конференцию в Сочи

Сегодня постараюсь выложить первую домашку. Пока что сделал табличку для оценок, оттуда же буду брать данные для индивидуальных вариантов. Там сейчас только бакалавриат кафедры ДМ. Если вы из магистратуры или с другой кафедры и сдаёте курс, напишите мне имя и номер группы, чтобы я добавил. Ссылка: https://docs.google.com/spreadsheets/d/12ApZWYJQSgR4HAWgosn4kFy8u7V0wZqHZbNNYZ52b9M/edit?usp=sharing

Завтра, 23 марта, занятия не будет - я уеду на всерос по экономике

Приглашаю поучаствовать в математическом квесте "Интеграл по городу", который пройдёт в Майкопе (Адыгея) и онлайн 11-12 марта. Суть квеста - поиск различных объектов в городе или в интернет-источниках (панорамах, фотосайтах и т.д.) и решение математических задач, данные для которых нужно найти на этих объектах. Задачи не используют высшую математику, так что доступны старшим школьникам - зовите друзей-нематематиков или младших братьев и сестёр (а половина заданий не требуют математики вообще). 11 марта будут короткие категории "Тьюринг" онлайн и "Евклид" в городе, начало в 15:30, окончание в 18:00. 12 марта - длинные категории "Колмогоров" онлайн и "Лобачевский" в городе, начало в 10:00, окончание в 18:30. Можно участвовать командами от 1 до 6 человек. Подробности и регистрация по ссылке https://www.runcity.org/ru/events/maykop2023/ Участие стоит 961 рубль с команды или бесплатно по промокоду mipt. Если кто-то захочет добраться до Майкопа и понадобится помощь, пишите в личку.

Закреплённый пост со служебной информацией, весна 2023 Расписание: Лекции - четверг, 10:45-13:00, 113 ГК. Ресурсы для студентов: https://t.me/diht_complexity - этот канал https://t.me/+_zvpm0_mwVwwZThi - чат к каналу https://www.dropbox.com/sh/r46j99n2ujdfjhm/AADMtzp7AVXyX9oZWnZOGoNja?dl=0 - папка с материалами

Сегодня будет вводная лекция, по крайней мере первую пару из полутора. На ней я неформально расскажу про основные темы курса, в том числе опишу решения таких задач: 1) Как убедить недоверчивого дальтоника, что в остальном одинаковые предметы имеют разный цвет. 2) Как гениальному археологу доказать назойливой прессе открытие древнего заклинания, не разгласив его. 3) Как записать математическое доказательство, чтобы для его проверки было достаточно прочесть лишь несколько битов, и при чём здесь задачи аппроксимации. 4) Как заставить жадного владельца облачного сервера проводить именно те вычисления, которые нужны клиенту. Приходите, лекция уже скоро!

Кто не сдавал экзамен, но хочет сдать, напишите мне в личку, выберем дату. Особенно если хотите сдавать в первой половине февраля.

В новом семестре этот канал будет использоваться для курса дополнительных глав сложности вычислений. Он будет проходить по четвергам с 10:45 до 13:05 (полторы пары) в 113 ГК. Этот курс обязательный для кафедры ДМ и факультативный для всех остальных. В том числе он входит в пул курсов по выбору на 5-м курсе магистратуры бывшего фупма, так что название канала актуализирую. Программа нового курса и прочие подробности будут чуть позже.

Комментарий по датам экзамена: - предварительные даты есть в таблице с результатами. - можно без ограничений меняться датами друг с другом. - если ваша группа в табличке отличается от "официальной", то можно перенести на тот день, когда сдаёт "официальная" - на 23-е получается много сдающих и мало экзаменаторов. Так что с 23-го можно переносить в любом направлении, первые 15 заявок будут удовлетворены, дальше не факт. - если уже знаете, что вообще не сможете прийти по любой причине, напишите, пожалуйста - если хотите перенести или есть особые обстоятельства, не покрытые пунктами выше, пишите мне в личку Хотелось бы финализировать список сдающих 21-го завтра (20-го) днём, тогда я расставлю по времени согласно текущему рейтингу (чем он выше, тем раньше заход). Потом тоже можно будет ещё поменяться временем или перенести по уважительной причине.