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

Это конспект Шеня про MIP=NEXP

Завтра, 19 апреля, состоится лекция по допглавам сложности. Начало, как обычно, в 12. Будем разбираться с теоремой MIP=NEXP. Она соединяет в себе идеи из IP=PSPACE и PCP-теоремы. Будут использованы техника тестирования и самокоррекции, многочлены малых степеней, расширение булевой функции на конечное поле и т.д.

Завтра, 12 апреля, после перерыва продолжатся занятия по допглавам сложности. Начало, как обычно, в 12. Будем обсуждать коды Уолша-Адамара, дикретное преобразование Фурье, тесты линейности и экспоненциальную PCP-теорему.

Завтра, 1 марта, занятия по дополнительным главам сложности вычислений начнутся в 11:00 в связи с отсутствием предыдущей пары. Будет рассказано доказательство теоремы IP=PSPACE.

Желающие ходить на спецкурс по комбинаторным играм и/или следить за происходящим там приглашаются в специальный чат по ссылке https://t.me/mipt_cgt

Прошу прощения за позднее объявление, но приглашаю на спецкурс по комбинаторной теории игр. Курс будет по четвергам с 18:30 в 413 ГК. Первое занятие завтра. Сейчас выложу аннотацию.

Готова дорешка по второй контрольной, решать можно до экзамена, но лучше присылать хотя бы за день.

Досрочный экзамен пройдёт завтра в Долгопрудном, сбор в 10 у 123 ГК.

Программа экзамена

По поводу лекции 15 декабря общественное настроение понятно: будет философская беседа. Но приходите, раз уж проголосовали.

Тренировочный вариант второй контрольной наконец подготовлен. Контрольная пройдёт в семинарское время 15 и 19 декабря.

Чем занять лекционное время в пятницу, 15 декабря? (Это пока замер мнений, результат не будет обязывающим).
anonymous poll

Беседа про философские аспекты сложности вычислений – 20
👍👍👍👍👍👍👍 67%

Контрольная для 599 группы и желающих из других групп – 4
👍 13%

Обычная лекция (материал НЕ будет на экзамене) – 3
👍 10%

Презентация проектов для желающих – 3
👍 10%

👥 30 people voted so far.

Дорешка изготовлена. По вашим заявкам задачи распределены случайно. Задачи упорядочены по студентам так же, как в табличке. Работает поичск по файлу. Некоторые сложные задачи повторяются с контрольной, кому-то может даже та же самая попасться, это нормально. Некоторые могут оказаться сильно сложнее, чем на контрольной, но случайное распределение должно всё сгладить. Срок сдачи я поставил перед 2-й контрольной (15/19 декабря). Конечно, группе 599 тоже можно сдавать до 19-го, но лучше всё-таки 15-го.

Каким методом выдавать дорешку? (Решится простым большинством по этому опросу).

Распределить задачи случайно – 49
👍👍👍👍👍👍👍 92%

Сделать список со свободным выбором (1 задача на группу) – 4
👍 8%

👥 53 people voted so far.