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

Ссылка для подключения: https://us02web.zoom.us/j/81448543564?pwd=VFlISDFndmFnYmd6RlVjTmVGQTVoQT09 Идентификатор конференции: 814 4854 3564 Код доступа: 144189

ВНИМАНИЕ! Я заболел, так что сегодняшняя лекция пройдёт онлайн (в Zoom). Ссылку пришлю сюда перед лекцией.

Завтра на нашей кафедре открывается новый онлайн-семинар по математике в память о Э.Б.Винберге. Будет доклад, посвящённый приложениям алгебры в компьютерных науках. Ниже анонс на английском и ссылка на регистрацию. Приходите! Prof. Alex Lubotzky (Hebrew Univ., Israel) will speak on Tuesday October 5 at 18.00 by Moscow time = 17.00 by Paris/Berlin = 11.00am by New York/New Jersey in our new online seminar «The Vinberg Distinguished Lecture Series». Web-page of the seminar : https://vinberg.combgeo.org/ Registration for receiving a Zoom link is here : http://eepurl.com/hISqyv Title of the talk: Stability and testability of permutations' equations Abstract: Let A and B be two permutations in Sym(n) that ``almost commute" -- are they a small deformation of permutations that truly commute? More generally, if R is a system of words-equations in variables X = x_1,....,x_d and A_1,...,A_d permutations which are nearly solution; are they near true solutions? It turns out that the answer to this question depends only on the group presented by the generators X and relations R. This leads to the notions of ``stable groups" and ``testable groups". We will present a few results and methods which were developed in recent years to check whether a group is stable or testable. We will also describe the connection of this subject with property testing in computer science, with the long-standing problem of whether every group is sofic and with invariant random subgroups. Hoping many of you will be able to come! Upcoming Talks: - Alex Lubotzky (Hebrew University, Israel) on Tue Oct 5, 2021 - Alan Reid (Rice University, USA) on Tue Oct 19, 2021 - Peter Sarnak (IAS Princeton, USA) on Tue Nov 9, 2021 - Dmitry Alekseevsky (IITP RAS, Moscow, Russia) on Tue Nov 23, 2021 - Maryna Viazovska (EPFL, Switzerland) on Tue Dec 7, 2021 Best regards, Nikolay Bogachev, Sasha Kolpakov, Alex Kontorovich

В это воскресенье, 3 октября, приглашаю поучаствовать в математическом онлайн-квесте от "Бегущего города". Там будут весёлые задачки, данные для которых нужно найти в интересных местах на панорамах "Яндекс-карт" и в других онлайн-источниках. Игра командная с любым числом участников, пройдёт утром, с 8 до 14 по Московскому времени, но время на дистанции ограничено 4 часами после старта. Регистрация на сайте https://www.runcity.org/ru/events/onlineintegral2021/, по промокоду, который можно узнать у меня, участие бесплатное. (Всем участникам команды нужно завести профиль на сайте и добавиться в команду).

