Понедельник, 10 декабря, 106. Начало в 14:30.

Докладчик: А.Х. Шень (LIRMM, ИППИ РАН).

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

(по работе с Глебом Пособиным)

Семинар: Городской алгебраический семинар им. Д.К.ФаддееваВремя: понедельник, 3 декабря 2018, 10:30Место: ком. 311Докладчик: И. М. Зильберборд (СПбГУ)Тема: Обобщённая теорема о согласованных разложениях для модулей над полусовершенными кольцами

Семинар: Городской алгебраический семинар им. Д.К.ФаддееваВремя: понедельник, 26 ноября 2018, 10:30Место: ком. 311Докладчик: Н. М. Добровольский (Тульский гос. университет)Тема: Теоретико-числовой метод в приближенном анализе: история, достижения, проблемыМатериалы:  Dobrovolski.pdf

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

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

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

Пятница, 7 декабря, ПОМИ РАН, ауд. 106. Начало в 14:00.

Докладчик: С.Л. Кузнецов (Математический институт им. В.А. Стеклова РАН).

Тема: Звёздочка Клини в структурах с делениями.Abstract Итерация, или звёздочка Клини, является одной из наиболее интересных алгебраических операций, встречающихся в теоретической информатике. В докладе будет рассказано о поведении этой операции в частично упорядоченных структурах, содержащих операции деления. Операции деления проще всего объяснить с лингвистической точки зрения, на алгебре формальных языков над некоторым алфавитом. Например, если S — язык, состоящий из всех правильно построенных предложений, а N — язык имён существительных, то к языку N\S будут относиться непереходные глаголы (если к такому глаголу приписать слева существительное, то получится правильное предложение); в N\S/N будут переходные глаголы, и т.д. Поскольку формальные языки в общем случае некоммутативны (порядок букв и слов имеет значение), различают левое и правое деления. Звёздочка Клини также естественно вписывается в эту лингвистическую модель: например, S* будет множеством правильных текстов (конечных последовательностей предложений). Другой естественный пример — алгебра бинарных отношений на некотором множестве, где звёздочка Клини — это рефлексивно-транзитивное замыкание. Если понимать бинарное отношение как некоторое (недетерминированное) действие на множестве состояний: xRy, если при действии R система переходит из состояния x в состояние y, — то деление R\S соответствует действию, которое, будучи предварено действием R, даст действие S. В таком случае звёздочка Клини R* означает повторение действия R несколько (возможно ноль) раз. В общем же случае звёздочку Клини a* можно определять по-разному: как предел n-ых степеней a (с помощью омега-правила) или посредством какой-либо из разновидностей индуктивного определения. Будет рассказано как об известных, так и о новых результатах о соотношениях между этими подходами, об алгоритмической сложности соответствующих логик (эквациональных теорий), о полноте и неполноте относительно упомянутых выше естественных интерпретаций.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 29 ноября 2018, 16:00Место: комната 106Докладчик: С. В. Буяло (ПОМИ)Тема: Обратная задача мебиусовой геометрии на окружностиАннотация: 

Будет рассказано об условиях, при которых мебиусова
структура на окружности индуцирована гиперболическим
пространством. Кроме того, я объясню, что мебиусовы
структуры, выделяемые упомянутыми условиями, образуют
окрестность канонической структуры (индуцированной
гиперболической плоскостью H^2) в подходящей тонкой
топологии.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 22 ноября 2018, 16:00Место: комната 106Докладчик: А. В. Малютин (ПОМИ)Тема: Метрические обобщения теоремы Борсука–Улама 2Аннотация: 

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

Будут обсуждаться новые результаты о расстоянии Борсука–Улама в
продолжение доклада от 11 октября 2018.

Аннотация доклада от 11 октября 2018:

Пусть X и Y – метрические пространства, f – отображение из X в Y. Точки a
и b, лежащие в X, назовем f-соседними, если их образы f(a) и f(b)
совпадают или лежат в Y на крае метрического шара, внутренность которого
не затронута образом f(X).

Расстоянием (или шириной, или поперечником) Борсука–Улама для отображения
f будем называть супремум расстояний между f-соседними точками в X.

Расстоянием Борсука–Улама для пары (X,Y) будем называть инфимум расстояний
Борсука–Улама для непрерывных отображений из X в Y.

Расстоянием Борсука–Улама для пространства X будем называть инфимум
расстояний Борсука–Улама пар (X,Y) для всевозможных стягиваемых Y.

