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

Сегодня на межкафедральном семинаре (18:30, 115 КПМ) будет интересный доклад Николая Мощевитина "Диофантовы приближения и квадратичные формы" Аннотация: Я расскажу о классических и совсем новых результатах о равномерных приближениях точек на квадратичных поверхностях рациональными точкам. В частности, я попробую объяснить, почему законы приближения на сфере в Rn такие же, как на вещественной прямой R.

https://docs.google.com/spreadsheets/d/1n1GvkogrZPe10Va0HzlvT70LblAReEUnIt7NJK-z9bU/edit?usp=sharing - в эту таблицу можно будет записывать номера выбранных проектов. Если есть своя тема, впишите номер 0 и комментарий. Внизу табличка со списком, какой проект сколько раз выбран. Если больше двух, то строка загорается красным - тогда нужно кому-то выбрать другой, либо всем явно указать разные спецификации. Не занимайтесь вандализмом, портя чужие строки! Конфликты решайти коммуникацией, а лучше придумыванием своих тем. Сам файл со списком выложу в 18:00.

Завтра, 12.09, в 18:30 в 115 КПМ будет межкафедральный семинар. Сначала будет доклад Ильи Шкредова про аддитивную комбинаторику, потом я расскажу про вычислительную сложность задач поиска и их связь с математической экономикой.

На всякий случай повторяю ссылку на чат по спецкурсу о псевдослучайности и дерандомизации: https://t.me/joinchat/DZlFTRI3Dvope1VxBqmUng Занятия будут проходить по четвергам в 16:15 в ШАДе (м. Парк Культуры). Если есть желающие ходить 3-курсники, которым расписание неудобно, сообщите об этом.

Для присоединившихся: ссылка на чат для обсуждения оперативных вопросов https://t.me/joinchat/DZlFTUSE1txDQid4LeIkbA

Также на второй неделе начнётся спецкурс по псевдослучайности и дерандомизации. Для него тоже есть отдельный чат: https://t.me/joinchat/DZlFTRI3Dvope1VxBqmUng

В новом семестре этот канал будет использоваться для рассылки новостей по предметам у третьего курса. По криптографии у четвёртого курса создан отдельный чат: https://t.me/joinchat/DZlFTQ8qiK7Ymz7GXLiaKw

Напоминание информации из чата: контрольная по дополнительным главам будет сегодня в 10:30, аудитория Гарвард.

Это конспект Шеня про 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 ГК. Первое занятие завтра. Сейчас выложу аннотацию.