Возможно, вы знаете, что бывают студенческие олимпиады по математике. Так вот завтра на ФКН состоится одна из таких олимпиад. Поэтому если слова "олимпиадная математика" греют вам душу, то можно поучаствовать. Кроме того, обычно на осенних олимпиадах бывает отдельный вариант для первого курса. Вот информация: Открытая осенняя олимпиада по математике ФКН ВШЭ (OSAM Comp'21) состоится в субботу 18го сентября, предварительно, в 16:30 в двух форматах: очно на Факультете компьютерных наук (Покровский бульвар 11 с.4, аудитории станут известны позднее) и онлайн (с привлечением систем прокторинга). К участию приглашаются студенты 1-4 курса бакалавриата, а также, вне конкурса, студенты магистратуры. Олимпиада открытая, приглашаются студенты всех ВУЗов! Рабочие языки олимпиады русский и английский. Обязательна предварительная регистрация: https://forms.gle/Y29ksCmj3Utnr5sq5 Примеры заданий и результаты прошлых лет можно найти по ссылке: https://cs.hse.ru/olymp/open_math_olymp Информационный Telegram-канал олимпиады: https://t.me/osamcomp21

В этом семестре @AlexeySMilovanov и Александр Шень будут читать спецкурс "Колмогоровская сложность". Спецкурс будет проходить онлайн по понедельникам с 17.05 по 18.30, начиная с 13 сентября. Концепция Колмогоровской сложности возникла в 60-х годах 20-го века на стыке теории алгоритмов, теории информации и теории вероятностей. С помощью этого понятия можно определить количество информации в индивидуальном сообщении. В спецкурсе будет рассказано про основные достижения этой науки, а также об её применениях (например, в комбинаторике и теории автоматов). Если интересно, заходите в чат https://t.me/joinchat/HahiTYS05UQxYmNi

Тех, кто проходил курс в прошлом году, приглашаю в чаты по курсам наступающего семестра: https://t.me/joinchat/RGQjj4R4Y4VcuJor - Криптография https://t.me/joinchat/TFWCy-HlhfwGqZSe - спецкурс "Псевдослучайность и дерандомизация"

Внимание, есть возможность поехать на летнюю школу по сложности вычислений в Сириусе, с очень сильными преподавателями из Санкт-Петербурга. Все расходы оплачивают. Основной минус - дедлайн по подаче уже в воскресенье, 4 июля, и нужно решить несколько задач. Ещё там нужна рекомендация, скорее всего я смогу её написать, но сообщите как можно быстрее, если она нужна. Список курсов: Схемная сложность булевых функций (Александр Куликов) Высокоточные оценки сложности (Иван Михайлин) Сложность доказательств (Дмитрий Соколов) Формульная сложность и гипотеза KRW (Александр Смаль) Подача заявок тут: https://siriusmathcenter.ru/program/005s От себя добавлю, что в своё время подобная школа от тех же организаторов сильно помогла моему развитию как преподавателя и исследователя.

Кто хочет писать контрольную по допглавам, заходите в ближайшее время сюда: https://us02web.zoom.us/j/85031883772?pwd=OERNZU10c2NXekZuYmcwNW12M2lmQT09 Она с 17 часов на 2.5 часа.

Большинство участников опроса высказались за "Псевдослучайность и дерандомизацию". Так и сделаем. По этому курсу уже есть чат, так что присоединяйтесь, кто хочет ходить: https://t.me/joinchat/TFWCy-HlhfwGqZSe Скорее всего, занятия будут в четверг вечером, но в любом случае согласованы с расписанием базовых предметов на кафедре ДМ.

Внезапно от меня попросили названия спецкурсов на следующий год. Традиционно осенью я читаю продвинутый спецкурс по сложности вычислений. Есть несколько возможных тем. В чате я сейчас сделаю неанонимный опрос, а тут подробно напишу о содержании в разных вариантах. * Вероятностно проверяемые доказательства - основы теории экспандеров, полное доказательство PCP-теоремы и рассмотрение сложности приближения в конкретных задачах, роль Unique Game Conjecture * Псевдослучайность и дерандомизация - тоже основы теории экспандеров, генераторы псевдослучайных чисел, методы дерандомизации, теорема Рейнгольда (детерминированная проверка достижимости в графе на лог. памяти), почему мы верим, что P=BPP, и почему пока что не получилось этого доказать. * Сложность задач поиска - подробное рассмотрение классов PPA, PPAD и других, доказательство полноты задач о неподвижных точках в PPAD, классификация некоторых других задач * Рациональные интерактивные доказательства - доказательство теорем о классификации разных классов интерактивных доказательств. Такой курс был в прошлом году, так что будет повторён, только если к нему будет повышенный интерес

С 28 июня по 4 июля в Сириусе пройдёт очень интересная летняя школа "Современные задачи прикладной комбинаторики". Требования на входе: * знакомство с основами машинного обучения, теорией оптимизации, математической статистикой и теорией графов * владение навыками программирования на языках высокого уровня Сама программа включает в себя такие разделы, как: * теория случайных графов; * геометрические графы; * задачи комбинаторной оптимизации; * методы оценки хроматических чисел графов; * теоретико-числовые алгоритмы и оптимизированные меры частотности в языке. Школа бесплатная, но отбор по конкурсу. Конкурсные задачи и другие подробности тут: https://sochisirius.ru/obuchenie/graduates/smena936/4522

https://drive.google.com/file/d/1N2vO4G0EzkfefxyK1Obctwi-1QF10lyQ/view?usp=sharing - видеозапись последней лекции