Семинар по истории математики, 2 мая 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Семинар по истории математики, 2 мая 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Городской семинар по теории вероятностей и математической статистике, 26 апреля 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Городской семинар по теории вероятностей и математической статистике, 19 апреля 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Пятница, 19 апреля, ауд. 106. Начало в 16:00.

Докладчик: Виктор Лопаткин.

Тема: Двудольные графы как полиномы и полиномы как двудольные графы.Abstract В докладе будут представлены следующие две конструкции:
(1) По каждому неориентированному (ориентированному) конечному двудольному графу строится полином , который в случае, если граф неориентируемый, то , а если -- ориентируемый, то .
(2) По каждому полиному строится неоринтируемый двудольный конечный граф , а по каждому полиному строится ориентируемый конечный двудольный граф .

При этом, обе эти конструкции взаимно обратны друг к другу, то есть . Мы далее покажем, что обычное произведение (двудольных) графов соответствует произведению их полиномов, то есть , а граф соответствующий сумме полиномов, скажем , есть граф полученный ``приклеиванием'' графа к по определённому, но при этом простому, правилу.

Как приложение, мы обсудим делимость в полукольцах , с помощью этих конструкций. Наконец, мы вводим на множестве двудольных графов топологию Зарисского.

Доклад по совместной работе с Андреем Гринблат.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 18 апреля 2019, 16:00Место: комната 203Докладчик: Н. Н. Косовский (СПбГУ)Тема: Area minimizing surfaces of bounded genus in metric spacesАннотация: 

По работе Мартина Фитци и Стефана Венгера.
 

Петербургский топологический семинар им. В. А. Рохлина, 15 апреля 2019 г. 17:15, г. Санкт-Петербург, ПОМИ, комн. 203 (наб. р. Фонтанки, 27)

Cреда, 17 апреля, 106. Начало в 14:00.

Докладчик: Д. Соколов.

Тема: Псевдо-ширина и замыкания.Abstract Резолюция является наиболее хорошо изученной системой доказательств. Известные техники для доказательств нижних оценок на данную систему плохо применимы в случае, когда формула <<перегружена>> переменными. Одним из ярких примеров <<нехорошей>> для резолюций формулы является Weak-PigeonHole (принцип Дирихле с m кроликами и n клетками, причем m >> n^2). Впервые нижняя оценка для данной формулы была доказана Разом в 2001 году, Разборов впоследствии усилил и обобщил с помощью своего так называемого метода псевдоширины.

На семинаре мы обсудим технику псевдо-ширины, и покажем нижнюю оценку на weak-PHP для разреженных графов. Совместная работа с Susanna F. de Rezende, Jakob Nordström и Kilian Risse.

Городской семинар по теории вероятностей и математической статистике, 12 апреля 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Семинар: Городской алгебраический семинар им. Д.К.ФаддееваВремя: понедельник, 15 апреля 2019, 10:30Место: ком. 311Докладчик: С. В. Востоков (СПбГУ)Тема: Явные законы взаимности и криптография

Городской семинар по теории вероятностей и математической статистике, 5 апреля 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Семинар по истории математики, 4 апреля 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Семинар по истории математики, 4 апреля 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 4 апреля 2019, 16:00Место: комната 203Докладчик: А. В. Смирнов (ПОМИ)Тема: Двойные отношения в наши дниАннотация: 

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

В докладе будет сделан обзор на эту тему работ J. Beyrer и его соавторов.

Пятница, 5 апреля, ауд. 106. Начало в 17:00.

Докладчик: С.И. Грязнов.

Тема: Нижние оценки в древовидной системе доказательств Res(+) на ordering principles.Abstract Система доказательств Res(+), предложенная Ицыксоном и Соколовым, -- расширение резолюционной системы доказательств. Она оперирует с дизъюнкциями линейных равенств над . В докладе мы рассмотрим технику доказательства нижних оценок на размер доказательств некоторых противоречивых семейств формул для древовидной Res(+), основанную на играх Прувера и Дилеера. Данная техника является обобщением доказательства нижней оценки для принципа Дирихле. Затем мы применим данную технику для доказательства нижних оценок на Ordering principle и Dense Linear Ordering principle.

Ordering principle утверждает, что не существует конечного линейного порядка без минимума. Мы дадим нижнюю оценку на размер любого древовидного Res(+) доказательства этого утверждения, записанного в КНФ. Dense Linear Ordering principle утверждает, что не существует конечных плотных линейных порядков. Мы дадим нижнюю оценку на размер любого древовидного Res(+) доказательства этого утверждения, записанного в КНФ.

Ordering principle и Dense Linear Ordering principle имеют доказательство полиномиального размера в резолюциях. Таким образом, мы приведем естественные примеры, разделяющие древовидную версию системы Res(+) и резолюцию.

Семинар: Городской алгебраический семинар им. Д.К.ФаддееваВремя: понедельник, 8 апреля 2019, 10:30Место: ком. 311Докладчик: П. Б. Гвоздевский (СПбГУ)Тема: О надгруппах подсистемных подгрупп

Городской семинар по теории вероятностей и математической статистике, 29 марта 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 28 марта 2019, 16:00Место: комната 203Докладчик: С. В. Буяло (ПОМИ)Тема: SRA-free условие Золотова для самосжимающихся кривых и невырожденность zz-расстояния для мебиусовых структур на окружностиАннотация: 

Будет рассказано, как некоторый мебиусов вариант условия SRA-free
Золотова (отсутствие грубых малых углов) позволяет доказать,
что zz-расстояние на множестве гармонических четверок точек
мебиусовой струртуры на окружности является невырожденным и
полным.

Пятница, 29 марта, ауд. 106. Начало в 17:00.

Докладчик: Д.М. Ицыксон (ПОМИ РАН).

Тема: Нижние оценки для OBDD-систем доказательств, использующих несколько порядков на переменных.Abstract Упорядоченные диаграммы принятия решений (OBDD) - это частный случай однопроходных ветвящихся программ, в которых переменные встречаются в определенном порядке. Наложенное ограничение позволяет эффективно выполнять многие операции с булевыми функциями, записанными в этом виде. В 2004 году Атсериас, Варди и Колайтис предложили систему доказательств, в которых строки доказательств записываются в виде OBDD, из двух OBDD можно выводить любую OBDD, которая из них семантически следует. В 2008 году Крайчек доказал экспоненциальную нижнюю оценку в этой системе доказательств, если все OBDD в доказательстве используют одни и те же порядки на переменных. Если разрешить использовать в доказательствах OBDD в разных порядках, то получится строго более сильная система доказательств, для которой суперполиномиальных нижних оценок не известно.

В докладе мы рассмотрим исчисление однопроходных ветвящихся программ (1-BP), в котором можно выводить новые 1-BP как конъюнкцию уже имеющихся или как проекцию имеющейся 1-BP. Это семантическое обобщение некоторой подсистемы упомянутой выше OBDD-системы доказательств, в которой можно использовать различные порядки на переменных в OBDD. Мы покажем, что существует семейство невыполнимых формул в O(1)-КНФ и константа C, что любой вывод в этом исчислении, использующий проекции по не более, чем Cn различным переменным, имеет размер хотя бы .

Доклад основан на совместной работе с С. Басом, А. Кнопом, А. Рязановым и Д. Соколовым.

Городской семинар по теории вероятностей и математической статистике, 22 марта 2019 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)