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

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

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

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 19 сентября 2019, 16:00Место: комната 203Докладчик: А. Л. Вернер (РГПУ им. А. И. Герцена)Тема:  Прогулки среди многогранников ВложениеРазмер Прогулки среди многогранников.pdf589.33 КБ

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

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

Семинар: Городской алгебраический семинар им. Д.К.ФаддееваВремя: вторник, 3 сентября 2019, 11:00Место: ком. 311Докладчик:  Г. А. Гаркуши (Department of Mathematics, Swansea University)Тема: Сравнение мотивов гладких алгебраических многообразий

Городской семинар по теории вероятностей и математической статистике, 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

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

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

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

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

Система доказательств Res($lin_R$) определяется как расширение резолюционной системы доказательств Res, в ней выводимыми утверждениями являются дизъюнкции линейных уравнений над кольцом R. Одна из мотиваций для изучения таких систем заключается в том, что если R - это конечное поле $F_p$ или поле рациональных чисел, то Res(lin_R) является простейшим примером систем $AC_0[p]$-Frege или $TC_0$-Frege соответственно, доказательство суперполиномиальных нижних оценок на длины доказательств в которых - давно открытая проблема.

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