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

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

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 25 апреля 2019, 16:00Место: комната 203Докладчик: А. В. Малютин (ПОМИ)Тема:  Метрические обобщения теоремы Борсука–Улама. Часть 3.Аннотация: 

Совместное исследование с О.Р.Мусиным.

Будут обсуждаться новые обобщения теоремы Борсука–Улама, полученные с
помощью триангуляций Делоне и диаграмм Вороного.

Теорема Борсука–Улама утверждает, что при непрерывном отображении n-мерной сферы в n-мерное евклидово пространство на сфере найдутся антиподальные точки с совпадающими образами.

Мы доказываем, что при непрерывном отображении n-мерной сферы в N-мерное евклидово пространство при N>n на сфере найдутся достаточно далекие точки, образы которых в определенном смысле близки.

Точная формулировка одного из новых результатов выглядит следующим образом:

Пусть S^n – сфера единичного радиуса в R^{n+1} и пусть f: S^n –> R^N –
непрерывное отображение. Тогда на S^n найдется пара точек X и Y, евклидово расстояние между которыми составляет по меньшей мере корень из двух, а образы f(X) и f(Y) в R^N лежат на крае некоторого шара B, внутри которого точек образа f(S^n) не имеется. В частности, если образ f(S^n) гомеоморфен шару, то на S^n найдется пара точек X и Y, евклидово расстояние между которыми составляет по меньшей мере корень из двух, а образы f(X) и f(Y) совпадают.

 

 

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

Докладчик: Андрей Рыжиков (университет Пари-Эст Марн-ля-Вале, Франция).

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

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

Это совместная работа с Мареком Шикуа (университет Вроцлава, Польша), являющаяся усилением наших результатов с MFCS 2018.

Петербургский топологический семинар им. В. А. Рохлина, 22 апреля 2019 г. 17:15, г. Санкт-Петербург, ПОМИ, комн. 203 (наб. р. Фонтанки, 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Докладчик: П. Б. Гвоздевский (СПбГУ)Тема: О надгруппах подсистемных подгрупп

Классическое определение коммуникационного протокола использует фиксированное разбиение входных переменных на 2 множества $X\cup Y = M$. Мы рассмотрим естественное обобщение, в котором протокол может недетерминированно выбирать между $k$ различными подпротоколами, каждый из которых использует разное разбиение $f_1(X_1, Y_1)$, ... $f_k(X_k, Y_k)$, определим multi-partition communication complexity, и изучим её связь с нижними оценками на сложность однопроходных ветвящихся программ.

Первая статья Колмогорова 1965 года указывала "три подхода к определению количества информации" - комбинаторный (логарифм мощности), вероятностный (шенноновская энтропия) и алгоритмический (длина кратчайшего описания). Эта возможность перевода с одного языка на другой многократно оказывалась полезной: скажем, теорема Харпера о множестве с минимальной окрестностью в булевом кубе была переформулирована (Бюрман, Верещагин, Фортноу и др.) как возможность увеличить колмогоровскую сложность изменением некоторой доли битов.