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

Листочки последних семинаров

Третья к/р пройдёт 20.12 в 13:55 в Б.Хим. На ней будут даны 4 задачи по 10 баллов. Можно пропустить по любой причине, тогда задачи перейдут в дорешку по 8 баллов. Если же вы пишете к/р, то дорешка будет по 5 баллов, как обычно. Прошу выбрать, придёте ли вы на к/р, на третьем листе в табличке: https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing Если будет много желающих писать, которые не могут прийти, что-нибудь придумаем. Варианты сделаю на тех, кто придёт, плюс немного запасных Темы задач (формальный тренировочный вариант постараюсь выложить завтра утром): * Вариации P/poly (конкретные полиномы и т.д.) * Классификация в NC-иерархии * Несложная задача про вероятностные классы (модификация языка из одного класса лежит в том же ли другом заданном классе) * Дерандомизация (методом УМО или k-независимости на выбор) Будет ещё 2 задачи только на дом: * Вероятностные классы с неравномерной монеткой * NP-трудные задачи подсчёта (не было в курсе, нужно разобраться самостоятельно)

Рассадка на сегодня. Актовый зал в ЛК, по 7 мест с каждой стороны от прохода. Приходите к 13:55, до того же времени принимаются сообщения об уважительном пропуске.

https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit#gid=0 - в табличке открыты поля до конца семестра. В том числе в столбце CM есть предварительная оценка за семестр. Формула может немного поменяться в любую сторону, но вряд ли сильно. Сейчас она такая (нелинейная): 1 балл итоговой оценки ставится за 36 баллов за к/р+д/з, 2 балла за 80, 3 балла за 132, 4 балла за 192, в промежутках линейная интерполяция. К этому будет добавлено число баллов за проект (0-12), поделённое на 5, и число баллов за экзамен (0-10), поделённое на 2. Потом всё это округлится вниз до целого и это будет итоговая оценка (при условии, что экзамен хотя бы на 3). Напоминаю, что завтра будет контрольная - 13:55, Актовый зал. Если пропускаете по уважительной причине, сообщите до начала контрольной.

❗️В следующую среду, 29 ноября, в 13:55, вместо лекции будет вторая контрольная работа. Место - Актовый зал, как и у первой. Темы задач: * Классификация в полиномиальной иерархии * Полнота на втором уровне полиномиальной иерархии * Полнота в PSPACE * Доказательство принадлежности к L * Принадлежность и полнота в NL * Диагонализация * (только д/з) Случайные оракулы Формальный тренировочный вариант подготовим в ближайшее время. По третьей к/р, вероятнее всего, сделаем выбор: либо написать на зачётной неделе с оценкой в 10 баллов на к/р и 5 в дорешке, либо решать дома с оценкой в 8 баллов. (Т.е. любая причина пропуска будет уважительной).

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

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

Я тут ещё немного дописал и перекомпилировал 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 МСК. Обратите внимание на необычное время!!! 📌 Ссылка на зум. Чтобы получать наши анонсы, зарегистрируйтесь в боте (инструкция). #открытые_лекции #анонс