Математический семинар
Математический семинар ФКН объединяет математиков разных специальностей, а доклады доступны широкому кругу слушателей, включая аспирантов и заинтересованных студентов. Каждому выступающему предложено сформулировать для участников семинара актуальные задачи.
Встречи проходят раз в две недели по пятницам, с 18:10 до 19:30.
Бюро семинара:
• Устинов Алексей Владимирович
• Промыслов Валентин Валерьевич
2022–2023
31 марта в 18:10
Докладчик: Степан Кузнецов, МИАН им. В.А. Стеклова; ФКН НИУ ВШЭ.
Тема: Алгебраические логики с итерацией Клини
Аннотация: Итерация, или звёздочка Клини — это одна из наиболее интересных алгебраических операций, используемых в теоретической информатике. Алгебраические структуры с итерацией Клини, развившиеся из известной алгебры регулярных выражений, широко используются для описания формальных языков и для моделирования вычислительных процессов. В связи с этим интерес представляют алгебраические логики для структур с итерацией — т.е. логические исчисления, описывающие тождества, истинные в таких структурах — их алгоритмическая разрешимость и сложность. Эти логики оказываются неклассическими (точнее, субструктурными) вариантами логики высказываний, однако, за счёт индуктивной природы звёздочки Клини, приобретают некоторые черты намного более сильных систем, таких как формальная арифметика. В докладе будет дан обзор результатов об алгебраических логиках с итерацией Клини, как ранее известных, так и принадлежащих докладчику.
Место проведения: Покровский бульвар, 11 аудитория R405.
17 марта в 18:10
Докладчик: Николай Верещагин, ФКН НИУ ВШЭ, Мехмат МГУ, Яндекс
Тема: Полудуплексная коммуникационная сложность
Аннотация: В классической модели коммуникационной сложности, введённой Эндрю Яо в 1979 году, рассматривается игра для двух игроков, Алисы и Боба, которые хотят вычислить f(x,y) для некоторой функции f, причём Алисе известно только значение x, а Бобу - только значение y. Для решения этой задачи Алиса и Боб могут общаться, посылая друг другу битовые сообщения по одному биту за раунд. Важное свойство этой коммуникационной модели заключается в том, что на каждом раунде общения один из игроков посылает некоторое битовое сообщение, а другой игрок обязательно его принимает. Коммуникационная сложность функции определяется как минимальное количество битов, которые нужно передать, чтобы вычислить f(x,y) для всех возможных пар x,y.
Эта модель была обобщена в 2018 году Гувером, Импальяццо, Михайлиным и Смалем до модели, описывающей общение по так называемому полудуплексному каналу. Широко известный пример полудуплексного канала в обычной жизни - это общение при помощи раций: для передачи сообщения по рации нужно зажать кнопку передачи (принцип «push-to-talk»), в то же время на принимающей стороне в этот момент кнопка должна быть отпущена. Если два человека пытаются передавать сообщения одновременно (т.е. у обоих рации находятся в режиме передачи), то они не слышат друг друга. Есть разные модели полудуплексных коммуникационных протоколов: модель с тишиной (если оба пытаются принять сообщения, то они получают специальный символ "тишина"), модель с нулем (они принимают нулевой бит) и модель с противником (они принимают произвольные биты, выбираемые противником). Для большинства функций коммуникационная сложность с тишиной и с нулем меньше классической коммуникационной сложности. Однако до сих пор было неизвестным, различается ли коммуникационная сложность с противником от классической. Мы приведем пример функции, для которой полудуплексная коммуникационная сложность с противником строго меньше классической коммуникационной сложности.
Место проведения: Покровский бульвар, 11 аудитория R405.
3 марта в 18:10
Докладчик: Григорий Кабатянский факультет компьютерных наук, НИУ ВШЭ, Сколтех
Тема: Разделение секрета – многочлены над конечными полями, комбинаторика, коды и матроиды
Аннотация: Доклад будет посвящен некоторым математическим задачам, возникающим при изучении так называемого разделения секрета. Саму задачу можно сформулировать так: надо «разделить» секрет между n участниками таким образом, что разрешенные коалиции участников могли бы найти секрет, а любые неразрешенные не знали о секрете ничего «дополнительного», т.е. кроме априорных сведений. Самый популярный и изученный пример – пороговые схемы, т.е. разрешенные коалиции это все коалиции из t или более участников, и никакие больше. Эта задача связана, в частности, со следующей гипотезой, известной в комбинаторике, теории кодирования и даже алгебраической геометрии – пусть множество из n r-мерных векторов над конечным полем из q элементов таково, что любые r из них линейно независимы. Тогда n<q+2 (два исключения в характеристике 2). Гипотеза недавно доказана для простых полей.
А еще мы обсудим задачу о построении семейств k-мерных подпространств в n-мерном пространстве со свойством «все или ничего», то есть линейная оболочка любого множества этих подпространств пересекается с фиксированным k-мерным подпространством либо по вектору 0, либо содержит это фиксированное подпространство целиком. А отсюда уже рукой подать до матроидов!
Место проведения: Покровский бульвар, 11 аудитория R503.
17 февраля в 18:10
Докладчик: Дмитрий Шабанов, факультет компьютерных наук, НИУ ВШЭ
Тема: Пороговые вероятности в случайных графах и гиперграфах
Аннотация: Одно из основных направлений исследований в теории случайных подмножеств связано с поиском так называемых пороговых вероятностей. В биномиальной модели случайного подмножества Γ(n,p) данный эффект может быть кратко описан следующим образом: для каждого монотонного возрастающего свойства существует такая функция q(n), что при p=o(q) вероятность наличия свойства у случайного подмножества стремится к нулю, а при p=ω(q), наоборот, стремится к единице. Особенный интерес для изучения представляет ситуация, когда пороговая вероятность является точной.
В докладе будет дан краткий обзор общих результатов о пороговых вероятностях, а также представлены недавние результаты докладчика с соавторами об оценках пороговых вероятностей для свойств раскрасок случайных гиперграфов.
Место проведения: Покровский бульвар, 11 аудитория R405.
3 февраля в 18:10
Докладчик: Алексей Ремизов, кафедра высшей математики, МФТИ
Тема: Восстановление изображений математическими методами
Аннотация: Доклад посвящен прикладной задаче - восстановлению поврежденных изображений (inpainting). Существует большое число подходов к этой задаче, основанных на различных идеях. В докладе планируется рассказать о методе восстановления, основанном на использовании геометрической модели зрения, восходящей к работам нобелевских лауреатов Хьюбеля и Визеля, согласно которой плоское изображение, воспринимаемое сетчаткой глаза, обрабатывается нейронами коры головного мозга и "поднимается" на трехмерное многообразие - проективизированное касательное расслоение плоскости. Кроме того, планируется обсудить ситуации, в которых этот метод не работает и требуется придумать что-то совсем другое. Доклад носит ярко выраженный прикладной характер, будет много эмпирических данных, но не доказано ни одной теоремы.
Место проведения: Покровский бульвар, 11 аудитория R405.
20 января в 18:10
Докладчик: Иван Аржанцев, факультет компьютерных наук, НИУ ВШЭ
Тема: Образы аффинного пространства
Аннотация: В докладе изучаются алгебраические многообразия над полем комплексных чисел. Мы расскажем, что такое аффинное, проективное и абстрактное алгебраическое многообразие, и определим морфизмы между ними. Затем мы перейдем к вопросу о том, какие алгебраические многообразия можно реализовать как образы аффинного пространства. Оказывается, таких многообразий очень много. Используя понятие гибкого многообразия и конструкцию фактор-пространства, мы докажем, что для любого невырожденного торического многообразия X существует сюръективный морфизм из аффинного пространства в X. Аналогичный результат справедлив для однородных пространств и для многообразий, покрытых аффинными пространствами. Также в докладе будут сформулированы пять открытых вопросов, над которыми могут работать слушатели, знакомые лишь с основами алгебраической геометрии.
Место проведения: Покровский бульвар, 11 аудитория R405.
11 ноября, 18:10
Докладчик: Валентин Промыслов, факультет компьютерных наук, НИУ ВШЭ
Тема: Гипотеза о соответствиях Джека
Аннотация: Структурные константы Джека были введены в 1996 Гулденом и Джексоном как коэффициенты некоторых рядов, зависящие от параметра α и обобщающие структурные константы двух классических коммутативных подалгебр групповой алгебры симметрической группы, а именно, алгебры классов сопряжённости (при α = 1) и алгебры двойных смежных классов (при α = 2).
Структурные константы двух указанных алгебр (соответствующие значениям α = 1, 2) имеют интересные комбинаторные и топологические интерпретации в терминах паросочетаний на графах, вложенных в локально ориентируемые поверхности. Исходя из этой интерпретаций Гулден и Джексон выдвинули гипотезу о комбинаторном смысле структурных констант Джека. Рассказ будет посвящен этой гипотезе, а также рекуррентным формулам, позволяющим доказать её в некоторых частных случаях.
Место проведения: Покровский бульвар, 11 аудитория R503.
28 Октября, 18:10
Докладчик: Александр Калмынин, факультет математики, НИУ ВШЭ
Тема: Суммы двух квадратов и модулярные формы
Аннотация: Множество натуральных чисел, представимых в виде суммы двух квадратов, можно рассматривать как множество, промежуточное между простыми числами и множеством всех натуральных чисел. В этом контексте естественно решать задачи, представляющие интерес в случае простых чисел. Некоторые из них, такие как задача о числах-близнецах, оказываются тривиальными, а некоторые остаются настолько же сложными. Мы поговорим об одном из примеров последнего явления, а именно о распределении сумм двух квадратов в коротких интервалах. Задачи из этого направления оказываются тесно связаны со свойствами функции от двух переменных, которая проявляет некоторые из свойств автоморфных форм Якоби. В разложении Тейлора данной функции появляется последовательность одномерных модулярных форм, которая сводится к некоторой линейной дифференциальной рекуррентной последовательности многочленов. Все необходимые определения из теории модулярных форм будут даны в докладе.
Место проведения: Покровский бульвар, 11 аудитория R406.
Если у вас нет пропуска в здание НИУ ВШЭ, пожалуйста, укажите эту деталь в форме для регистрации!
14 Октября, 18:10
Докладчик: Алексей Устинов, факультет компьютерных наук, НИУ ВШЭ
Тема: Скрытые теоремы сложения
Аннотация: Скрытые теоремы сложения
Место проведения: Покровский бульвар, 11 аудитория R503.
Если у вас нет пропуска в здание НИУ ВШЭ, пожалуйста, укажите эту деталь в форме для регистрации!