Напоминаю, что до 11:00 завтра нужно выбрать, хотите ли вы решать задачи из 3-й к/р в аудитории или дома. Можно менять свой выбор, если передумали. Сама контрольная будет в 13:55 в 202 НК. Параллельно будет устный приём задач по логике, надеюсь, он не помешает.

Это программа экзамена этого года (а также зачёта у магистров с потока блокчейн). Подробные правила приёма экзамена и выставления оценки за него внутри файла.
(Обновлено 18.12 в 11:12 - добавлена и затем исправлена точная формула расчёта итоговой оценки).

Также выкладываю последнюю версию своей книги. Для нашего курса релевантны первые 10 глав и немножко 11-я. Местами текст не дописан, но для подготовки к экзамену должно хватить. Если найдёте вопрос из программы, который совсем не освещён, напишите, постараюсь быстро добавить.

Третья контрольная проверена, дорешка тоже составлена, прикладываю. Экзамены будут уже на следующей неделе, так что я поставил срок сдачи 15:00 накануне экзамена, чтобы успеть проверить. Но в крайнем случае допринимаем устно перед выдачей билета.

Расписание экзаменов:
Вторник, 24.12, поточная Арктики - группы 220, 221, 222
Среда, 25.12, 113 ГК - группы 224, 226, 227
Магистры из 411 могут приходить в удобный день из этих двух.
Расписание захода сделаем позже, наверное, завтра.

Расписание захода задержалось, пока что поставил даты из академических групп. На листе "Дата экзамена" можно:
- выбрать дату, если вы из группы 411 (магистратура блокчейн)
- попросить о переносе даты (удовлетворение просьб не гарантируется, посмотрим по ситуации с количеством просьб и принимающих. Если причина уважительная, постараемся удовлетворить, но пишите мне в личку, в чём эта причина заключается)
- заявить, что на эту сдачу вы по какой-либо причине не придёте

Через пару часов я хотел бы составить время захода на завтра. Как обычно, чем выше текущая оценка за семестр, тем раньше будем звать. Начнём в 10 часов.

Про пересдачу осеннего курса: будет 2 возможности, в эту пятницу 14.02 и в понедельник 24.02. Оба раза утром, ориентировочно в 10. При необходимости сделаем ещё один день в марте. В табличке (https://docs.google.com/spreadsheets/d/1pOIEwQIhLC8v8JTX5Rk_By83tPb8cN-r75E02vVDr3Q/edit?usp=sharing) я пометил цветом, кто есть в списках на пересдачу. Пока что напишите мне в личку (@musatych), в какой из дней хотите прийти, в т.ч. если вас в списках по какой-то причине нет. Формальная запись для формирования ведомости тоже скоро будет. До пересдачи можно досдавать задачи из 2-й и 3-й домашки, которые не сдавались (в домашке) ранее, но в любом случае из расчёта 5 баллов за задачу.

В этом семестре канал и чат традиционно будут использоваться для курса дополнительных глав сложности вычислений. Это одновременно кафедральный курс для кафедры ДМ и курс по выбору в магистратуре. Но при желании можно и просто так ходить/сдавать. В этом файле приведена примерная программа курса, возможны изменения.

#дневниклекций
В этом семестре буду стараться записывать, что успели изучить на лекциях. Первая лекция 6 февраля была вводная. Мы прошли:
- неформальное объяснение, что такое интерактивное доказательство, на примере Боба-дальтоника и разноцветных носков
- неформальное объяснение, что такое доказательство с нулевым разглашением, на примере игры "Where's Waldo?" и судоку
- продолжение рассказа про нулевое разглашение: история про Али-Бабу, разбойника и Мика Али по мотивам статьи Кискатера и Гийю
- неформальное объяснение, что такое вероятностное проверяемое доказательство и его связь с задачами аппроксимации
- пара слов про доказательства с несколькими пруверами
- неформальный рассказ про игры Артура-Мерлина (интерактивные доказательства с общей случайностью), а также Артура и рационального Мерлина и их связь с облачными вычислениями
- несколько более формальный рассказ про интерактивный протокол для задачи о неизоморфизме графов

Выяснилось, что в программе была неправильная ссылка на чат. Вот правильная: https://yangx.top/+d7Y5C4MxnaRmZmM6

#дневниклекций
В прошлый раз, 13 февраля, на лекции прошли вот что (если что важное забыл перечислить, дополняйте):
- максимально общее определение интерактивной системы доказательств
- определение классов MA и AM
- амплификация в MA, вложение MA в AM.
- теорема о коллапсе AM-иерархии и теорема об ускорении: формулировки и идеи доказательства
- вложение MA и AM в полиномиальную иерархию: идея доказательства, формально наличие нужных сдвигов не доказывали
- протокол Голдвассер-Сипсера с общими случайными битами для задачи о неизоморфизме графов: идея сводимости к проверке размера множества и идея хеширования

Сегодня будем подробнее разбираться с этим протоколом, потом перейдём к IP=PSPACE

#дневниклекций
20 февраля подробно обсуждали протокол Голвассер-Сипсера:
- Повтор общей идеи
- Определение семейства попарно независимых хеш-функций. 2 эквивалентных формулировки.
- Обсуждение арифметики конечных полей. Построение поля размера 2^n: сложение и умножение по модулю неприводимого многочлена. О сложности поиска неприводимого многочлена.
- Построение семейства попарно независимых хеш-функций как аффинных функций в конечном поле
- Лемма о том, что ожидаемый размер образа под действием случайной хеш-функции не меньше 3/4 от размера исходного множества
- Построение протокола Голдвассер-Сипсера и доказательство его корректности

IP=PSPACE не успели, будет в следующий раз

Информация для пересдающих завтра осенний курс. Аудитория 520 ГК, начало в 10:00, рекомендуемое время захода есть в табличке. Если время не подходит или не отмечено, пишите в личку.

Подготовлена табличка для оценок этого года: https://docs.google.com/spreadsheets/d/1wBpGmPHv2-uyMeayswf-2Dp_5I9Iy5wlnnowFKTtbFg/edit?usp=sharing . Если вас нет в табличке, напишите в личку @musatych

Также готовы файлы с первой домашкой (индивидуальные варианты) и проектами для желающих (стоимость как у трёх задач, не блокируют никакие оценки, только теоретические проекты, которые никто не выбрал на основном курсе, либо новые добавленные). Правила и сроки сдачи в файлах, выбор проектов в табличке на втором листе.

Вчера был выложен неправильный файл - с программой, а не проектами, а все тактично промолчали. Надеюсь, кто-нибудь всё же захочет сделать проект, выбирайте по этому файлу.

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

Можно также предлагать свои варианты, если мне один из них приглянётся, то можно будет изучить что-нибудь вместе. Имеющиеся программы курсов и опрос в комментариях.

Готова вторая домашняя работа. К сожалению, на выполнение мы можем дать время только до следующей субботы, потом учебный офис начнёт активно просить оценки, а нам ещё нужно будет проверить. Гарантированные пороги на оценки внутри файла.

Контрольная работа состоится в четверг, 22 мая, с 10:45 до 13:45. Вероятно, в 432 ГК, но я ещё уточню на всякий случай. Это вариант прошлого года, выкладываю в качестве тренировочного.
Для магистров: у вас это экзамен, так что времени больше. Зарезервирована дата 10 июня, если хотите написать в неё, пишите в личку. Кто из магистров хотел перезачесть оценку из бакалавриата, также напишите ещё раз.