Задачи к 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 недели с небольшим.

По поводу проектов: ряд номеров (в настоящий момент 66, 68, 72, 82, 86) выбраны с превышением квоты на число студентов на проект, при этом нет никаких явно указанных спецификаций. Если у вас один из этих номеров, то нужно сделать одно из двух: либо договориться, кто из троих выберет другой номер, либо написать явно спецификации, так чтобы подтемы были разными. Лист выбора проектов пока что открыт на редактирование, так что можно ещё выбрать проект, но тоже без превышения квоты, либо с соблюдением правил такого превышения. В конце недели выбор проектов закроется, если останутся превышения квот без комментариев, то будут проанализированы по истории изменений, и последняя по времени запись аннулирована.

Задачи к 10—12 семинарам