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

Нужно сейчас заявить спецкурс на следующий год. Традиционно я читаю спецкурс на одну из продвинутых тем курса сложности вычислений. Раньше было только осенью, но последние 4 года по просьбам слушателей продолжаю и весной. В связи с тем, что студенты ПМИ.Инф уже проходили курс криптографии, а он обязательный для кафедры ДМ, он будет заменён на более продвинутый курс криптографии, так что один курс точно будет. Не уверен, что смогу совмещать с другим курсом, но при наличии интереса постараюсь. Вот несколько возможных тем, в комментариях будут примерные программы, а также неанонимный консультативный опрос (т.е. будет выбран не обязательно вариант, набравший большинство голосов). Можно выбирать до утра 1 июня. Дополнительные главы криптографии - обязательный для ПМИ.Инф+ДМ, факультативный для всех. Рекомендуется проходить после основного курса, но в принципе можно и параллельно. Примерные темы: конфиденциальные дву- и многосторонние вычисления, разделение секрета, византийское соглашение, электронные выборы, электронная наличность, блокчейн, неинтерактивные доказательства с нулевым разглашением, снарки и старки, обфускация. Возможны вариации. Вероятностно проверяемые доказательства - это то, что мы недавно проходили, так что подробное представление, думаю, не нужно. В этом курсе доказывается "большая" PCP-теорема и её вариации вроде трёхбитной теоремы Хостада, а также изучаются сложности приближённого решения разных конкретных задач. Предыдущий раз курс читался 2 года назад. Псевдослучайность и дерандомизация - в этом курсе изучаются разные псевдослучайные конструкции (экспандеры, экстракторы, коды с декодированием списком, генераторы псевдослучайных чисел и др.), которые в конечном итоге могут привести к доказательству BPP=P. Этот курс читался 3 года назад и обычно вызывает интерес, вполне могу прочесть снова. Вычислительная сложность задач поиска - изучается сложность задач поиска, прежде всего тех, где ответ точно есть (и потому вопрос о существовании ответа тривиален). Есть растущий зоопарк классов, а также много приложений к разного рода экономическим моделям на базе теорем о неподвижных точках. Рациональные интерактивные доказательства - изучается делегирование вычислений, при котором мощный сервер выполняет вычисления за деньги, максимизируя вознаграждение. Нужно так выстроить стимулы, чтобы при этом сервер выявил правильный ответ. Курс читался в прошлом году, так что повторю только при высоком интересе. Можно также предлагать свои варианты, если мне один из них приглянётся, то можно будет изучить что-нибудь вместе. Имеющиеся программы курсов и опрос в комментариях.

Сделал табличку для выбора даты кр, должно редактироваться по ссылке: https://docs.google.com/spreadsheets/d/1PVLo1Tmm_hnT6S1KHpmMz3607Mk8BuOWUijOUyTMJWU/edit?usp=sharing

Сделал табличку для выбора даты кр, должно редактироваться по ссылке: https://docs.google.com/spreadsheets/d/1PVLo1Tmm_hnT6S1KHpmMz3607Mk8BuOWUijOUyTMJWU/edit?usp=sharing

Мы подготовили второе домашнее задание. Поставил срок сдачи следующий понедельник, дальше вряд ли сможем продлить.

Предварительно расписание на оставшиеся занятия: Завтра, 7 мая, будет только лекция про рациональные интерактивные доказательства, без семинара. Лекцию постараюсь начать вовремя, но могу задержаться из-за важного созвона. 14 мая будет 2 семинара: во время лекции и во время обычного семинара.

Также сделал папку с материалами: https://www.dropbox.com/scl/fo/9wslv92i9vqbg1cdvqr54/AGAfcvXxt7B1wdrqryhB_uE?rlkey=775k6hbqsg4k0nv9fluf6fwqt&dl=0 Там два последних файла и последняя версия компл-бука. Что ещё нужно туда положить?

Также есть возможность выполнить индивидуальный проект. На этом курсе он не блокирующий, но если вам интереснее разобраться в какой-то теме вместо решения задач, то это хороший вариант. Занимать номера проектов можно тут, должно быть открыто для редактирования: https://docs.google.com/spreadsheets/d/16YrAMmJgOBkFG19q5RLJr0SQz7AdTH6h7KZ4SGt7fwU/edit?usp=sharing

