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

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

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

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

Cреда, 10 июля, 203. Начало в 17:00.

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

Тема: A proof of the Sensitivity Conjecture & A tradeoff between length and width in PCR.Abstract Докладчиком предлагается рассмотреть две темы. Распределение времени семинара между темами будет определяться пожеланиями слушателей семинара.

Title: A proof of the Sensitivity Conjecture

In this talk we will show that for any function f block sensitivity of f is bounded by a polynomial of sensitivity of f.

Based on paper of Hao Huang: "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture".

Title: A tradeoff between length and width in PCR

For various proof systems we know that proof of small size can be translated into a proof of small degree (or small width). In this constructions, the size of the final proof is usually exponential in terms of variables of the formula. For Resolution Thapen showed that it is necessary. We extend his result into polynomial calculus proof system.

More formally:
We construct a formula \varphi of size n that in polynomial calculus resolution (PCR) has a refutation of polynomial size and degree c := n^{1 - o(1)} and hence a refutation of exponential size and degree n^{0.5 + o(1)}. However, we show that there is no refutation achieving both polynomial size and degree at most c - O(\lg n)$ at the same time.

Joint work with Guillaume Lagarde, Jakob Nordström, Joseph Swernofsky.

Cреда, 10 июля, 203. Начало в 12:00.

Докладчик: Navid Talebanfard (Institute of Mathematics CAS, Prague).

Тема: A separator theorem for hypergraphs and a CSP-SAT algorithm.Abstract I will show how to remove a small number of edges from a hypergraph of small degree to break it into small connected components. I will then use it to solve CSP-SAT instances in which no variable appears in too many constraints and to give refutations of Tseitin formulas in small degree graphs with savings independent of the degree.

Joint work with Michal Koucký and Vojtěch Rödl.

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

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

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

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

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 30 мая 2019, 16:00Место: комната 203Докладчик: А. Е. Мадисон ( Центр перспективных исследований, Санкт-Петербургский политехнический университет Петра Великого)Тема: Некоторые замечательные апериодические самоподобные разбиения, генерируемые при помощи подстановок, и описание структуры икосаэдрических квазикристалловАннотация: 

Краткая аннотация: Предложено теоретическое описание структуры
икосаэдрических квазикристаллов без привлечения
методов многомерной кристаллографии и проецирования из шестимерного
пространства (cut-and-project method).
Предлагаемый метод основан на использовании оригинального алгоритма
построения разбиения Соколара-Стейнхардта
и метода квази-элементарных ячеек.

