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

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

Докладчик: В.В. Подольский (ВШЭ).

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

Гранулярностью gran(f) булевой функции f называется минимальное натуральное k, такое что всякий коэффициент Фурье функции f выражается как целое число, умноженное на 1/2^k. Мы докажем, что D(f) ≥ gran(f)+1. Эта нижняя оценка является усилением оценок на D(f) через l_0-норму спектра Фурье f и через степень f как многочлена над GF(2). Используя новую оценку мы находим точное значение D(f) для некоторых важных функций f, включая функцию голосования и итерированную функцию голосования. Для функции голосования сложность оказывается равной n-B(n)+1, где B(n) равно числу единиц в двоичной записи n. Для итерированной функции голосования сложность равна (n+1)/2. Также мы приведем пример функции, для которой наша нижняя оценка не является точной. Из наших результатов вытекает новая нижняя оценка на мультипликативную сложность функции голосования. Доклад основан на совместной работе с Анастасией Чистопольской.

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

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

Докладчик: В.В. Подольский (ВШЭ).

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

Гранулярностью gran(f) булевой функции f называется минимальное натуральное k, такое что всякий коэффициент Фурье функции f выражается как целое число, умноженное на 1/2^k. Мы докажем, что D(f) ≥ gran(f)+1. Эта нижняя оценка является усилением оценок на D(f) через l_0-норму спектра Фурье f и через степень f как многочлена над GF(2). Используя новую оценку мы находим точное значение D(f) для некоторых важных функций f, включая функцию голосования и итерированную функцию голосования. Для функции голосования сложность оказывается равной n-B(n)+1, где B(n) равно числу единиц в двоичной записи n. Для итерированной функции голосования сложность равна (n+1)/2. Также мы приведем пример функции, для которой наша нижняя оценка не является точной. Из наших результатов вытекает новая нижняя оценка на мультипликативную сложность функции голосования. Доклад основан на совместной работе с Анастасией Чистопольской.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 1 ноября 2018, 16:00Место: комната 203Докладчик: Е. СтепановТема: Множества Чигера и изопериметрические башниАннотация: 

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

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

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

Докладчик: Jarkko Peltomäki (University of Turku).

Тема: On Numeration Systems and Automatic Sequences.Abstract A sequence is k-automatic if its elements are obtained when the base-k representations of integers are successively fed into a given finite automaton. For example, the famous Thue-Morse sequence abbabaabbaab... is 2-automatic: symbol a occurs at position n (indexing from 0) if and only if the base-2 representation of n contains an even number of 1's (this is checkable by a simple automaton). These k-automatic sequences are a well-studied object in combinatorics on words, and they have many good properties. One important feature is that any property of a k-automatic word that is expressible in a certain first-order logic is decidable. Moreover, these sequences satisfy many closure properties. For instance, taking the symbols whose indices are in an arithmetic progression in a k-automatic sequence is again k-automatic.

Using a more exotic way of representing integers than the usual base-k representation, this notion of a k-automatic word can be generalized. In the talk, I will introduce some unusual numeration systems, like Pisot numeration systems and Parry numeration systems. I will compare the corresponding automatic sequences with k-automatic sequences, and sketch ideas that show that the Pisot case is similar to the k-automatic case while the more general Parry-automatic sequences break many of the good properties (like decidability and closure properties mentioned above) of k-automatic sequences.

I will give definitions of automatic sequences and numeration systems, so no prior knowledge of them is needed.

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

Докладчик: Jarkko Peltomäki (University of Turku).

Тема: On Numeration Systems and Automatic Sequences.Abstract A sequence is k-automatic if its elements are obtained when the base-k representations of integers are successively fed into a given finite automaton. For example, the famous Thue-Morse sequence abbabaabbaab... is 2-automatic: symbol a occurs at position n (indexing from 0) if and only if the base-2 representation of n contains an even number of 1's (this is checkable by a simple automaton). These k-automatic sequences are a well-studied object in combinatorics on words, and they have many good properties. One important feature is that any property of a k-automatic word that is expressible in a certain first-order logic is decidable. Moreover, these sequences satisfy many closure properties. For instance, taking the symbols whose indices are in an arithmetic progression in a k-automatic sequence is again k-automatic.

Using a more exotic way of representing integers than the usual base-k representation, this notion of a k-automatic word can be generalized. In the talk, I will introduce some unusual numeration systems, like Pisot numeration systems and Parry numeration systems. I will compare the corresponding automatic sequences with k-automatic sequences, and sketch ideas that show that the Pisot case is similar to the k-automatic case while the more general Parry-automatic sequences break many of the good properties (like decidability and closure properties mentioned above) of k-automatic sequences.

