Вторник, 11 ноября, Zoom. Начало в 15:00.

Докладчик: А.В. Пастор (ПОМИ).

Тема: О вершинах степени 6 C_3-критических минимальных 6-связных графов.Abstract Будет доказано, что в C_3-критическом минимальном 6-связном графе любая
вершина степени 6 смежна как минимум с двумя вершинами степени 6. Также
будет рассказано о некоторых других свойствах таких графов.

Вторник, 11 ноября, Zoom. Начало в 14:00.

Докладчик: Я.В. Благушин (ПОМИ).

Тема: О некоторых свойствах суммы Полиа-Виноградова.Abstract В докладе будут рассмотрены некоторые свойства суммы
Полиа-Виноградова, появляющейся в различных задачах теории чисел.
Особое внимание будет уделено её оценкам и асимптотическим свойствам.
Будет также отмечено, что невзаимнопростота параметров суммы является
важным частным случаем, о котором нам на сегодняшний день известно
чуть больше, чем о других случаях. В докладе автор также кратко
расскажет о некоторых других своих исследованиях, вышедших в этом
году.

Вторник, 28 октября, Zoom. Начало в 14:00.

Докладчик: В.П. Оревков (ПОМИ).

Тема: Слабая форма свойства подформульности секвенциальных доказательств с сечениями..Abstract В докладе будут сформулированы условия, когда правила, которые
применяются в доказательствах с сечениями, не будут применяться
после устранения сечений. Будет также доказана индукцией по глубине
формул теорема об устранимости сечений в классическом исчислении
предикатов.

Вторник, 28 октября, Zoom. Начало в 15:00.

Докладчик: Н.Н. Воробьев (ПОМИ).

Тема: Теоремы о разбиениях для семейств полу-Пфаффовых множеств.Abstract Будет рассказано об обобщениях теорем о полиномиальных разбиениях Гута-Каца на множества, задаваемые как многочленами, так и трансцендентными функциями. Эти теоремы применяются для доказательства обобщений теорем типа Семереди-Троттера о верхних оценках на число инцеденций, а также для верхней оценки на число джоинтов Пфаффовых кривых.

Вторник, 14 октября, Zoom. Начало в 14:00.

Докладчик: С.И. Николенко (ПОМИ).

Тема: Улучшения и приложения больших языковых моделей.Abstract В докладе речь пойдёт о результатах нескольких моих публикаций,
вышедших в 2025 году и посвящённых главным образом работе с большими
языковыми моделями. Основная тема первой части -- улучшение работы
больших языковых моделей в разных сценариях, в частности при
использовании внешних инструментов и при написании и последующей
верификации программного кода. Во второй части я расскажу об
исследованиях об использовании больших языковых моделей в
онлайн-маркетинге.

Вторник, 14 октября, Zoom. Начало в 14:00.

Докладчик: С.И. Николенко (ПОМИ).

Тема: Улучшения и приложения больших языковых моделей.Abstract В докладе речь пойдёт о результатах нескольких моих публикаций,
вышедших в 2025 году и посвящённых главным образом работе с большими
языковыми моделями. Основная тема первой части -- улучшение работы
больших языковых моделей в разных сценариях, в частности при
использовании внешних инструментов и при написании и последующей
верификации программного кода. Во второй части я расскажу об
исследованиях об использовании больших языковых моделей в
онлайн-маркетинге.

Вторник, 14 октября, Zoom. Начало в 15:00.

Докладчик: Д.В. Карпов (ПОМИ).

Тема: Удаление деревьев из n-связного графа с сохранением связности.Abstract Д.В. Карпов расскажет о том, что может получиться, если покопаться вокруг олимпиадной задачи (которая, в свою очередь, получилась как раз из науки).
Это совместная работа с Елизаветой Аксеновой, получившаяся несколько неожиданно для нас.

Вторник, 14 октября, Zoom. Начало в 15:00.

Докладчик: Д.В. Карпов (ПОМИ).

Тема: Удаление деревьев из n-связного графа с сохранением связности.Abstract Д.В. Карпов расскажет о том, что может получиться, если покопаться вокруг олимпиадной задачи (которая, в свою очередь, получилась как раз из науки).
Это совместная работа с Елизаветой Аксеновой, получившаяся несколько неожиданно для нас.

Вторник, 7 октября, zoom. Начало в 15:00.

Докладчик: Ю.В. Матиясевич (ПОМИ).

Тема: Dirichlet L-functions, lower gamma-function, and Touchard polynomials.Abstract We introduce a particular one-parameter family of polyno-
mials in one variable. These polynomials are defined as linear combinations
of the so-called Touchard polynomials (sometimes also called the Bell poly-
nomials). We demonstrate the connections between our polynomials and
Dirichlet L-functions and the lower incomplete gamma-function.

Вторник, 7 октября, zoom. Начало в 15:00.

Докладчик: Ю.В. Матиясевич (ПОМИ).

Тема: Dirichlet L-functions, lower gamma-function, and Touchard polynomials.Abstract We introduce a particular one-parameter family of polyno-
mials in one variable. These polynomials are defined as linear combinations
of the so-called Touchard polynomials (sometimes also called the Bell poly-
nomials). We demonstrate the connections between our polynomials and
Dirichlet L-functions and the lower incomplete gamma-function.

