Seminars

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



Пятница 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.



Среда 24.10. Jarkko Kari (University of Turku): "Periodicity in Algebraic Subshifts"

Speaker: 
Jarkko Kari (University of Turku)
Date: 
Wednesday, October 24, 2018 - 14:00
Place: 
ауд. 203
Abstract: 

A two-dimensional configuration over the alphabet B={0,1} is a binary coloring Z^2 -> B of the infinite grid. For a finite subset D of Z^2, the D-patterns of a configuration are the patterns of shape D that appear in the configuration. The algebraic subshift defined by shape D is the set of the configurations whose D-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 2 sum of the colors on its north and north-east neighbors. We say a configuration has low complexity if it has at most |C| different C-patterns, for some finite C. 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 D has line factors in at most one direction.



Пятница 05.10. Д. Сагунов (АУ): "Параметризованная сложность задач о счастливой раскраске графов"

Speaker: 
Д. Сагунов (АУ)
Date: 
Friday, October 5, 2018 - 14:00
Place: 
106
Abstract: 

В задаче Maximum Happy Vertices (MHV) входом является граф, некоторые вершины которого изначально покрашены в несколько цветов. Вершина в графе называется счастливой, если она и все ее соседи имеют один и тот же цвет. Ответом на задачу является такая раскраска оставшихся вершин, что количество счастливых вершин в такой раскраске максимально возможно.

Во второй задаче о счастливой раскраске --- Maximum Happy Edges (MHE) --- требуется максимизировать количество счастливых ребер --- ребро считается счастливым, если его концы имеют один и тот же цвет. Эта задача очень тесно связана с задачей Multiway Cut, где требуется удалить минимальное число ребер в графе, чтобы выделенные вершины оказались в разных компонентах связности.

Известно, что обе задачи являются NP-трудными, если в раскраске используются хотя бы три различных цвета, даже на некоторых простых классах графов. Задача MHE находится в FPT, если в качестве параметра рассматривать количество счастливых ребер. Задача MHV, напротив, является W[1]-трудной, если в качестве параметра рассматривать требуемое количество счастливых вершин.

В трудах последних лет рассматриваются эти и другие параметры для задач MHE и MHV, многие из них --- структурные параметры графа. Для большинства из них получены верхние оценки, однако во многих из этих результатов необходимо фиксировать количество используемых в раскраске цветов. Для нескольких из них в работах оставлены открытые вопросы о существовании FPT-алгоритмов или полиномиальных ядер для задач MHV или MHE.

Мы отвечаем на многие из этих вопросов. Вот основные из этих результатов:
1) MHE NP-трудна уже на пороговых графах, а для MHV существует полиномиальный алгоритм на интервальных графах;
2) И MHV, и MHE W[1]-трудны для многих структурных параметров графа;
3) MHE W[1]-трудна для параметра "расстояние до кластерного графа", а для MHV существует FPT-алгоритм;
4) Для MHE и MHV не существует полиномиальных ядер относительно размера вершинного покрытия, если полиномиальная иерархия не схлопывается на третьем уровне.

Кроме того, мы устанавливаем важную связь между задачей MHV и задачей Node Multiway Cut, в которой требуется удалить наименьшее количество вершин, чтобы разрушить все пути между различными терминальными вершинами.

Мы постараемся рассмотреть и доказать вышеперечисленные результаты.



Пятница 21.09. Петр Смирнов: "Сложность выполнимых и невыполнимых цейтинских формул для однопроходных ветвящихся программ"

Speaker: 
Петр Смирнов
Date: 
Friday, September 21, 2018 - 14:00
Place: 
ауд. 106
Abstract: 

Классическая теория сложности изучает задачи распознавания: по входным данным необходимо выдать ответ «да» или «нет», то есть посчитать значение некоторой булевой функции. В теории сложности пропозициональных доказательств часто возникает задача поиска невыполненного дизъюнкта: по данной невыполнимой формуле в КНФ и подстановке значений переменных необходимо выдать какой-нибудь дизъюнкт формулы, который опровергается данной подстановкой. Мы рассмотрим однопроходные ветвящиеся программы (1-BP) и сравним для этой модели сложности двух естественных задач, связанных с цейтинскими формулами. Мы покажем, что задача вычисления значения выполнимой цейтинской формулы на графе G и задача поиска вершины, в которой нарушается условие четности, невыполнимой цейтинской формулы на графе G имеют близкую сложность для 1-BP. А именно, если минимальная программа для поиска вершины имеет размер S, то размер минимальной программы для вычисления значения имеет размер от S/n до S^O(log n), где n — число вершин в графе G.


Pages