I will give definitions of automatic sequences and numeration systems, so no prior knowledge of them is needed.

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

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

Докладчик: Mika Hirvensalo (University of Turku).

Тема: Decidable and undecidable problems related to Measure-Once Quantum Automata with rational and irrational coefficients.Abstract Measure-Once Quantum Automata, also known as Moore-Crutchfield QFA, are the most straightforward quantum variants of probabilistic finite automata: They are obtained by replacing the stochastic matrices by unitary ones, and L1-norm by L2-norm. It turns out that the expressive power of MO-QFA is weaker than that of PFA, but sometimes the MO-QFA may be exponentially more compact than their classical counterparts.

It may appear surprising that determining the emptiness of a strict cut-point languages for MO-QFA is decidable, whereas the same question for PFA is undecidable. On the other hand, removing the attribute "strict" yields an undecidable problem for MO-QFA again. In this talk, I will demonstrate that the ambiguity problem of the acceptance probability for MO-QFA is undecidable, if some radical irrational amplitudes are allowed. It turns out that, conditional to Bombieri-Lang conjecture (or to a speculation by Don Zagier), the problem remains undecidable even if only rational amplitudes are allowed.

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

Докладчик: Mika Hirvensalo (University of Turku).

Тема: Decidable and undecidable problems related to Measure-Once Quantum Automata with rational and irrational coefficients.Abstract Measure-Once Quantum Automata, also known as Moore-Crutchfield QFA, are the most straightforward quantum variants of probabilistic finite automata: They are obtained by replacing the stochastic matrices by unitary ones, and L1-norm by L2-norm. It turns out that the expressive power of MO-QFA is weaker than that of PFA, but sometimes the MO-QFA may be exponentially more compact than their classical counterparts.

It may appear surprising that determining the emptiness of a strict cut-point languages for MO-QFA is decidable, whereas the same question for PFA is undecidable. On the other hand, removing the attribute "strict" yields an undecidable problem for MO-QFA again. In this talk, I will demonstrate that the ambiguity problem of the acceptance probability for MO-QFA is undecidable, if some radical irrational amplitudes are allowed. It turns out that, conditional to Bombieri-Lang conjecture (or to a speculation by Don Zagier), the problem remains undecidable even if only rational amplitudes are allowed.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 25 октября 2018, 16:00Место: комната 203Докладчик: Г. Ю. Панина (ПОМИ)Тема: О модулярных компактификациях M0,nАннотация: 

Доклад по совместной работе с И. Некрасовым, arXiv:1808.08600.

 

Модулярные компактификации пространства M0,n  (=пространства наборов n точек на комплексной  проективной прямой) расклассифицированы в 2013 D. Smyth, и могут быть представлены в виде ЧУМа, стрелки диаграммы Хассе которого отвечают раздутиям. Максимальным элементом в этой иерархии является компактификация Делиня-Мамфорда, а мы сосредоточим свое внимание на минимальных элементах. Последние соответствуют самодвойственным (по Александеру) симплициальным комплексами. Среди этих "минимальных" (в смысле ЧУМа)  компактификаций -- все существующие пространства трехмерных конфигураций шарнирных многоугольников.  Мы опишем кольца Чжоу (они же -- кольца когомологий) минимальных компактификаций и покажем, как считать числа пересечения классов Черна тавтологических расслоений на компактификациях.  

 

 

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

Cреда, 24 октября, ауд. 203. Начало в 14:00.

Докладчик: Jarkko Kari (University of Turku).

Тема: Periodicity in Algebraic Subshifts.Abstract A two-dimensional configuration over the alphabet is a binary coloring of the infinite grid. For a finite subset of , the -patterns of a configuration are the patterns of shape that appear in the configuration. The algebraic subshift defined by shape is the set of the configurations whose -patterns all contain an even number of 1s. For example, the Ledrappier subshift consists of those configurations where each cell is colored by the modulo sum of the colors on its north and north-east neighbors. We say a configuration has low complexity if it has at most different -patterns, for some finite . Every low complexity configuration is in some algebraic subshift so to understand the periodicity properties of general low complexity configurations it is enough to consider elements of algebraic subshifts. It turns out that in the Ledrappier subshift all low complexity configurations are periodic, and the same is true for any algebraic subshift whose defining shape has line factors in at most one direction.