Вторник, 23 сентября, zoom. Начало в 16:00.

Докладчик: А.В. Смаль (ПОМИ).

Тема: Каталитические вычисления и регистровые программы за пределами логарифмической глубины.Abstract В работе Buhrman, Cleve, Koucký, Loff, и Speelman (STOC 2014) авторы
определили сложностной класс CSPACE(s,c) – класс задач, разрешимых в
на машине Тьюринга с обычной рабочей лентой размера s и с
дополнительной "каталитической" лентой размера c, чьё начальное
содержимое должно быть восстановлено в конце вычисления. Они показали,
что равномерные схемы TC1 вычислимы в каталитическом логарифмическом
пространстве, то есть CL=CSPACE(O(log n), 2^{O(log n))}), тем самым
предоставив веские доказательства того, что наличие доступа к
каталитической ленте даёт дополнительную вычислительную мощность. Их
исследование сосредоточено на арифметической модели, называемой
регистровыми программами, которая с тех пор стала одним из центральных
объектов изучения.

Понимание CL остаётся важной открытой проблемой, поскольку "TC1 лежит
в CL" остаётся наиболее мощным включением такого типа на сегодняшний
день. В докладе будет рассказано о том, как используя регистровые
программы показать, что класс SAC2 булевых схем полиномиального
размера и глубины O(log n), с ограниченным арностью гейтов "И" и
неограниченной арностью гейтов "ИЛИ", можно вычислить на
каталической машине Тьюринга с рабочей лентой размера o(log n)
и каталитической лентой почти полиномиального размера.

По совместной работе https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or...

Вторник, 23 сентября, zoom. Начало в 16:00.

Докладчик: А.В. Смаль (ПОМИ).

Тема: Каталитические вычисления и регистровые программы за пределами логарифмической глубины.Abstract В работе Buhrman, Cleve, Koucký, Loff, и Speelman (STOC 2014) авторы
определили сложностной класс CSPACE(s,c) – класс задач, разрешимых в
на машине Тьюринга с обычной рабочей лентой размера s и с
дополнительной "каталитической" лентой размера c, чьё начальное
содержимое должно быть восстановлено в конце вычисления. Они показали,
что равномерные схемы TC1 вычислимы в каталитическом логарифмическом
пространстве, то есть CL=CSPACE(O(log n), 2^{O(log n))}), тем самым
предоставив веские доказательства того, что наличие доступа к
каталитической ленте даёт дополнительную вычислительную мощность. Их
исследование сосредоточено на арифметической модели, называемой
регистровыми программами, которая с тех пор стала одним из центральных
объектов изучения.

Понимание CL остаётся важной открытой проблемой, поскольку "TC1 лежит
в CL" остаётся наиболее мощным включением такого типа на сегодняшний
день. В докладе будет рассказано о том, как используя регистровые
программы показать, что класс SAC2 булевых схем полиномиального
размера и глубины O(log n), с ограниченным арностью гейтов "И" и
неограниченной арностью гейтов "ИЛИ", можно вычислить на
каталической машине Тьюринга с рабочей лентой размера o(log n)
и каталитической лентой почти полиномиального размера.

По совместной работе https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or...

Вторник, 23 сентября, zoom. Начало в 15:00.

Докладчик: И.Н. Пономаренко (ПОМИ).

Тема: Большое семейство сильно регулярных графов с малой размерностью Вейсфейлера-Лемана.Abstract В 2002 году Д. Фон-дер-Флаассом было предложено семейство сильно регулярных графов, отличающееся большим количеством/разнообразием элементов (prolific family). В этом докладе мы обсудим, что такое сильно регулярные графы и как строятся подобные конструкции. Мы покажем, что для бесконечного числа натуральных чисел $n$ семейство Фон-дер-Флаасса содержит $n^{\mathsf{\Omega}(n^{2/3})}$ сильно регулярных $n$-вершинных графов $X$ с одинаковыми параметрами и удовлетворяющих следующему условию: изоморфизм между $X$ и любым другим графом может быть проверен 4-мерным алгоритмом Вейсфейлера-Лемана. 

Вторник, 23 сентября, zoom. Начало в 15:00.

Докладчик: И.Н. Пономаренко (ПОМИ).

Тема: Большое семейство сильно регулярных графов с малой размерностью Вейсфейлера-Лемана.Abstract В 2002 году Д. Фон-дер-Флаассом было предложено семейство сильно регулярных графов, отличающееся большим количеством/разнообразием элементов (prolific family). В этом докладе мы обсудим, что такое сильно регулярные графы и как строятся подобные конструкции. Мы покажем, что для бесконечного числа натуральных чисел $n$ семейство Фон-дер-Флаасса содержит $n^{\mathsf{\Omega}(n^{2/3})}$ сильно регулярных $n$-вершинных графов $X$ с одинаковыми параметрами и удовлетворяющих следующему условию: изоморфизм между $X$ и любым другим графом может быть проверен 4-мерным алгоритмом Вейсфейлера-Лемана.