Теорема Борсука–Улама утверждает, что расстояние Борсука–Улама пары
(n-мерная сфера, n-мерное евклидово пространство) совпадает с диаметром
сферы.

Мы получаем оценки на расстояние Борсука–Улама для некоторых пространств с
помощью лемм Шпернера и Кнастера–Куратовского–Мазуркевича.

Пятница, 30 ноября, ауд. 106. Начало в 14:00.

Докладчик: Татьяна Белова.

Тема: Верхние и нижние оценки для различных параметризаций задачи (n, 3)-MAXSAT.Abstract Задача (n,3)-MAX-SAT является частным случаем задачи MAX-SAT с дополнительным ограничением на входную формулу, что каждая переменная встречается в формуле не более трех раз. Мы рассмотрим различные параметризации этой задачи, улучшим известные ранее верхние оценки на время решения (n,3)-MAXSAT относительно числа переменных в формуле, а также относительно числа клозов, которые мы хотим выполнить.
Кроме того, мы покажем, что выполнить хотя бы на один клоз больше, чем при тривиальном означивании, где всем переменным присваивается истина, уже является NP-трудной задачей.

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

Пятница, 23 ноября, ауд. 106. Начало в 14:00.

Докладчик: Анастасия Софронова.

Тема: Верхние оценки на размер dag-like коммуникационных протоколов.Abstract Dag-like коммуникационные протоколы — обобщение классических коммуникационных протоколов. С их помощью можно перенести нижние оценки на ширину резолюционного доказательства невыполнимой формулы на другие системы доказательств, а также на размер монотонных схем для некоторых связанных задач. Для этого используется техника lifting — вместо каждой переменной формулы подставляется некоторая функция от новых переменных, так называемый гаджет. Однако известные гаджеты, подходящие для этой техники, имеют большой размер. Вопрос, можно ли использовать гаджет константного размера, является открытым. Мы рассмотрим некоторые конкретные гаджеты константного размера и приведём пример семейства формул, показывающий, что их нельзя использовать для переноса нижних оценок. А именно, рассмотрим семейство формул с минимальной шириной резолюционного доказательств и полиномиальным размером dag-like протокола для задачи поиска невыполненного дизъюнкта после подстановки гаджета.

Понедельник, 26 ноября, ПОМИ РАН, ауд. 106. Начало в 14:00.

Докладчик: А.В. Родин (Институт философии РАН).

Тема: Конструктивный аксиоматический метод и унивалентные основания математики.Abstract Современное понятие аксиоматического метода восходит к работам Давида Гильберта по основаниям математики в первой половине 20-го века. Свою новую версию аксиоматического метода Гильберт называл «экзистенциальным» аксиоматическим методом и отличал её от более традиционного метода построения математических теорий, который он называл «генетическим» или «конструктивным». Отличие конструктивного метода от экзистенциального состоит в том, что в первом случае используются правила для конструирования непропозициональных объектов из данных примитивных объектов, тогда как во втором случае в каждой интерпретации формальной теории объекты предполагаются фиксированными, и теория содержит только логические правила, с помощью которых из одних пропозиций выводятся другие пропозиции. Унивалентные основания математики представляют собой основанную на теории типов формальную схему для генетического конструирования математических теорий, в рамках которой логические правила вывода оказываются частным случаем более общих правил, которые применяются также и к непропозициональным объектам. Такой новый подход в основаниях математики эффективно решает задачу компьютерной проверки нетривиальных математических доказательств, а также устанавливает более тесную связь между логическими и внелогическими элементами математического рассуждения, чем стандартный подход.

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

Понедельник, 19 ноября, ауд. 106. Начало в 14:00.

Докладчик: Федор Парт.

Тема: Нижние оценки для резолюций с линейными уравнениями над кольцами.Abstract Система доказательств Res() определяется как расширение резолюционной системы доказательств Res, в ней выводимыми утверждениями являются дизъюнкции линейных уравнений над кольцом R. Одна из мотиваций для изучения таких систем заключается в том, что если R - это конечное поле или поле рациональных чисел, то Res(lin_R) является простейшим примером систем -Frege или -Frege соответственно, доказательство суперполиномиальных нижних оценок на длины доказательств в которых - давно открытая проблема. Оказывается, даже для Res() проблема доказательства нижних оценок в общем случае крайне нетривиальна и на данный момент является открытой.

