Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo


Вторник 22.10. Н.Н. Воробьёв (ПОМИ): "Триангуляция кляксы"

Speaker: 
Н.Н. Воробьёв (ПОМИ)
Date: 
Tuesday, October 22, 2024 - 14:00
Place: 
Zoom
Abstract: 

Рассмотрим компактное множество K в R^3, определимое в о-минимальной структуре над R, например, полуалгебраическое или субаналитическое. В работе решается задача триангуляции монотонно растущего однопараметрического определимого семейства подмножеств в К. В каждом симплексе триангуляции семейство имеет один из 9 стандартных типов, биективно кодируемых лексикографически монотонными булевыми функциями от трех переменных. Подобные триангуляции полезны для верхних оценок гомологий определимых множеств.

Вторник 08.10. И.Н. Пономаренко (ПОМИ): "Вокруг проблемы изоморфизма"

Speaker: 
И.Н. Пономаренко (ПОМИ)
Date: 
Tuesday, October 8, 2024 - 15:00
Place: 
Zoom
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. Д.М. Ицыксон (ПОМИ): " Нижние оценки для регулярных резолюций над линейными уравнениями"

Speaker: 
Д.М. Ицыксон (ПОМИ)
Date: 
Tuesday, October 8, 2024 - 14:00
Place: 
Zoom
Abstract: 

Аннотация: Система доказательств резолюция над линейными уравнениями (Res(⊕)) оперирует дизъюнкциями линейных уравнений (линейными дизъюнктами) над полем GF(2); эта система расширяет обычную резолюцию с помощью линейной алгебры над полем GF(2). За последние десять лет было доказано несколько экспоненциальных нижних оценок на размер древовидных Res(⊕) опровержений. Суперполиномиальные нижние оценки на размер опровержений в системе Res(⊕) без ограничений до сих пор неизвестны.

В докладе будет рассказана экспоненциальная нижняя оценка на размер вывода в регулярной версии системы Res(⊕). Регурярная Res(⊕) --- это подсистема Res(⊕), естественным образом обобщающая регулярную резолюцию.
Это первая суперполиномиальная нижняя оценка на фрагмент системы Res(⊕), который строго сильнее древовидной Res(⊕).

Доклад основан на совместной работе с Климом Ефременко и Михалом Гарликом.

Пятница 21.01. Д. М. Ицыксон (ПОМИ РАН): "Нижние оценки и вопросы оптимальности для систем доказательств"

Speaker: 
Д. М. Ицыксон (ПОМИ РАН)
Date: 
Friday, January 21, 2022 - 13:00
Place: 
Zoom
Abstract: 

В докладе будет дан обзор результатов докладчика на следующие темы:

(1) сложность вывода в системах доказательств, основанных на OBDD;
(2) сложность вывода цейтинских формул в зависимости от древесной ширины графа;
(3) нижние оценки на сложность вывода в подсистемах системы Res(+) (резолюция над дизъюнкциями линейных равенств по модулю 2); 
(4) оптимальные эвристические и вероятностные аксепторы.

Подключиться к докладу можно по ссылке: https://zoom.us/j/95294301096?pwd=dXJXOWtqcjVZcy9qdXZZUTNFRjl0UT09

Pages