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

Я тут ещё немного дописал и перекомпилировал compl-book, сделал 3 варианта по размеру шрифта: 10pt, 11pt и 12pt. Давайте я их сейчас выложу, а вы посмотрите, как вам лучше читается. Я тогда дальнейшие версии буду в выбранном формате выкладывать.

📢 Лекция Льва Суханова в это воскресенье, 22 октября, в 17:00 Лев Суханов - выпускник матфака ВШЭ и исследователь в PSE, Ethereum Foundation. Он расскажет про очень важную область криптографии, в которой он работает - быстрые проверки доказательств. 🔍 Верифицируемые вычисления при помощи sumcheck-протокола 📝 Давайте рассмотрим следующую ситуацию: Алиса посчитала на известных публичных данных X функцию f(X), и хочет убедить Боба в том, что ответ, который она говорит - правильный. Боб, однако, ограничен в вычислительных ресурсах, и не хочет повторять всё вычисление Алисы. Выясняется, что (при условии что Боб допускает небольшую вероятность ошибки, скажем $2^{-128}$), такую задачу можно решить намного быстрее. Такую постановку вопроса называют "снарк" (succinct non-interactive arguments of knowledge). Я расскажу про довольно старый протокол из 90х - sumcheck (проверка суммы), в последние год-два получивший второе дыхание в контексте делегированных вычислений и блокчейна, и построенный на этом аргументе протокол GKR (Голдвассер-Калаи-Ротблюма). Пререквизиты: знать что такое конечное поле и уметь раскрывать скобки, если дойдём до приложений то ещё понадобится (наверное) знать что такое хэш ⏰ Начало в 17:00 МСК. Обратите внимание на необычное время!!! 📌 Ссылка на зум. Чтобы получать наши анонсы, зарегистрируйтесь в боте (инструкция). #открытые_лекции #анонс

Завтра в 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, дата начала уточняется