В докладе мы докажем ряд dag-like и tree-like верхних и нижних оценок на размер доказательств в Res() для разных полей F. В случае char(F)=0 мы докажем экпоненциальную нижнюю оценку, но не для КНФ, а для клоза вида для больших, то есть растущих суперполиномиально от n, коэффициентов. Эта оценка получается как следствие из полиномиальных нижних и верхних оценок на размер кратчайшего Res() доказательства как функции от размера образа линейной формы . Также в случае char(F)=0 мы докажем экспоненциальную tree-like нижнюю оценку на , если коэффициенты малы, то есть ограничены полиномом от n. Это влечет экспоненциальное разделение dag-like и tree-like Res(lin_F) в случае малых коэффициентов

Для конечных полей мы докажем экспоненциальные разделения между tree-like Res(lin_Fp) и tree-like Res(lin_Fq) для различных p и q, где в качестве разделяющих КНФ использованы mod-p Цейтинские формулы. Этот результат, а также экспоненциальная нижняя оценка для tree-like Res(lin_Fp) на случайных КНФ, получается как следствие варианта классического соотношения ширины и размера резолюционных доказательств вкупе с нижней оценкой на ширину через симуляцию в Polynomial Calculus. Мы обобщим доказательство Ицыксона и Соколова tree-like Res() нижней оценки на PHP для произольных полей F с помощью теоремы Алона-Фюреди о покрытиях гиперкуба гиперплоскостями.

Доклад основан на совместной статье с И. Цамеретом.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 15 ноября 2018, 16:00Место: комната 106Докладчик: А. В. Смирнов (ПОМИ)Тема: О квази-изометрической и билипшицевой классификациях 3-мерных групп ЛиАннотация: 

Доклад по работе K. Fassler и E. Le Donne.

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

Докладчик: Людмила Глинских.

Тема: Нижняя оценка на размер ветвящихся программ и формул для задачи Orthogonal Vectors.Abstract Мы рассмотрим задачу Orthogonal Vectors, в которой дано множество из n d-мерных булевых векторов и необходимо определить, есть ли среди этого множества два вектора ортогональных друг другу. Существует гипотеза (Orthogonal Vector Conjecture, OVC), что при d порядка log(n) любой алгоритм для данной задачи работает за время . В предположении данной гипотезы уже доказаны нижние оценки для многих других задач из класса P, например, для задач Edit Distance и Longest Common Subsequence.

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

Доклад по статье The Orthogonal Vectors Conjecture for Branching Programs and Formulas авторов Daniel Kane и Ryan Williams.

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

Понедельник, 12 ноября, ауд. 106. Начало в 14:00.

Докладчик: Кирилл Симонов (Университет Бергена).

Тема: Параметризованная сложность задачи k-means.Abstract k-means кластеризация -- это следующая задача: по данным n точкам в найти k центров кластеров так, чтобы минимизировать сумму расстояний от точек до ближайших к ним центрам кластеров. Задача получила широкую известность благодаря применениям в data mining, и в особенности эвристическому алгоритму Ллойда. Известно, что найти
оптимальную кластеризацию NP-трудно даже при d=2 или k=2, в то же время существует алгоритм со временем работы . Мы впервые рассматриваем задачу k-means с точки зрения параметризованной сложности, где целью является либо нахождение алгоритма со временем
работы для некоторого параметра задачи t, либо доказательство невозможности его существования при условии FPT≠W[1]. Рассматриваемые нами параметры для k-means -- это k, d и искомое расстояние D (при условии, что входные данные целочисленные).

Используя алгоритм для быстрого нахождения подгиперграфа с малым fractional cover number, мы получаем FPT-алгоритм по D для -расстояния. Интересно, что в случае расстояния в задача ощутимо труднее — мы показываем, что одна из подзадач, возникающая в нашем алгоритме, является здесь W[1]-трудной. Мы также обобщаем эти результаты на для остальных значений p, и даем нижние оценки для некоторых комбинаций параметров в экстремальных случаях and . Отдельный интерес может представлять набор используемых нами сведений, позволяющих представить стандартные комбинаторные задачи на графах как геометрические задачи кластеризации.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 8 ноября 2018, 16:00Место: комната 106Докладчик: Н. Н. Косовский (СПбГУ)Тема: Volume pinching theorems for CAT(1) spacesАннотация: 

доклад по работе Koichi Nagano