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

Закреплённый пост со служебной информацией:

Расписание:
Лекции - среда, 13:55, 202 НК.
Семинары и семинаристы:
020 - Голованов, чт, 10:45, 424 ГК
021 - Якунин, чт, 12:20, 204 УПМ
022 - Александров, вт, 10:45, 530 ГК
023 - Васильчишин, вт, 09:00, 409 ГК
024 - Степанов, чт, 15:30, 528 ГК
025 - Мусатов, чт, 15:30, 302 КПМ
026 - Якунин, чт, 13:35, 204 УПМ
027 - Александров, вт, 12:20, 530 ГК
028 - Смирнов, вт, 13:55, 418 ГК
029 - Букреев, чт, 10:45, 411 ГК

Ресурсы для студентов:
https://t.me/diht_complexity - этот канал
https://t.me/+_zvpm0_mwVwwZThi - чат к каналу
https://www.dropbox.com/sh/78k1vny4gy9bs9y/AADvsSaKxRWTtrrFIeCXgh7na?dl=0 - папка с материалами
https://docs.google.com/spreadsheets/d/1tU8AaboXrUVQmrWKz92vsEah1xvQ8dSC_fy4aNkSb0A/edit?usp=sharing - табличка с оценками за контрольные и для выбора темы проекта

А студентов кафедры ДМ, перешедших на 4-й курс, приглашаю в чат курса по криптографии: https://t.me/+RGQjj4R4Y4VcuJor

По итогам голосования и сопутствующих соображений решил попробовать прочесть спецкурс по задачам поиска. Кто хочет ходить, присоединяйтесь к чату https://t.me/+BsCLVBEcojw1NmYy, там и время обсудим.

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

Сделал небольшую дорешку по первому д/з. Задачи по 5 баллов, суммируется с баллами за ту же задачу на основном д/з, но сумма не больше 8. Принимать можем сегодня и завтра. Экзамен я потихоньку проверяю, в основном будет готово сегодня. Вторая домашка - скорее всего, завтра. Так что выбирать, что дорешивать, придётся немного вслепую.

К сожалению, я сегодня не приду на экзамен, его проведёт Дмитрий Ильинский. Приходите к 10:15 в Б.Хим., там будут разложены варианты условием вниз, в основном на самых левых и самых правых местах во всех рядах, и немного посередине. Потом по команде переворачивайте условие, и будет 2.5 часа на написание. Возможности отвечать на вопросы нет, так что если с условием что-то не так, то исправляйте его по своему усмотрению.

Я обещал майский вариант в качестве тренировочного, а мне никто не напомнил. Выкладываю.

16 июня будет вторая возможность написать контрольную. Аудитория - Б.Хим., там же будет устный экзамен по теории колец и полей, но аудитория большая - поместимся. Начало - в 10:15.

Завтра, 26 мая, с 11 до 14 можно будет написать контрольную по допглавам сложности вычислений. Аудитория - УЛК-2 № 424. Вторая возможная дата - 16 июня.

Наконец готово второе д/з. Срок сдачи пока не ставлю, ориентировочно середина июня (вокруг второй даты к/р).

Я только устно в прошлый раз сказал, а написать забыл: сегодня занятия нет, я на всеросе по экономике.

Готова домашка, варианты индивидуальные. Если вас нет в списке, напишите мне, а вариант берите самый последний. Срок сдачи - 28 апреля.

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

Обнаружил, что в канале нет информации: занятия теперь проходят с 11:15 до 13:15, по-прежнему по четвергам, онлайн:
https://us02web.zoom.us/j/84836554884?pwd=dGp4L0UxR2NES0NyT1NPTEhuT05odz09
Идентификатор конференции: 848 3655 4884
Код доступа: 298433

Постоянная ссылка на доску: https://idroo.com/board-zIonaCWSP2

Материалы по курсу выкладываются тут: https://www.dropbox.com/sh/ze5hrkzdvolb1x7/AABqqsm3SLQPPze7faj-f1L2a?dl=0

Пересдача по первой части курса планируется завтра в 12 в 308 КПМ. С утра ещё пришлю подтверждение.

Завтра, 17 февраля, занятие будет онлайн, одна пара с 10:45 до 12:15. Ссылка прежняя:

https://us02web.zoom.us/j/84836554884?pwd=dGp4L0UxR2NES0NyT1NPTEhuT05odz09
Идентификатор конференции: 848 3655 4884
Код доступа: 298433

Обратите внимание, 17 февраля занятие всё же будет, формат уточним.

В этот четверг, 10 февраля, будет очная пара, начнём изучать интерактивные доказательства. 17 февраля занятий не будет вероятно, всё же будут, формат уточню. Потом возможен переход на дистант, а то свободной аудитории на третью пару не нашлось, а я бы хотел полторы пары читать с учётом пропускаемых дней.

https://www.dropbox.com/sh/ze5hrkzdvolb1x7/AABqqsm3SLQPPze7faj-f1L2a?dl=0 - папка с материалами по курсу "Дополнительных глав" (пока пустая)

Курс "Дополнительных глав" будет проходить по четвергам с 10:45 до 13:00.

На первой лекции 3 февраля я расскажу несколько весёлых историй, вокруг которых будет строиться курс:
- как доказать брату-дальтонику, что он надел носки разного цвета
- как убедить прессу, что ты разгадал древнее волшебное заклинание, не произнося его
- как ободрить приунывшую коллегу, что её судоку решается, не делая подсказок
- как проверить корректность математического доказательства, прочтя в нём всего несколько символов
- как эксплуатировать жадность волшебника, доказывающего теоремы
- и как доказывать теоремы при помощи очной ставки между двумя такими волшебниками

3 февраля будем заниматься в зуме по старой ссылке:
https://us02web.zoom.us/j/84836554884?pwd=dGp4L0UxR2NES0NyT1NPTEhuT05odz09
Идентификатор конференции: 848 3655 4884
Код доступа: 298433

В дальнейшем планируются очные занятия, аудитория уточняется, по записи/трансляции тоже решим.