Как обещал вчера, сделал индивидуальные домашние задания. Пока что про IP, AM и ZKP. Про PCP и MIP будет ещё второе. Срок сдачи - после майских.

Сегодня, 16 апреля, лекция начнётся по расписанию (обсудим класс MIP и теорему MIP=NEXP), а вот семинара не будет - Иван заболел.

Сегодня, 2 апреля, лекции не будет - я болею. Семинар будет по расписанию.

Завтра, 19 марта, лекция будет. Начнём вовремя, приходите!

Завтра, 26 февраля, семинар состоится онлайн, ссылка появится в чате перед началом семинара. Настройка трансляции через проектор в аудитории остаётся на усмотрение слушателей.

#дневниклекций В прошлый раз обсуждали подробно про АМ-классы: - Напоминание определений: классы МА, АМ, более высокие вроде АМА и МАМ и общий AM[k] - Формулировка теоремы об ускорении: AM[const]=AM, AM[2k(n)]=AM[k(n)] - Схема доказательства первой части:…

#дневниклекций Попробую в этом семестре записывать, что прошли на лекциях. Если что-то важное забываю, дополняйте. В прошлый раз была начальная лекция про интерактивные доказательства. Примерное содержание: - Доказательство как текст и как процесс. Пример…

Объявление: завтра семинара не будет, только лекция. Вероятно, 19 марта не будет лекции, а будет 2 семинара.

#дневниклекций Попробую в этом семестре записывать, что прошли на лекциях. Если что-то важное забываю, дополняйте. В прошлый раз была начальная лекция про интерактивные доказательства. Примерное содержание: - Доказательство как текст и как процесс. Пример с разноцветными носками. - Общее определение интерактивной системы доказательств с прувером и верификатором. Класс IP. Тривиальные вложения NP и BPP в IP, протокол для задачи GNI (о неизоморфизме графов). - Независимость класса от точных порогов ошибки (через амплификацию). Варианты с совпадением порогов для строгих неравенств и с идеальной полнотой должны были разбираться на семинаре. - Вложение IP в PSPACE через вычисление оптимальных ответов прувера на полиномиальной памяти. (Доказали для упрощённого случая). - Вариант с общими случайными битами. Классы MA и AM. Вложение МА в АМ. Утверждения про многраундовый АМ (с константным числом раундов - так же, как с двумя, с полиномиальным - как IP, пока без доказательств)

Сложность вычислений ФПМИ pinned «Служебный пост с информацией на весну 2026 для курсов «Сложность вычислений: дополнительные главы» в бакалавриате ДМ и «Дополнительные главы теории сложности» в магистратуре (будет дополняться). Расписание: Лекции - Даниил Мусатов, четверг, 10:45, 424 Арктика…»

Служебный пост с информацией на весну 2026 для курсов «Сложность вычислений: дополнительные главы» в бакалавриате ДМ и «Дополнительные главы теории сложности» в магистратуре (будет дополняться). Расписание: Лекции - Даниил Мусатов, четверг, 10:45, 424 Арктика Семинары - Иван Смирнов, четверг, 12:20, 424 Арктика Ссылки: Этот канал (с новостями и материалами): https://t.me/diht_complexity Чат для обсуждений и вопросов: https://t.me/+WYa2jWEwL-VkNWUy Папка с материалами: https://www.dropbox.com/scl/fo/9wslv92i9vqbg1cdvqr54/AGAfcvXxt7B1wdrqryhB_uE?rlkey=775k6hbqsg4k0nv9fluf6fwqt&dl=0 Табличка для оценок: https://docs.google.com/spreadsheets/d/16YrAMmJgOBkFG19q5RLJr0SQz7AdTH6h7KZ4SGt7fwU/edit?usp=sharing

Традиционно весной этот канал используется для курса дополнительных глав сложности вычислений. Если вы ходите на курс обычной сложности для ПМИ.Инф или по выбору, то подписывайтесь на канал https://t.me/compl_pmi_inf

Первая пересдача по осеннему курсу сложности будет в эту пятницу, 13 февраля, с 10 до 14 часов, аудитория 204а ГК. Пишите в личку @musatych, придёте ли вы, чтобы мы планировали число принимающих и время захода. Ещё одна пересдача точно будет на первой неделе марта, до этого - не факт.