Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



Понедельник 19.11. Федор Парт: "Нижние оценки для резолюций с линейными уравнениями над кольцами"

Speaker: 
Федор Парт
Date: 
Monday, November 19, 2018 - 14:00
Place: 
ауд. 106
Abstract: 

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

В докладе мы докажем ряд dag-like и tree-like верхних и нижних оценок на размер доказательств в Res($lin_F$) для разных полей F. В случае char(F)=0 мы докажем экпоненциальную нижнюю оценку, но не для КНФ, а для клоза вида $a_1x_1+...+a_nx_n=A$ для больших, то есть растущих суперполиномиально от n, коэффициентов. Эта оценка получается как следствие из полиномиальных нижних и верхних оценок на размер кратчайшего Res($lin_F$) доказательства как функции от размера образа линейной формы $a_1x_1+...+a_nx_n$. Также в случае char(F)=0 мы докажем экспоненциальную tree-like нижнюю оценку на $a_1x_1+...+a_nx_n=A$, если коэффициенты малы, то есть ограничены полиномом от 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($lin_{F_2}$) нижней оценки на PHP для произольных полей F с помощью теоремы Алона-Фюреди о покрытиях гиперкуба гиперплоскостями.

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



Пятница 16.11. Людмила Глинских: "Нижняя оценка на размер ветвящихся программ и формул для задачи Orthogonal Vectors"

Speaker: 
Людмила Глинских
Date: 
Friday, November 16, 2018 - 14:00
Place: 
ауд. 106
Abstract: 

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

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

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



Пятница 09.11. В.В. Подольский (ВШЭ): "Нижние оценки в модели разрешающих деревьев с XOR-запросами"

Speaker: 
В.В. Подольский (ВШЭ)
Date: 
Friday, November 9, 2018 - 14:00
Place: 
106
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. Также мы приведем пример функции, для которой наша нижняя оценка не является точной. Из наших результатов вытекает новая нижняя оценка на мультипликативную сложность функции голосования. Доклад основан на совместной работе с Анастасией Чистопольской.



Пятница 02.11. Jarkko Peltomäki (University of Turku): "On Numeration Systems and Automatic Sequences"

Speaker: 
Jarkko Peltomäki (University of Turku)
Date: 
Friday, November 2, 2018 - 14:00
Place: 
ауд. 106
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.10. Mika Hirvensalo (University of Turku): "Decidable and undecidable problems related to Measure-Once Quantum Automata with rational and irrational coefficients"

Speaker: 
Mika Hirvensalo (University of Turku)
Date: 
Friday, October 26, 2018 - 14:00
Place: 
ауд. 106
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.


Pages