План доклада:
- Использование идей Дэвида Мамфорда (лауреат медали Филдса, 1974) для
анализа некоторых свойств разбиения Пенроуза.
(Имеется в виду монография "Ожерелье Индры", "Indra's pearls: The vision
of Felix Klein" и, в особенности, глава
"Двойные спирали и преобразование Мёбиуса")
- Пенроузо-подобные разбиения с симметрией 7-го порядка.
(Будут продемонстрированы несколько успешных примеров использования идей
Мамфорда для построения самоподобных
разбиений плоскости с симметрией 7-го порядка )
- Рекурсивный алгоритм построения икосаэдрического разбиения
Соколара-Стейнхардта (3D аналога разбиения Пенроуза).
Заполнение всего 3D пространства четырьмя типами "золотых" зоноэдров.
Правила подстановок, правила локального
соответствия, рекурсивный алгоритм заполнения пространства, генерация всех
3-х типов локально-изоморфных
икосаэдрических упаковок по общим правилам. Матрица подстановок и что даёт
её анализ в рамках теории Перрона-Фробениуса.
- Расчет дифракции от самоподобных структур. Парциальные структурные
факторы для каждого типа квази-элементарных
ячеек. Матрица подстановок с фазовыми множителями. Усреднение парциальных
структурных факторов.
(Эту часть можно переформулировать как "Фурье-преобразование почти
периодических функций и родственные проблемы").
Разбиение "вертушка" или "цевочное колесо", Conway-Radin pinwheel (не
решено).

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

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

На докладе будут рассказаны основные результаты и 

вопросы в данной области. Будет рассказан контр-пример

к теореме Мовахеди-Ланкарани Уэллса, а также ее, 

осиротевшее следствие.

 

(Я буду рассказывать только про теоремы и вопросы, где 

нужно вложить метрическое пространство целиком. 

Про науку о вложении n точечных подмножеств я знаю 

очень мало.)

 

Пятница, 31 мая, ПОМИ РАН, ауд. 106. Начало в 17:00.

Докладчик: М.Р. Старчак (Санкт-Петербургский государственный университет).

Тема: О совместности систем выражений вида НОД(a,x+b)=d с приложением к проблемам элиминации кванторов.Abstract Разрешимость элементарной теории целых чисел с единицей, сложением, равенством и отношением порядка (назовём её PA) была доказана Мойжешем Пресбургером в 1929 году. Было показано, что если обогатить сигнатуру экзистенциально выразимыми отношениями делимости на константы 2, 3, 4 и т.д., то по всякой формуле можно построить эквивалентную бескванторную. Так как отрицания отношений равенства, порядка и делимостей выразимы бескванторными формулами, то, в действительности, достаточно рассматривать только положительные (не содержащие логической связки отрицания) экзистенциальные фомулы. Помимо доказательства разрешимости, процесс элиминации кванторов позволяет описать выразимые в рассматриваемой структуре множества.

Элементарная теория целых чисел с единицей, сложением, порядком и делимостью (PAD) неразрешима, как было показано Дж. Робинсон в 1949 году. В то же время, в 1976 году независимо А.П. Бельтюковым и Л. Липшицем была доказана разрешимость экзистенциальная теории указанной структуры (назовём эту теорию EPAD). Так как неделимость оказывается экзистенциально выразимой, в данном случае невозможно построить по положительной экзистенциальной формуле эквивалентную бескванторную.

Всякую делимость x на число a можно записать в виде НОД(a,x)=a. В докладе будет дано необходимое и достаточное условие разрешимости систем выражений вида НОД(a,b+x)=d, где a и b — целые числа, причем a не равно 0; d — положительное целое. Этот результат является обобщением китайской теоремы об остатках. Далее будут рассмотрены примеры структур, элементарные теории которых неразрешимы, экзистенциальные разрешимы как подтеории EPAD, но для положительных экзистенциальных формул которых уже можно построить эквивалентные бескванторные с помощью полученного обобщения китайской теоремы.

Cреда, 29 мая, ПОМИ РАН, ауд. 106. Начало в 15:00.

Докладчик: С.Н. Артёмов (The Graduate Center of the City University of New York).

Тема: О доказательствах непротиворечивости.Abstract Теоремы Гёделя о неполноте основаны на арифметизации содержательных математических рассуждений в виде арифметических формул. При этом как Гёдель, так и Гильберт допускали, что такая арифметизация не покрывает всех «финитарных» методов и отмечали, что теорема о неполноте не влечёт невозможность финитарных доказательств непротиворечивости.

Однако получила распространение противоположная точка зрения, восходящая к фон Нейману, и состоящая в том, что гёделевская арифметизация покрывает все методы, выразимые в арифметике Пеано РА (а следовательно, и все финитарные методы) и что, тем самым, теорема Гёделя влечёт невозможность доказательства непротиворечивости РА методами, выразимыми в РА.

Мы приводим простой пример содержательного доказательства методами, выразимыми в РА, которое не представляется в виде единой формулы. Мы также даём математическое доказательство непротиворечивости РА методами, формализуемыми в РА; оно основано на известной технике частичных предикатов истинности.

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

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

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 16 мая 2019, 16:00Место: комната 203Докладчик: Е. А. Фоминых (СПбГУ)Тема: Вычисление сложности трехмерных многообразийАннотация: 

Сложность трехмерного многообразия - естественный инвариант трехмерных многообразий, введенный С.В. Матвеевым. Вычислить сложность многообразия довольно трудно. В докладе будет сделан обзор результатов докладчика и его соавторов по вычислению сложности для нескольких бесконечных серий многообразий.

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

Семинар: Городской алгебраический семинар им. Д.К.ФаддееваВремя: понедельник, 13 мая 2019, 10:30Место: ком. 311Докладчик: Е. А. Егорченкова (РГПУ им. А.И.Герцена)Тема: Вербальные отображения групп Шевалле над бесконечными полямиАннотация: 

Для любой группы $G$ и элемента (слова) $w = w(x1,\dots,x_n)$ свободной
группы $F_n$ определено вербальное отображение $\tilde w : G^n \to G$, заданное формулой
$\tilde w(g_1,dots,g_n) = w(g_1,dots,g_n)$. В последние годы вырос интерес к вербальным отображениям для случаев, когда $G = G(K)$ группа точек простой алгебраической
группы. В докладе рассматриваются вербальные отображения групп $G=G(K)$
для случая, когда $G$ -- простая односвязная алгебраическая группа, определенная и
расщепимая над бесконечным полем $K$.
 

ВложениеРазмер Доклад Егорченкова.pdf81.57 КБ

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