Семинары ПОМИ
П. Н. Антонюк, А. Томаш и Э.-М. Аморетти: производящая функция и производящее число для натурального ряда
А. С. Токмачев, Распределение числа целых точек внутри случайно сдвинутого тела
С. С. Постушков, Порядок вторичного функционала гладкого отображения сферы
С. В. Самсонов, Неасимптотический анализ алгоритма стохастического градиентного спуска с модификацией Ричардсона-Ромберга
А. В. Люлинцев, Якобиевы ветвящиеся случайные блуждания, соответствующие ортогональным многочленам дискретной переменной
С. В. Фомин, Порядки гомотопических инвариантов отображений в пространства Эйленберга ---; Маклейна
Г. Л. Эпштейн, Анри Пуанкаре и качественная теория динамических систем
Махмуд Аль-Хамза, Об истории научной арабистики в России: История изучения арабских математических рукописей средневековья в России
Вторник 08.10. И.Н. Пономаренко: "Вокруг проблемы изоморфизма"
Вторник, 8 октября, Zoom. Начало в 15:00.
Докладчик: И.Н. Пономаренко (ПОМИ).
Тема: Вокруг проблемы изоморфизма.Abstract В докладе будут затронуты две проблемы теории сложности вычислений: распознавание изоморфизма (конечных) графов и групп, и нахождение группы автоморфизмов ``симметричных’' объектов. В первом части мы приведем несколько эквивалентных определений размерности Вейсфейлера-Лемана групп и графов, проследим связь этого инварианта с проблемой изоморфизма, и опишем два новых результата: об алгебраической природе этого инварианта [1] и о размерности Вейсфейлера-Лемана графов перествновок [2]. Во второй части, мы поговорим о многомерных комбинаторных объектах, возникающих из групп перестановок и опишем новый результат о вычислении полной группы автоморфизмов такого объекта в случае, когда исходная группа перестановок разрешима [3].
[1] G.Chen, Q.Ren, and I.Ponomarenko, On multidimensional Schur rings of finite groups, J. Group Theory, 27:1, 61-88 (2024), https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or....
[2] J. Guo, A.L.Gavrilyuk, and I.Ponomarenko, On the Weisfeiler-Leman dimension of permutation graphs, SIAM Journal on Discrete Mathematics, 38:2, 1193-1929 (2024), https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or....
[3] I.Ponomarenko and A.V.Vasil'ev, On computing the closures of solvable permutation groups, International J. Algebra and Computation, 34:1, 137-145 (2024), doi: 10.1142/S0218196724500036.
Вторник 08.10. Д.М. Ицыксон: " Нижние оценки для регулярных резолюций над линейными уравнениями"
Вторник, 8 октября, Zoom. Начало в 14:00.
Докладчик: Д.М. Ицыксон (ПОМИ).
Тема: Нижние оценки для регулярных резолюций над линейными уравнениями.Abstract Аннотация: Система доказательств резолюция над линейными уравнениями (Res(⊕)) оперирует дизъюнкциями линейных уравнений (линейными дизъюнктами) над полем GF(2); эта система расширяет обычную резолюцию с помощью линейной алгебры над полем GF(2). За последние десять лет было доказано несколько экспоненциальных нижних оценок на размер древовидных Res(⊕) опровержений. Суперполиномиальные нижние оценки на размер опровержений в системе Res(⊕) без ограничений до сих пор неизвестны.
В докладе будет рассказана экспоненциальная нижняя оценка на размер вывода в регулярной версии системы Res(⊕). Регурярная Res(⊕) --- это подсистема Res(⊕), естественным образом обобщающая регулярную резолюцию.
Это первая суперполиномиальная нижняя оценка на фрагмент системы Res(⊕), который строго сильнее древовидной Res(⊕).
Доклад основан на совместной работе с Климом Ефременко и Михалом Гарликом.
И. А. Рагозин, Критерии согласия, основанные на характеризациях распределений, и их эффективность
А. А. Наумов, Нормальная аппроксимация и мультипликативный блок-бутстреп для алгоритмов стохастической аппроксимации с марковским шумом
Вторник 17.09. А.В. Смаль: "Lifting Dichotomies"
Вторник, 17 сентября, Zoom. Начало в 15:00.
Докладчик: А.В. Смаль.
Тема: Lifting Dichotomies.Abstract Lifting theorems are used to transfer lower bounds between Boolean function complexity measures. Such theorems have applications in many different areas, such as circuit complexity, communication complexity, proof complexity, etc. In this talk, we will systematically study the question, "For which gadgets does the lifting result hold?'' in the following settings: lifting from decision tree depth to decision tree size, lifting from decision tree depth to parity decision tree depth and size, and lifting from block sensitivity to deterministic and randomized communication complexities.
Доклад по совместной работе с Ярославом Алексеевым и Yuval Filmus.
Вторник 17.09. А.С.Куликов, А.В.Смаль по 45 мин: "Темы будут объявлены докладчиками"
Вторник, 17 сентября, Zoom . Начало в 14:00.
Докладчик: А.С.Куликов, А.В.Смаль по 45 мин (ПОМИ).
Тема: Темы будут объявлены докладчиками.Abstract Обзоры недавних работ
Г. И. Синкевич, Новое в иконографии Л.Эйлера
Ал. В. Булинский, Вклад академика А.Н. Колмогорова в создание современной теории вероятностей
Жаров В. К., Математика древних и средневековых алгоритмов, по избранным трактатам китайских ученых
Вторник 03.09. Надежда Юрьевна Власова : "О стягиваемых подграфах 3-связного графа"
Вторник, 3 сентября, ауд. 203. Начало в 14:00.
Докладчик: Надежда Юрьевна Власова.
Тема: О стягиваемых подграфах 3-связного графа.Abstract Будут представлены результаты диссертации на тему, указанную в названии доклада.
Русский
English