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

Задачи к 4-му семинару

В следующую среду, 11 октября, вместо лекции в 13:55 будет контрольная работа. Она пройдёт в Актовом зале. Прилагается файл с тренировочным вариантом и правилами к/р. Задачи даны с запасом, отличным результатом будет считаться 4 решённые задачи из 6, хотя могут быть и 1-2 работы со всеми решёнными. Если пропускаете по уважительной причине, пишите мне до начала контрольной.

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

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

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

Закреплённый пост со служебной информацией, осень 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 - табличка с оценками

Предлагаемый список проектов на этот год и правила оценивания. Сроки написаны в файле, будут уточнены после появления расписания сессии.
Записаться на выбранный проект можно в табличке https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing на листе "Проекты" (столбец C и при необходимости D напротив своего имени). Важно: на один проект можно записываться не более чем 2 людям с курса и не более чем 1 человеку из группы. На листе это проверяется. По некоторым темам возможны разные спецификации, тогда укажите свою в столбце D, критерии по повторам будут относится к конкретным спецификациям и проверяться вручную. Если выбираете тему не из файла, впишите номер 0 и название темы.

Задачи к 6-му семинару

Задачи к 7-му семинару

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

📢 Лекция Льва Суханова в это воскресенье, 22 октября, в 17:00

Лев Суханов - выпускник матфака ВШЭ и исследователь в PSE, Ethereum Foundation. Он расскажет про очень важную область криптографии, в которой он работает - быстрые проверки доказательств.

🔍 Верифицируемые вычисления при помощи sumcheck-протокола

📝 Давайте рассмотрим следующую ситуацию: Алиса посчитала на известных публичных данных X функцию f(X), и хочет убедить Боба в том, что ответ, который она говорит - правильный. Боб, однако, ограничен в вычислительных ресурсах, и не хочет повторять всё вычисление Алисы.

Выясняется, что (при условии что Боб допускает небольшую вероятность ошибки, скажем $2^{-128}$), такую задачу можно решить намного быстрее. Такую постановку вопроса называют "снарк" (succinct non-interactive arguments of knowledge).

Я расскажу про довольно старый протокол из 90х - sumcheck (проверка суммы), в последние год-два получивший второе дыхание в контексте делегированных вычислений и блокчейна, и построенный на этом аргументе протокол GKR (Голдвассер-Калаи-Ротблюма).

Пререквизиты: знать что такое конечное поле и уметь раскрывать скобки, если дойдём до приложений то ещё понадобится (наверное) знать что такое хэш

⏰ Начало в 17:00 МСК. Обратите внимание на необычное время!!!

📌 Ссылка на зум. Чтобы получать наши анонсы, зарегистрируйтесь в боте (инструкция).

#открытые_лекции #анонс

Задачи к 8-му семинару

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

Задачи к 9-му семинару

Готова дорешка по первой к/р. В нй задачи по 8 темам - всем, что были в к/р хотя бы у одной группы. Число баллов за задачу написано в файле и в табличке. Срок сдачи поставлен на 22 ноября - через 2 недели с небольшим.