Семинары

Рассылка: https://groups.google.com/forum/#!forum/spb-algo



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

Докладчик: 
Д. Сагунов (АУ)
Дата: 
Friday, October 5, 2018 - 14:00
Место: 
106
Аннотация: 

В задаче 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. Петр Смирнов: "Сложность выполнимых и невыполнимых цейтинских формул для однопроходных ветвящихся программ"

Докладчик: 
Петр Смирнов
Дата: 
Friday, September 21, 2018 - 14:00
Место: 
ауд. 106
Аннотация: 

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



Понедельник 06.08. Владимир Лифшиц (University of Texas at Austin): "Стабильные модели формул исчисления высказываний"

Докладчик: 
Владимир Лифшиц (University of Texas at Austin)
Дата: 
Monday, August 6, 2018 - 14:00
Место: 
ауд. 106
Аннотация: 

Понятие стабильной модели формулы исчисления высказываний служит основой новой формы декларативного программирования, которая часто применяется сегодня для решения переборных задач. Мы рассмотрим примеры программ этого типа, написанных в языке системы CLINGO, созданной в Потсдамском университете в Германии. Затем мы обсудим два конкурирующих определения стабильной модели, используемые разными группами программистов, и новые результаты, описывающие, при каких условиях эти определения эквивалентны.



Пятница 20.07. Zhi-Wei Sun (Nanjing University): "Problems and Results on Sums of Squares"

Докладчик: 
Zhi-Wei Sun (Nanjing University)
Дата: 
Friday, July 20, 2018 - 16:00
Место: 
ауд. 203
Аннотация: 

Due to the efforts of Fermat, Euler, Legendre and Gauss, it is known what
natural numbers can be written as the sum of two squares or three squares.
Lagrange's four-square theorem proved in 1770 states that each natural
number can be expressed as the sum of four squares.
In the talk we will first review classical results on sums of two or three
or four squares. Then we turn to the speaker's recent discoveries which
refine Lagrange's four-square theorem or the Gauss-Legendre theorem on
sums of three squares.
In particular we will introduce our results refining Lagrange's
four-square theorem as well as some recent conjectures of the speaker one
of which states that any integer greater than one can be written as the
sum of two squares, a power of 3 and a power of 5.



Пятница 13.07. Д. Соколов: "От доказательств к вычислениям"

Докладчик: 
Д. Соколов
Дата: 
Friday, July 13, 2018 - 13:30
Место: 
203
Аннотация: 

Монотонные Span Programs (mSP) были предложены Карчмером и Вигдерсоном в начале 90-х годов, позднее было
доказано, что они моделируют монотонные булевы формулы. Также известно квазиполиномиальное разделение между
mSP над полем F_2 и монотонными схемами.

Пользуясь недавними теоремами о лифтинге мы покажем, что задача о разделении данных моделей вычислений следует из разделения резолюционной системы доказательств и Nullstellensatz. Мы предъявим экспоненциальное разделение данных систем.


Pages