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

Завтра в 17:00 будет открытая онлайн-лекция по одной из "горячих" тем современной сложности вычислений - верификации вычислений с использованием небольших вычислительных ресурсов. Анонс и ссылка на зум в посте ниже. Присоединяйтесь!

Закреплённый пост со служебной информацией, осень 2023 Расписание: Лекции - среда, 13:55-15:20, 115 КПМ (Мусатов Д.В,) Семинары по группам: 122 - вторник, 15:30-16:55, 424 Арктика (Васильчишин С.М.) 123 - среда, 10:45-12:10, 507а ГК (Ковалев К.А.) 124 - вторник, 10:45-12:10, 432 ГК (Коротков М.С.) 125 - среда, 9:00-10:25, 424 Арктика (Киселёв Ф.А.) 126 - понедельник, 15:30-16:55, 532 ГК (Степанов И.Д.) 127 - среда, 12:20-13:45, 512 ГК (Оверчук А.Д.) 128 - понедельник, 15:30-16:55, 532 ГК (Степанов И.Д.) 129 - вторник, 13:55-15:20, 426 ГК (Смирнов И.Н.) 151 - среда, 9:00-10:25, 514 ГК (Оверчук А.Д.) 152 - четверг, 12:20-13:45, 522 ГК (Шиманогов И.Н.) Ресурсы для студентов: https://t.me/diht_complexity - этот канал https://t.me/+_zvpm0_mwVwwZThi - чат к каналу https://www.dropbox.com/sh/6u1h2glyhucbbeg/AADLzweWSsROxmSJw7HnOXnVa?dl=0 - папка с материалами https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing - табличка с оценками

Рассадка на сегодня. Напоминаю, это Актовый зал ЛК. Места нумеруются слева направо, если смотреть на доску. Места с 1 до 7 слева от прохода, с 8 до 14 справа.

Организационные моменты по завтрашней контрольной: * Контрольная будет в 13:55 в Актовом зале, рассадка будет готова утром. Продолжительность 1 час 20 минут, так что не опаздывайте к началу. * Проверьте, что вы есть в табличке в нужной группе: https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing. Если нет, то пишите, исправлю * Если не можете прийти по уважительной причине, пишите до начала контрольной, лучше не впритык, чтобы мы не печатали лишних вариантов. Тогда можно будет дорешивать задачи исходя из 8 баллов за задачу, а не из 5 * Вам будет дано 2 подписанных листа: один с условиями задач и один пустой. Писать можно на обоих. Если понадобятся дополнительные листы, их можно будет взять у проводящих. * Завтра вечером появится список проектов и форма для их выбора. Надеюсь, список студентов к тому времени устаканится.

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

Выкладываю листочки с задачами прошедших семинаров

Сегодня начинается спецкурс про изоморфизм графов, (чт, 17:05, 302 КПМ). Там Данила Дёмин будет рассказывать алгоритм Ласло Бабаи решения этой задачи за квазиполиномиальное время. Если планируете ходить, вступайте в чат https://t.me/+GiURflv_rt1lZGM6

Поздравляю с днём знаний! В этом семестре канал будет использоваться для очередного курса сложности вычислений у третьего курса ПМИ (кроме потока информатики). При желании можно остаться в канале и чате и помогать новым студентам. А для тех, кто закончил курс и продолжит изучать различные сложностные курсы, вот ссылки на соответствующие чаты: - Криптография (обязательна в бакалавриате ДМ): канал 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 перенесём, предыдущий экзамен затягивается - не будет свободных мест в аудитории.